1. 二叉树的实现分析

问题思考：如何存储一棵完全二叉树？
结果：使用一个数组，按照二叉树中每个节点的位置进行存储即可

完全二叉树的存储图示.png

如果不是一颗完全二叉树则在使用数组存储的时候就要将没有节点的位置置空，如下图所示，当一棵树是斜树的时候就会浪费很多存储空间，所以如果是斜树使用链式存储会更好一些，如果是一颗完全二叉树则使用数组存储是非常完美的。

一般树的存储图示.png

2. 二叉树的顺序存储实现

2.1 准备条件

我们在实现顺序存储的二叉树的时候，只需要一个数组即可，所以我们设计一个数组来存储二叉树。

代码实现：

#include <stdio.h>
#include "stdlib.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 100 /* 存储空间初始分配量 */
#define MAX_TREE_SIZE 100 /* 二叉树的最大结点数 */

typedef int Status;        /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int CElemType;      /* 树结点的数据类型，目前暂定为整型 */
typedef CElemType SqBiTree[MAX_TREE_SIZE]; /* 0号单元存储根结点  */
CElemType Nil = 0;   /*设整型以0为空 或者以 INT_MAX(65535)*/

// 节点的层和每层中的位置
typedef struct {
    int level; //结点层
    int order; //本层的序号(按照满二叉树给定序号规则)
} Position;

2.2 初始化并创建二叉树

初始化一个二叉树则需要将存储这个二叉树的所有节点置空即可，与清空一致。

代码实现：

/// 初始化一个二叉树
/// @param T 树
Status InitBiTree(SqBiTree T) {
    // 将所有节点置空
    for (int i = 0; i<MAX_TREE_SIZE; i++) {
        T[i] = Nil;
    }
    return OK;
}

// 在顺序存储中清空和初始化的操作是一样的
#define ClearBiTree InitBiTree

我们这里的创建一个二叉树就是能够自动给树创建一些节点，方便后续的测试，这里默认添加10个节点，在添加的时候做了一个判断，当前节点不为空，但其父节点为空则直接报错（根节点除外），其实我们这里判断这个有点多余，我们是按照完全二叉树的样子去创建的，但是如果在我们手动输入的时候难免会有错，所以多加些判断。

代码实现：

/// 创建一个树（按照完全二叉树初始化）
/// @param T 树
Status CreateBiTree(SqBiTree T) {
    int i = 0;
    while (i<10) {// 添加10个节点
        T[i] = i+1;
        // 如果该节点不是根节点，但有值，而且其父节点没值，则报错（防止手动插入的时候犯错）
        if (i!=0 && T[i] != Nil && T[(i+1)/2-1] == Nil) {
            printf("出现无双亲的非根结点%d\n",T[i]);
            exit(0);
        }
        i++;
    }
    // 将其余节点置空
    while (i<MAX_TREE_SIZE) {
        T[i] = Nil;
        i++;
    }
    
    return OK;
}

2.3 判断二叉树是否为空树

树最重要的就是根，没有根就没有树，所以二叉树的根节点为空则二叉树就是空树。
代码实现：

// 判断树是否为空，只需要判断根节点即可，根节点都没有指定为空
Status BiTreeIsEmpty(SqBiTree T) {
    
    if (T[0] == Nil) {
        return TRUE;
    } else {
        return FALSE;
    }
}

2.4 计算二叉树的深度

要想计算二叉树的深度就要找到最后一个节点，所以我们在顺序存储结构中通过从后往前遍历的方法找到的第一个有值的节点就是该二叉树的最后一个节点。

根据二叉树的节点规则，当2的当前深度的次幂超过刚才找到的位置时就找到了该二叉树的深度。
代码实现：

/// 二叉树的深度
/// @param T 树
int BiTreeDepth(SqBiTree T){
    int j = -1;
    // 如果树为空则返回-1
    if (BiTreeIsEmpty(T)) { return j; }
    
    int i;
    for (i = MAX_TREE_SIZE-1; i>=0; i--) {
        if (T[i] != Nil) {
            break;
        }
    }
    
    do {
        j++;
    } while (pow(2, j) <= i); //计算2的次幂
    
    return 0;
}

2.5 给定位置赋值

赋值操作首先要根据层号和序号找到需要赋值的位置，然后需要判断该位置是否合法，合法后给该位置赋值。

