数据结构与算法15-二叉树

1.概念

度：

结点拥有的子树数目称为结点的度。

结点的层次：

从根开始定义起，根为第1层，根的子结点为第2层，以此类推。

高度或深度：

• 树中结点的最大层次。
• 深度从上往下。
• 高度从下往上。
  以下不是标准定义，但对于我来说很容易记忆。

满二叉树：

双亲结点都有2个儿子。

完全二叉树：

• 从根结点出发，最深一层以上是满二叉树。
• 最后一层叶子结点是从左到右是连续的，不存在中间有空结点的情况。

2.实现

2.1 顺序存储

2.1.1 结构定义

#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)*/

// 左儿子索引(双亲结点出发)
#define LeftChild(x) (x)*2+1
// 双亲索引(左儿子反过来算)
// 右儿子多的1，除以2后为0，没有影响
// 如果要记，就记左儿子算法，双亲直接反推
#define Parent(x) ((x)-1)/2

// 查找用
typedef struct {
    int level; //结点层
    int order; //本层的序号(按照满二叉树给定序号规则)
} Position;

2.1.2 基础操作

// 1.访问
Status visit(CElemType c){
    printf("%d ", c);
    return OK;
}

// 2.构造空二叉树
Status InitBiTree(SqBiTree T) {
    memset(T, Nil, MAX_TREE_SIZE-1);
//    for (int i = 0; i < MAX_TREE_SIZE; i++) {
//        //将二叉树初始化值置空
//        T[i] = Nil;
//    }
    return OK;
}

// 3.按层序次序输入二叉树中的结点值(字符型或整型)，构造顺序存储的二叉树T
Status CreateBiTree(SqBiTree T) {
    /*
            1       -->1
       2        3   -->2
     4    5   6   7 -->3
    8 9 10          -->4
    1 2 3 4 5 6 7 8 9 10 Nil Nil Nil
    */
    int i = 0;
    while (i < 10) {
        T[i] = i+1;
        printf("%d ",T[i]);
        //结点不为空，且无双亲结点
        if (i != 0 // 不是根结点需要判断双亲
            && T[i] != Nil // 结点不为空，如果双亲结点为空就有问题
            && T[Parent(i)] == Nil) { // 双亲结点为空
            printf("出现无双亲的非根结点%d\n",T[i]);
            T[i] = Nil;
            return ERROR;
            // 或者直接退出
//            exit(ERROR);
        }
        i++;
    }
    printf("\n");
    //将空赋值给T的后面的结点
    while (i < MAX_TREE_SIZE) {
        T[i] = Nil;
        i++;
    }
    return OK;
}

// 4.清空二叉树
// 两个函数完全一样，没必要写2份，但是为了阅读方便可以重命名
#define ClearBiTree InitBiTree

// 5.判断二叉树是否为空
Status BiTreeEmpty(SqBiTree T) {
    //根结点为空，则二叉树为空
    if (T[0] == Nil)
        return TRUE;
    return FALSE;
}

// 6.获取二叉树的深度
int BiTreeDepth(SqBiTree T) {
    int i = MAX_TREE_SIZE - 1, j = 0;
    for (; i>=0 && T[i] == Nil; i--);// 最后一个叶子节点
    // 左斜树序号  1 2 4 8 ...
    // 索引需要-1，0 1 3 7 ...，所以是powl(2, j)-1
    // j层的头序号比最后一个叶子节点大时停止遍历
    for (; powl(2, j)-1 <= i; j++);
    return j;
}

// 7.返回处于位置e(层,本层序号)的结点值
CElemType Value(SqBiTree T, Position e){
    /*
     Position.level -> 结点层.表示第几层;
     Position.order -> 本层的序号(按照满二叉树给定序号规则)
     */
    // 深度为层数-1
    int depth = e.level - 1;
    // 左斜树序号  1 2 4 8 ...
    // 索引需要-1，0 1 3 7 ...，所以是powl(2, depth)-1
    int levelStart = (int)pow(2, depth) - 1;
    // order从1开始而不是0，所以-1
    int idx = e.order - 1;
    return T[levelStart + idx];
}