代码实现：

/// 给特定位置的节点赋值
/// @param T 树
/// @param p 位置
/// @param e 值
Status setValue(SqBiTree T, Position p, CElemType e) {
    
    // 找到位置
    int i = (int)pow(2, p.level-1) + p.order - 2;
    
    // 判断要赋值的位置的父节点是否为空
    if (T[(i+1)/2-1] == Nil && e != Nil) {
        return ERROR;
    }
    
    // 判断要赋值的位置的子节点是否有值
    if ((T[i*2+1] != Nil || T[i*2+1] != Nil) && e !=Nil) {
        return ERROR;
    }
    
    // 赋值
    T[i] = e;
    
    return OK;
}

2.6 获取根节点的值和指定位置的值

• 根节点
  代码实现：

/// 获取跟节点的值
/// @param T 树
/// @param e 值存储
Status Root(SqBiTree T,CElemType *e){
    if (BiTreeIsEmpty(T)) {
        return ERROR;
    }
    
    *e = T[0];
    return OK;
}

• 其他节点

根据传入的层号和该层序号找到此值的位置，返回即可

代码实现：

/// 获取给定位置的值
/// @param T 树
/// @param p 位置
CElemType getValue(SqBiTree T, Position p) {
    
    // 打印层
    printf("要获取的层号是：%d\n", (int)pow(2, p.level-1));
    // 打印序号
    printf("该层的序号是 %d\n", p.order);
    // 返回
    return T[(int)pow(2, p.level-1)+p.order-2];
}

2.7 获取某节点的父节点

获取双亲节点只需找到该节点，按照二叉树节点的规则，返回其双亲节点即可

/// 获取某个节点的父节点
/// @param T 树
/// @param e 节点值
CElemType GetParent(SqBiTree T, CElemType e){
    // 判断树是否为空
    if (T[0] == Nil) { return Nil; }
    // 遍历找到值所对应的节点，根节点没有双亲节点，所以从1开始
    for (int i = 1; i<MAXSIZE; i++) {
        if (T[i] == e) {
            return T[(i+1)/2 - 1];
        }
    }
    
    return Nil;
}

2.8 获取某节点的孩子节点（左右）

很简单，只需找到相应节点，然后根据规则查找左右孩子即可。

代码实现：

/// 获取某个节点的左孩子
/// @param T 树
/// @param e 节点值
CElemType getLeftChild(SqBiTree T, CElemType e) {
    // 树空判断
    if (T[0]==Nil) { return Nil; }
    
    // 找到e的位置
    for (int i=0; i<MAXSIZE-1; i++) {
        if (T[i]==e) {
            return T[i*2+1];
        }
    }
    
    return  Nil;
}

/// 获取某个节点的右孩子
/// @param T 树
/// @param e 节点值
CElemType getRightChild(SqBiTree T, CElemType e) {
    // 树空判断
    if (T[0]==Nil) { return Nil; }
    
    // 找到e的位置
    for (int i=0; i<MAXSIZE-1; i++) {
        if (T[i]==e) {
            return T[i*2+2];
        }
    }
    
    return  Nil;
}

2.9 获取某节点的兄弟节点（左右）

首先根据节点值找到节点，如果是找做兄弟则该节点必须是个右节点，反之也是。

/// 获取某个节点的左兄弟
/// @param T 树
/// @param e 节点值
CElemType GetLeftSibling(SqBiTree T, CElemType e){
    
    // 树空判断
    if (T[0]==Nil) { return Nil; }
    
    // 找到e的位置
    for (int i=1; i<MAXSIZE-1; i++) {
        // 值相等，并且找到的位置是右孩子，不然没有左兄弟
        if (T[i]==e && i%2==0) {
            return T[i-1];
        }
    }
    
    return Nil;
}

/// 获取某个节点的右兄弟
/// @param T 树
/// @param e 节点值
CElemType GetRightSibling(SqBiTree T, CElemType e){
    
    // 树空判断
    if (T[0]==Nil) { return Nil; }
    
    // 找到e的位置
    for (int i=1; i<MAXSIZE-1; i++) {
        // 值相等，并且找到的位置是左孩子，不然没有右兄弟
        if (T[i]==e && i%2==1) {
            return T[i+1];
        }
    }
    
    return Nil;
}

3. 二叉树的遍历

3.1 前序遍历