// 8.获取二叉树跟结点的值
Status Root(SqBiTree T,CElemType *e){
    if (T[0] == Nil) return ERROR;
    *e = T[0];
    return OK;
}

// 9.给处于位置e的结点赋值
Status Assign(SqBiTree T, Position e, CElemType value) {
    // 深度为层数-1
    int depth = e.level - 1;
    // 左斜树序号  1 2 4 8 ...
    // 索引需要-1，0 1 3 7 ...，所以是powl(2, depth)-1
    int levelStart = (int)pow(2, depth) - 1;
    // order从1开始而不是0，所以-1
    int idx = e.order - 1;
    
    // 目标位置
    int i = levelStart + idx;
    // 重点1：叶子结点的双亲为空
    if (value != Nil && T[Parent(i)] == Nil) return ERROR;
    // 重点2：给双亲赋空值但是有叶子结点
    if (value == Nil && (T[LeftChild(i)] != Nil || T[LeftChild(i)+1] != Nil)) return ERROR;
    // 成功赋值
    T[i] = value;
    return OK;
}

// 10.获取e的双亲
CElemType ParentValue(SqBiTree T, CElemType e) {
    if (T[0] == Nil) return Nil; //空树
    for (int i = 1 ; i < MAX_TREE_SIZE; i++) {
        if (T[i] == e) {
            return T[Parent(i)]; //找到e
        }
    }
    return Nil; //没有找到
}

// 11.获取某个结点的左孩子
CElemType LeftChildValue(SqBiTree T, CElemType e) {
    if (T[0] == Nil) return Nil; //空树
    for (int i = 0 ; i < MAX_TREE_SIZE-1; i++) {
        if (T[i] == e) { //找到e
            return T[LeftChild(i)];
        }
    }
    return Nil; //没有找到
}

// 12.获取某个结点的右孩子
CElemType RightChild(SqBiTree T,CElemType e){
    if (T[0] == Nil) return Nil; //空树
    for (int i = 0 ; i < MAX_TREE_SIZE-1; i++) {
        if (T[i] == e) { //找到e
            return T[LeftChild(i)+1];
        }
    }
    return Nil; //没有找到
}

// 13.获取结点的左兄弟，e值必须是右孩子才有左兄弟
CElemType LeftSibling(SqBiTree T, CElemType e) {
    if (T[0] == Nil) return Nil; //空树
    for (int i=1; i <= MAX_TREE_SIZE-1; i++) // 头结点没有左兄弟，从1开始
        if (T[i]==e && i%2==0) return T[i-1]; // 找到e且其序号为偶数(是右孩子)
    return Nil; //没有找到
}

// 14.获取结点的右兄弟，e值必须是左孩子才有右兄弟
CElemType RightSibling(SqBiTree T, CElemType e) {
    if (T[0] == Nil) return Nil; //空树
    for (int i=1; i <= MAX_TREE_SIZE-1; i++) // 头结点没有左兄弟，从1开始
        if (T[i]==e && i%2==1) return T[i+1]; // 找到e且其序号为奇数(是左孩子)
    return Nil; //没有找到
}

2.1.3 遍历

// 1.层序遍历(存储就是层序的)
void LevelOrderTraverse(SqBiTree T){
    int i = MAX_TREE_SIZE - 1;
    for (; i>=0 && T[i] == Nil; i--);// 最后一个叶子结点
    for (int j = 0; j <= i; j++) //从根结点起，按层序遍历二叉树
        if (T[j] != Nil) //只遍历非空结点
            visit(T[j]);
    printf("\n");
}

// 2.前序遍历二叉树
void PreTraverse(SqBiTree T, int i){
    //打印结点数据
    visit(T[i]);
    //遍历左子树
    if (T[LeftChild(i)] != Nil) PreTraverse(T, LeftChild(i));
    //遍历右子树
    if (T[LeftChild(i)+1] != Nil) PreTraverse(T, LeftChild(i)+1);
}

Status PreOrderTraverse(SqBiTree T) {
    if (T[0] != Nil) //树不为空
        PreTraverse(T, 0); // 递归遍历
    printf("\n");
    return  OK;
}