前序遍历（DLR/NLR），是二叉树遍历的一种，也叫做先序遍历。前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。

前序遍历.png
遍历结果为：ABCDGHCEIF

实现代码：

/// 前序遍历
/// @param T 树
/// @param e 节点
void PreTraverse(SqBiTree T, int e) {
    // 打印节点
    printf("%d ",T[e]);
    
    // 前序遍历左子树
    if (T[2*e+1] != Nil) {
        PreTraverse(T, 2*e+1);
    }
    
    // 前序遍历右子树
    if (T[2*e+2] != Nil) {
        PreTraverse(T, 2*e+2);
    }
}

/// 前序遍历封装
/// @param T 树
Status PreOrderTraverse(SqBiTree T){
    
    //树不为空
    if (!BiTreeIsEmpty(T)) {
        PreTraverse(T, 0);
    }
    printf("\n");
    return  OK;
}

3.2 中序遍历

中序遍历（LDR/LNR）是二叉树遍历的一种。在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。

中序遍历.png

遍历结果为：GDHBAEICF

实现代码：

/// 中序遍历
/// @param T 树
/// @param e 节点
void InTraverse(SqBiTree T, int e){
    // 如果传入节点的左子树不为空就一直寻找
    if (T[2*e+1] != Nil) {
        InTraverse(T, 2*e+1);
    }
    // 打印节点
    printf("%d ",T[e]);
    
    // 如果右子树也不为空则从该节点的右子树继续向下遍历
    if (T[2*e+2] != Nil) {
        InTraverse(T, 2*e+2);
    }
}

/// 中序遍历的包装
/// @param T 树
Status InOrderTraverse(SqBiTree T){
    
    // 树不为空则开始遍历
    if (!BiTreeIsEmpty(T)) {
        InTraverse(T, 0);
    }
    printf("\n");
    return OK;
}

3.3后序遍历

后序遍历（LRD/LRN）二叉树遍历的一种。在二叉树中，先左后右再根，即首先遍历左子树，然后遍历右子树，最后访问根结点。

后续遍历.png

遍历结果为：GHDBIEFCA

实现代码：

/// 后序遍历
/// @param T 树
/// @param e 节点
void PostTraverse(SqBiTree T, int e){
    // 如果传入节点的左子树不为空就一直寻找
    if (T[2*e+1] != Nil) {
        PostTraverse(T, 2*e+1);
    }
    
    // 如果右子树也不为空则从该节点的右子树继续向下遍历
    if (T[2*e+2] != Nil) {
        PostTraverse(T, 2*e+2);
    }
    
    // 打印节点
    printf("%d ",T[e]);
}

/// 后续遍历的包装
/// @param T 树
Status PostOrderTraverse(SqBiTree T)
{
    if(!BiTreeIsEmpty(T)){
        PostTraverse(T,0);
    }
        
    printf("\n");
    return OK;
}

3.4 层序遍历

层序遍历二叉树遍历的一种。即从根节点开始从左至右一层一层的遍历每个节点。

层序遍历.png

遍历结果为：ABCDEFGHI

实现代码：

/// 层序遍历
/// @param T 🌲
void LevelOrderTraverse(SqBiTree T) {
    // 初始化一个遍历存储值
    int i = MAX_TREE_SIZE-1;
    // 找到最后一个有值的
    while (T[i] == Nil) { i--; }
    // 遍历打印
    for (int j = 0; j<=i; j++) {
        if (T[j] != Nil) {
            printf("%d ", T[j]);
        }
    }
    printf("\n");
}

4 二叉树的链式存储实现

详细细节见注释，主要通过插入的时候进行前序方法进行设计，使用'#'作为判断到达叶子节点的条件，来实现叶子节点的置空操作。
代码实现：

#include <stdio.h>
#include "string.h"
#include "stdlib.h"
#include "math.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

/* 存储空间初始分配量 */
#define MAXSIZE 100
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;

char *chars;
int indexs = 0;

typedef char CElemType;
CElemType Nil=' '; /* 字符型以空格符为空 */
typedef struct BiTNode  /* 结点结构 */
{
    CElemType data;        /* 结点数据 */
    struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}BiTNode,*BiTree;


/// 初始化
/// @param T 树
Status InitBiTree(BiTree *T) {
    *T = NULL;
    return OK;
}