// 3.中序遍历二叉树
void InTraverse(SqBiTree T, int i) {
    //遍历左子树
    if (T[LeftChild(i)] != Nil) InTraverse(T, LeftChild(i));
    //打印结点数据
    visit(T[i]);
    //遍历右子树
    if (T[LeftChild(i)+1] != Nil) InTraverse(T, LeftChild(i)+1);
}

Status InOrderTraverse(SqBiTree T) {
    if (T[0] != Nil) //树不为空
        InTraverse(T, 0); // 递归遍历
    printf("\n");
    return OK;
}

// 4.后序遍历
void PostTraverse(SqBiTree T,int i) {
    //遍历左子树
    if (T[LeftChild(i)] != Nil) PostTraverse(T, LeftChild(i));
    //遍历右子树
    if (T[LeftChild(i)+1] != Nil) PostTraverse(T, LeftChild(i)+1);
    //打印结点数据
    visit(T[i]);
}

Status PostOrderTraverse(SqBiTree T) {
    if (T[0] != Nil) //树不为空
        PostTraverse(T,0);
    printf("\n");
    return OK;
}

2.1.4 检验

int main(int argc, const char * argv[]) {
    printf("二叉树顺序存储结构实现!\n");
    
    Status iStatus;
    Position p;
    CElemType e;
    SqBiTree T;
    /*
            1       -->1
       2        3   -->2
     4    5   6   7 -->3
    8 9 10          -->4
    1 2 3 4 5 6 7 8 9 10 Nil Nil Nil
    */
    InitBiTree(T);
    CreateBiTree(T);
    printf("建立二叉树后，树空否？%d (1:是 0:否) \n",BiTreeEmpty(T));
    printf("树的深度 = %d\n",BiTreeDepth(T));
    
    p.level = 3;
    p.order = 2;
    e = Value(T, p);
    printf("第%d层第%d个结点的值: %d\n",p.level,p.order,e);
    
    iStatus = Root(T, &e);
    if (iStatus) {
        printf("二叉树的根为:%d\n",e);
    } else {
        printf("树为空,无根!\n");
    }
  
    //向树中3层第2个结点位置上结点赋值99
    e = 99;
    Assign(T, p, e);
    
    //获取树中3层第2个结点位置结点的值是多少:
    e = Value(T,p);
    printf("第%d层第%d个结点的值: %d\n",p.level,p.order,e);
    
    //找到e这个结点的双亲;
    printf("结点%d的双亲为: %d ", e, ParentValue(T, e));
    //找到e这个结点的左右孩子;
    printf("左右孩子分别为: %d, %d\n", LeftChildValue(T, e), RightChild(T, e));
    //找到e这个结点的左右兄弟;
    printf("结点%d的左右兄弟: %d, %d\n", e, LeftSibling(T, e), RightSibling(T, e));
    
    // 还原
    Assign(T, p, 5);
    
    // 开始遍历
    printf("二叉树T层序遍历:");
    LevelOrderTraverse(T);
    printf("二叉树T先序遍历:");
    PreOrderTraverse(T);
    printf("二叉树T中序遍历:");
    InOrderTraverse(T);
    printf("二叉树T后序遍历:");
    PostOrderTraverse(T);
    return 0;
}
// 输出
二叉树顺序存储结构实现!
1 2 3 4 5 6 7 8 9 10 
建立二叉树后，树空否？0 (1:是 0:否) 
树的深度 = 4
第3层第2个结点的值: 5
二叉树的根为:1
第3层第2个结点的值: 99
结点99的双亲为: 2 左右孩子分别为: 10, 0
结点99的左右兄弟: 4, 0
二叉树T层序遍历:1 2 3 4 5 6 7 8 9 10 
二叉树T先序遍历:1 2 4 8 9 5 10 3 6 7 
二叉树T中序遍历:8 4 9 2 10 5 1 6 3 7 
二叉树T后序遍历:8 9 4 10 5 2 6 7 3 1 

2.2 链式存储

2.2.1 结构定义

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

/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;

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

为了方便后续创建二叉树：