/// 创建一棵链式树
/// @param T 树
void CreateBiTree(BiTree *T){
    // 使用一个全局数组来实现初始化的插入
    CElemType c = chars[indexs++];
    printf("%c ", c);
    /*
     1.如果第一个节点就是占位的则树就是空的
     2.由于叶子节点没有孩子，为了占有其左右孩子指针，通过#来判断，
     如遇#其孩子指针为空
     3.通过#号来结束插入，初始化构建的时候需要设计好顺序
     
     */
    if (c == '#') {
        *T = NULL;
    } else {
        *T = (BiTree)malloc(sizeof(BiTNode));
        // 如果没创建成功就报错
        if (!*T) { exit(OVERFLOW); }
        // 赋值
        (*T)->data = c;
        // 构造左子树
        CreateBiTree(&(*T)->lchild);
        // 构造右子树
        CreateBiTree(&(*T)->rchild);
    }
}

/// 判断是否是空树
/// @param T 树
Status BiTreeIsEmpty(BiTree T)
{
    if (T == NULL) {
        return TRUE;
    } else {
        return FALSE;
    }
}

/// 获取根节点的值
/// @param T 树
CElemType GetRoot(BiTree T) {
    if (BiTreeIsEmpty(T)) {
        return Nil;
    }
    return T->data;
}

/// 销毁二叉树
/// @param T 树
void DestroyBiTree(BiTree *T){
    // 空就不销毁了
    if (*T) {
        // 销毁左孩子
        if ((*T)->lchild) {
            DestroyBiTree(&(*T)->lchild);
        }
        
        // 销毁右孩子
        if ((*T)->lchild) {
            DestroyBiTree(&(*T)->rchild);
        }
        // 释放根节点
        free(*T);
        // 置空
        *T = NULL;
    }
}


/// 二叉树深度
/// @param T 树
int BiTreeDepth(BiTree T){
    
    /*
     由于存在左子树和右子树，那个最深需要比较一下
     */
    
    int i,j;
    // 计算左孩子的深度
    if (T->lchild) {
        i = BiTreeDepth(T->lchild);
    } else { i=0; }//没有左子树i为0
    
    // 计算有子树的深度
    if (T->rchild) {
        j = BiTreeDepth(T->rchild);
    } else { j=0; }//没有左子树i为0
    
    return i>j?i+1:j+1;
}

/// 获取某个节点的值
/// @param p 节点
CElemType GetValue(BiTree p) {
    return p->data;
}

/// 设置某个节点的值
/// @param p 节点
/// @param value 值
void SetValue(BiTree p,CElemType value){
    p->data = value;
}

/// 前序遍历
/// @param T 二叉树
void PreOrderTraverse(BiTree T){
    // 非空判断
    if (T==NULL) { return; }
    // 打印
    printf("%c ", T->data);
    // 遍历左子树
    PreOrderTraverse(T->lchild);
    // 遍历右子树
    PreOrderTraverse(T->rchild);
}

/// 中序遍历
/// @param T 二叉树
void InOrderTraverse(BiTree T){
    // 非空判断
    if (T==NULL) { return; }
    // 遍历左子树
    InOrderTraverse(T->lchild);
    // 打印
    printf("%c ", T->data);
    // 遍历右子树
    InOrderTraverse(T->rchild);
}

/// 后序遍历
/// @param T 二叉树
void PostOrderTraverse(BiTree T){
    // 非空判断
    if (T==NULL) { return; }
    // 遍历左子树
    PostOrderTraverse(T->lchild);
    // 遍历右子树
    PostOrderTraverse(T->rchild);
    // 打印
    printf("%c ", T->data);
}



int main(int argc, const char * argv[]) {
    // insert code here...

    BiTree T;
    
    InitBiTree(&T);
    chars = "ABDH#K###E##CFI###G#J##";
    CreateBiTree(&T);
    
    printf("二叉树是否为空%d\n", BiTreeIsEmpty(T));
    printf("树的深度是%d\n", BiTreeDepth(T));
    printf("树根的值是%c\n", GetRoot(T));
    
    printf("\n前序遍历二叉树:");
    PreOrderTraverse(T);
    
    printf("\n中序遍历二叉树:");
    InOrderTraverse(T);
    
    printf("\n后序遍历二叉树:");
    PostOrderTraverse(T);
    
    printf("\n");
    
    return 0;
}