// 全局变量
#define MAXSIZE 100 //存储空间初始分配量
typedef char String[MAXSIZE]; /*  0号单元存放串的长度 */
String str;
Status StrAssign(String T, char *chars) {
    size_t length = strlen(chars);
    if (length > MAXSIZE) return ERROR;
    T[0] = length;
    for (int i = 1; i <= T[0]; i++)
        T[i] = *(chars+i-1);
    return OK;
}

2.2.2 基础操作

// 1.打印数据
Status visit(CElemType e) {
    printf("%c ",e);
    return OK;
}

// 2.构造空二叉树T
Status InitBiTree(BiTree *T) {
    *T = NULL;
    return OK;
}

// 3.销毁二叉树
void DestroyBiTree(BiTree *T) {
    if (*T) {
        // 有左孩子
        if ((*T)->lchild)
            DestroyBiTree(&(*T)->lchild); // 销毁左孩子子树
        // 有右孩子
        if ((*T)->rchild)
            DestroyBiTree(&(*T)->rchild); // 销毁右孩子子树
        free(*T); // 释放结点
        *T = NULL; // 指针赋空
    }
}

// 4.清空树和销毁代码完全一样
#define ClearBiTree DestroyBiTree

// 5.创建二叉树
int createIndex = 1;
void CreateBiTree(BiTree *T) {
    CElemType ch = str[createIndex++]; // 获取字符
    if (ch == Nil) { // 判断当前字符是否为空
        *T = NULL;
    } else {
        //创建新的结点
        *T = (BiTree)malloc(sizeof(BiTNode));
        //是否创建成功
        if (!*T) {
            exit(OVERFLOW);
        }
        (*T)->data = ch; // 生成根结点
        CreateBiTree(&(*T)->lchild); // 构造左子树
        CreateBiTree(&(*T)->rchild); // 构造右子树
    }
}

// 6.二叉树T是否为空
Status BiTreeEmpty(BiTree T) {
    if (T)
        return FALSE;
    else
        return TRUE;
}

// 7.二叉树T的深度
int BiTreeDepth(BiTree T) {
    if (!T) return 0;
    int i, j;
    i = T->lchild ? BiTreeDepth(T->lchild) : 0; // 计算左孩子的深度
    j = T->rchild ? BiTreeDepth(T->rchild) : 0; // 计算右孩子的深度
    return i > j ? i+1 : j+1; // 比较i和j
}

// 8.二叉树T的根
CElemType Root(BiTree T) {
    if (BiTreeEmpty(T)) return Nil;
    return T->data;
}

// 9.返回p所指向的结点值
CElemType Value(BiTree p) {
    return p->data;
}

// 10.给p所指结点赋值为value
void Assign(BiTree p, CElemType value) {
    p->data = value;
}

2.2.3 遍历

// 1.前序递归遍历T
void PreOrderTraverse(BiTree T) {
    if (!T) return;
    printf("%c", T->data); // 显示结点数据
    PreOrderTraverse(T->lchild); // 遍历左子树
    PreOrderTraverse(T->rchild); // 遍历右子树
}

// 2.中序递归遍历T
void InOrderTraverse(BiTree T) {
    if (!T) return;
    InOrderTraverse(T->lchild); // 遍历左子树
    printf("%c", T->data); // 显示结点数据
    InOrderTraverse(T->rchild); // 遍历右子树
}

// 3.后序递归遍历T
void PostOrderTraverse(BiTree T) {
    if (!T) return;
    PostOrderTraverse(T->lchild); // 遍历左子树
    PostOrderTraverse(T->rchild); // 遍历右子树
    printf("%c", T->data); // 显示结点数据
}

2.2.4 检验

int main(int argc, const char * argv[]) {
    printf("二叉树链式存储结构实现!\n");
    
    BiTree T;
    CElemType e1;
    /*
                A
           B        C
         D   E     F   G
        H # # #   I # # J
       # K       # #   # #
        # #
     ABDH#K###E##CFI###G#J##
     */
    InitBiTree(&T);
    StrAssign(str,"ABDH#K###E##CFI###G#J##");
    CreateBiTree(&T);
    printf("二叉树是否为空: %d (1:是 0:否)\n树的深度: %d\n", BiTreeEmpty(T), BiTreeDepth(T));
    e1 = Root(T);
    printf("二叉树的根为: %c\n",e1);
    printf("前序遍历二叉树:");
    PreOrderTraverse(T);
    printf("\n中序遍历二叉树:");
    InOrderTraverse(T);
    printf("\n后序遍历二叉树:");
    PostOrderTraverse(T);
    printf("\n");
    return 0;
}

// 输出
二叉树链式存储结构实现!
二叉树是否为空: 0 (1:是 0:否)
树的深度: 5
二叉树的根为: A
前序遍历二叉树:ABDHKECFIGJ
中序遍历二叉树:HKDBEAIFCGJ
后序遍历二叉树:KHDEBIFJGCA

2.2.5 非递归遍历

// 1.前序循环遍历T
void LoopPreOrderTraverse(BiTree T) {
    if (!T) return;
    // 这里偷懒知道树高5
    int top = -1;
    BiTNode **stack = (BiTNode **)malloc(sizeof(BiTNode*) * 5);
    BiTNode *cur = T;
    while (cur || top > -1){
        while (cur) {
            stack[++top] = cur;
            printf("%c", cur->data); // 显示结点数据
            cur = cur->lchild;
        }
        if (top > -1) {
            cur = stack[top];
            --top;
            cur = cur->rchild;
        }
    }
    free(stack);
}

// 2.前序循环遍历T
void LoopInOrderTraverse(BiTree T) {
    if (!T) return;
    // 这里偷懒知道树高5
    int top = -1;
    BiTNode **stack = (BiTNode **)malloc(sizeof(BiTNode*) * 5);
    BiTNode *cur = T;
    while (cur || top > -1){
        while (cur) {
            stack[++top] = cur;
            cur = cur->lchild;
        }
        if (top > -1) {
            cur = stack[top];
            printf("%c", cur->data); // 显示结点数据
            --top;
            cur = cur->rchild;
        }
    }
    free(stack);
}

// 3.前序循环遍历T
void LoopPostOrderTraverse(BiTree T) {
    if (!T) return;
    // 这里偷懒知道树高5
    int top = -1;
    BiTNode **stack = (BiTNode **)malloc(sizeof(BiTNode*) * 5);
    BiTNode *cur = T, *recent = NULL;
    while (cur || top > -1) {
        if (cur) { //走到最左边
            stack[++top] = cur;
            cur = cur->lchild;
        } else {
            cur = stack[top];
            if (cur->rchild && cur->rchild != recent) //右子树存在，未被访问
                cur = cur->rchild;
            else {
                --top;
                printf("%c", cur->data); // 显示结点数据
                recent = cur; //记录最近访问过的节点
                cur = NULL; //节点访问完后，重置p指针
            }
        }
    }
    free(stack);
}

// 检验
int main(int argc, const char * argv[]) {
    BiTree T;
    CElemType e1;
    /*
                A
           B        C
         D   E     F   G
        H # # #   I # # J
       # K       # #   # #
        # #
     ABDH#K###E##CFI###G#J##
     */
    
    InitBiTree(&T);
    StrAssign(str,"ABDH#K###E##CFI###G#J##");
    CreateBiTree(&T);
    
    printf("递归前序遍历二叉树:");
    PreOrderTraverse(T);
    printf("\n递归中序遍历二叉树:");
    InOrderTraverse(T);
    printf("\n递归后序遍历二叉树:");
    PostOrderTraverse(T);
    
    printf("\n循环前序遍历二叉树:");
    LoopPreOrderTraverse(T);
    printf("\n循环中序遍历二叉树:");
    LoopInOrderTraverse(T);
    printf("\n循环后序遍历二叉树:");
    LoopPostOrderTraverse(T);
  
    printf("\n");
    return 0;
}
// 输出
递归前序遍历二叉树:ABDHKECFIGJ
递归中序遍历二叉树:HKDBEAIFCGJ
递归后序遍历二叉树:KHDEBIFJGCA
循环前序遍历二叉树:ABDHKECFIGJ
循环中序遍历二叉树:HKDBEAIFCGJ
循环后序遍历二叉树:KHDEBIFJGCA