发布日期: 2023-12-14

树和二叉树

本节，是数据结构的第一部分重难点树的知识梳理。其涉及到的知识体系极其繁杂，同时会常常与前面的数据结构有所联系。

树

树——概述

我们首先需要了解，树这个玩意到底是个啥？

我们在学习前面的数据结构时，往往其结构都是 线性的 ，这意味着其结构中的每一个元素都只有一个前驱，也只有一个后继。

树与之不同，树中的每个节点（除根结点外）只有一个前驱，但其可以包含多个后继，这就是其与此前的数据结构在根本上的区别。

树——常用术语

由于树的结构复杂性，我们需要先做出一些术语上的约定，以防止此后我们在进行描述时，产生歧义。

树的根：一棵树中的第一个元素，它没有前驱，只有后继
树的结点：包含一个元素，以及若干个指向其子树（后继）的分支；
结点的度：一个节点所连接的子树的数目；
树的度：这棵树里面所有结点度的最大值；
叶子结点 ：没有子树的结点；
分支节点：有子树的结点；
孩子结点 ：一个结点的两个子树的根；
双亲结点 ：一个结点的前驱结点；
兄弟结点 ：两个具有相同双亲结点的结点互相称为兄弟；
堂兄弟结点 ：两个双亲结点在同一层的结点互相称为堂兄弟；
结点的层次：从根结点到该结点的路径长度+1；
树的深度：树中所有叶子结点的层次的最大值；

相信看到这一堆名词已经能让一部分读者感到头疼了…
别着急，我们先从最简单的树——二叉树讲起。

二叉树

二叉树 是最简单的树，其特殊性在于规定了每个结点最多只能有两棵子树，这这两棵子树被称为 左 / 右子树 。

二叉树的性质

二叉树的形式非常特殊，因此在这里我们浅谈一下其具体性质：

在二叉树的第 i 层上至多有 2^i-1 个结点
深度为 k 的二叉树上至多有 2^k - 1 个结点
注：考虑结点最多的情况，即 2⁰ + 2¹ + … + 2^k-1 = 2^k - 1
对任意的一棵二叉树，若其度为0的结点（叶子结点）的数目为N，度为2的结点的数目为N₂，则N = N₂ + 1
注：这里我们不给严谨证明，我们只给一个思路，即在任意一棵二叉树中，多一个度为2的结点就必定意味着多出了一个叶子节点，而一棵二叉树在只有根结点的时候叶子节点数量为1，因此可以推出上式

在叙述第四个性质之前，我们需要先了解两类特殊的二叉树：

满二叉树：深度为k，且含有 2^k - 1 个结点的二叉树
顾名思义，这个二叉树里面除了叶子结点之外，所有的结点的度都是2，因此得名
完全二叉树：树中所含的n个结点和满二叉树编号为 1 -> n 的结点一一对应。
啥意思呢，这里得给两个图来解释一下：

满二叉树

完全二叉树

好的，了解完这两种特殊的二叉树，我们接下来回到此前性质的学习中：

具有n个结点的 完全二叉树 的深度为：[log₂n] +1
证：我们设完全二叉树的深度 k ；由于第二条性质的存在，得到 2^k-1 < 2^k ，对该式进行化简，即可得到 k-1 < [log₂n] < k ，同时k又只能是整数，因此得到这个性质。
对于任意的 完全二叉树 ，我们对其进行从上至下，从左至右的编号（就类似上图的编号方式），可以得到如下性质：
- 若结点编号 i = 1 ，则这个结点是其根结点，否则编号为 [i/2] 的结点就是其双亲结点。
- 对于任意结点，如果对于其编号 i 满足 2i > n ，则该结点没有左孩子。否则，编号为 2i 的结点是其左孩子。
- 对于任意结点，如果对于其编号 i 满足 2i +1 > n ，则该结点没有右孩子。否则，编号为 2i + 1 的结点是其右孩子。

关于二叉树的性质，大体就这么些，其中大部分的性质是比较容易就能推出来的，最后两个关于完全二叉树的性质也可以在读者对于完全二叉树的理解加深之后轻易写出。 ~~（实在不行咱画一个图看一眼，举例嘛，不寒碜）~~

二叉树的存储

说了挺多，现在咱来看看这东西在计算机里面该怎么实现

二叉树的顺序存储

相信挺多读者一看顺序存储应该挺诧异，觉着不是很好实现。确实，顺序存储（即利用数组的方式存储二叉树）仅比较适用于完全二叉树，这是因为其标号是有规律可循的（详见上面的最后一条性质）。

完全二叉树的顺序存储

如果想在非完全二叉树的基础上进行顺序存储，那我们为了保持结构以及访问的便利性，只能先创建一个与之相对的完全二叉树的数组，而后将其不存在的结点值赋值为0。

非完全二叉树的顺序存储

读者应该看出来了，如果这样存储二叉树，会产生极大的内存浪费，因为需要占用很大的空间来存储中间的0元素，这是得不偿失的。

二叉树的链式存储

二叉链表

非常自然地，加入二叉树的每一个结点都最多有两个孩子，那我们自然可以利用一个链表结构，只不过这个链表中的每个结点都有两个指针，分别指向其左孩子以及右孩子。

typedef struct BiTNode{
    ElemType data; //节点内存储的内容
    BiTNode *lchild, *rchild; //分别指向其左孩子与右孩子
}*BiTree;

三叉链表

有二叉链表，我们又想了，能不能达成一个通过子节点能够找到它双亲结点的结构呢？当然可以，无非就是加一个指针的事情：

typedef struct TriTNode{
    ElemType data;
    TriTNode *lchild, *rchild;
    TriTNode *parent; //新增一个指向双亲结点的指针，但是维护起来会更费时
};

三叉链表的存储比二叉链表更加清晰一些，但是维护起来明显更加费时，这里的选择可以由读者自行决定，本文中大部分的代码演示会通过二叉链表来进行。

二叉树的遍历

我们说完了这玩意该怎么在计算机里面实现存储，现在就需要说一说它的一些基础操作了。

我们首先需要明确遍历的原则，即二叉树中的每个结点均 被访问且仅被访问一次 。

对于二叉树而言，有两种遍历思路可选：

深度优先遍历：先进行左（右）子树的遍历，待这一过程完毕后，再遍历右（左）子树。
广度优先遍历：从上至下按照树的层次一层层遍历。

我们从广度优先的先左后右的遍历说起。

先左后右的深度优先遍历算法

这种思路又分为三种子思路，即我的根结点应该在什么时候进行访问：

先序遍历：即先访问根结点，再依次访问左子树，右子树
中序遍历：即先访问左子树，再访问根结点，最后访问右子树
后序遍历：即先访问左子树，右子树，最后访问根结点

这里额外说一句，构建二叉树的时候，我们是可以通过不同的遍历方式作为依据的，具体来说，我们可以通过中序遍历以及其余任意一种遍历方式来唯一确定一棵二叉树。

递归遍历算法

由于二叉树的特殊性，我们很容易想到递归的遍历方法：

//先序遍历
void PreOrder(BiTree T){
    if(T){
        //T不为空
        printf("%d", T->data); //打印当前节点的值
        PreOrder(T->lchild);
        PreOrder(T->rchild); //分别先后利用递归遍历左子树与右子树
    }
}

//中序遍历
void InOrder(BiTree T){
    if(T){
        //T不为空
        InOrder(T->lchild); //先遍历左子树
        printf("%d", T->data); //打印当前节点的值
        InOrder(T->rchild); //最后遍历右子树
    }
}

//后序遍历
void PostOrder(BiTree T){
    if(T){
        //T不为空
        PostOrder(T->lchild); //先遍历左子树
        PostOrder(T->rchild); //再遍历右子树
        printf("%d", T->data); //最后打印当前节点的值
    }
}

这种遍历算法利用递归，写起来简单明了，但存在效率问题。
相信写C语言递归的读者经常遇到递归深度过深的问题，我们试想一下，如果有一棵树，其深度达到100，那几乎不用考虑，这种算法肯定直接报错退出。

这也就需要引出我们的第二种算法。

非递归遍历算法

在这种算法中，我们使用此前我们学过的栈这种结构来对树进行遍历。

我们先把思想搞明白，然后再上代码，以中序遍历为例：

这种算法的思路为：

我们先从根结点一直向左下找，途中只要遇到一个结点，我们就将其入栈；
直到我们找到了NULL结点，这说明它上一个结点是整棵树最靠左下的结点了，这时我们将其出栈，并访问它，而后继续访问其右子树；
访问其右子树的过程与上述过程相同，直到整棵右子树被访问完毕。
此后，我们可以继续出栈一个结点，重复上述过程。
当栈空时，整棵二叉树就被我们遍历完毕了

上面的文字描述比较晦涩难懂，这里给出一棵具体的树作为例子：

实例树

我们将遍历过程写一遍：

对于这一棵二叉树，我们单独设置一个栈，初始为空。
从根结点找到最左下的结点，路径上所有的结点均入栈。即 1入栈、 2入栈、 4入栈；
- 现在栈中的元素：1, 2, 4;
到达4的左孩子，发现是NULL，因此此时出栈一个元素（4），访问它，并遍历它的右子树。
我们发现4的右子树是NULL，因此直接退出遍历，此时再次检测栈中是否有元素，发现栈不空，再次出栈一个元素（2），访问它，并遍历它的右子树。
- 此时根结点是5，同样的向左下找，路径上所有的结点均入栈。即5入栈、 6入栈；
  - 此时栈中的元素：1, 5, 6;
- 到达6的左子树，发现是NULL，因此此时出栈一个元素（6），访问它，遍历它的右子树（NULL）；
- 检测栈中是否有元素，发现栈不空，出栈一个元素（5），访问它，遍历其右子树
- 此时根结点是7，向左下找，路径上元素入栈。即7入栈；
  - 此时栈中元素：1, 7;
- 到达7的左孩子，发现是NULL，出栈一个元素（7），访问它，遍历其右子树（NULL）；
此时再次检测栈中元素，栈非空，出栈一个元素（1），访问它，遍历其右子树；
3入栈；
- 此时栈中元素：3;
3的左孩子是NULL，3出栈，同时遍历3的右子树（NULL）；
检测栈中元素，栈空，退出算法

上述过程就是这种算法进行遍历的方式，请读者务必理解，下面我们给出具体代码：

//中序遍历——非递归算法
void InOrder(BiTree b){
    BiTNode *stack = (BiTNode*)malloc(sizeof(BiTNode)*m); //m根据你的树的深度来决定，足够大就行
    BiTNode *p;
    int top = 0; //来表示栈顶的位置
    p = b;
    do{
        while(p!=NULL){
            top++;
            stack[top] = p; //p入栈
            p = p->lchild; //p指向其左孩子
        } //这个循环在p指向的左孩子是NULL的时候会停止
        if(top > 0){
            //判断栈不空
            p = stack[top];
            top--; //出栈一个元素
            printf("%d", p->data); //访问刚刚出栈的元素（打印）
            p = p->rchild; //继续扫描右子树，开始下一层循环
        }
    }while(p!=NULL || top != 0) //当 p不空或者栈不空时，继续该循环
    //额外提一嘴，这里最外层的do_while循环的停止条件是p为NULL，并且栈空，此时才会退出循环
}

在读者能够看明白上述代码的时候，我们可以继续将先序遍历以及后序遍历的非递归算法给出。

下面是先序遍历的算法，其思路为：

检测栈中是否为空
双亲结点出栈访问；
检测该结点有没有左右孩子，按照先右后左的顺序入栈；
回到第二步继续循环，直到栈空，算法结束

//先序遍历——非递归算法
void PreOrder(BiTree b){
  BiTNode* stack = (BiTNode*)malloc(sizeof(BiTNode)*m); //类似的，m可以由读者自行决定，够大就可以
  BiTNode* p;
  int top = 0;
  if(b!=NULL){
    //b不空，开始遍历
    stack[++top] = b; //根结点入栈
    while(top>0){
      //当栈不空时，循环
      p = stack[top]; //先将一个结点出栈（先序遍历的特点）
      top--;
      printf("%d", p->data);
      if(p->rchild){
        //p有右孩子
        top++;
        stack[top] = p->rchild; //p的右孩子先入栈
      }
      if(p->lchild){
        //p有左孩子
        top++;
        stack[top] = p->lchild; //p的左孩子后入栈
      }
    } //当栈空时，所有的结点均被访问完毕
  }
}

这个先序遍历算法有一点需要额外说明一下：在访问完当前结点，随后入栈当前结点的左右孩子时，为了保证程序能 先访问左孩子，再访问右孩子 ，我们需要 先将右孩子入栈，随后再将左孩子入栈 。这是由栈的后进先出原则决定的。

最后是后序遍历，这是三种遍历中最难写的一种。

这玩意涉及到了一个重复访问的问题：即我们先找到左节点，随后返回其双亲结点，再访问双亲结点的子树，再返回双亲结点，这就产生了问题：
我们如何判断返回双亲结点时，这是从左子树返回过来的，还是从右子树返回过来的？

因此，很遗憾的，我们可能又需要写一个辅助栈，来额外设置一个标记位，便于我们判断返回情况。

还是先给出大体思路：

沿着根结点一直向左下走，直到走到NULL，途中所有的结点入栈，同时辅助栈相应的位置添加标记0；
走到NULL后，检测当前栈顶结点，并将其对应标记位设置为1，开始访问其右子树；
右子树的访问规则与第一步相同；
当我们访问完右子树再次返回这个结点时（即总有一次我们检测栈顶元素，发现这个结点的标记位已经被我们之前置成1了），我们将其出栈，并打印。

//后序遍历——非递归写法
void PostOrder(BiTree b){
  BiTNode* stack = (BiTNode*) malloc(sizeof(BiTNode)*m);
  BiTNode* p = b;
  int* sub = (int*) malloc(sizeof(int)*m); //辅助栈
  int top; //由于辅助栈的栈顶与主栈栈顶同步，因此只需要设置一个表示栈顶的变量即可
  do{
    while(p!=NULL){
      top++;
      stack[top] = p;
      tag[top] = 0; //第一次入栈时，将其标志位置为0
      p = p->lchild;
    } //向左下一直找到NULL
    while((top>0) && sub[top] == 1){
      //如果当前栈顶元素的左右子树都被访问过了
      printf("%d", stack[top]->data);
      top--; //出栈
    }
    if((top>0) && sub[top] == 0){
      //当前栈顶元素的右子树还没被访问过
      p = p->rchild; //把p指向右子树，用于下一次的循环
      tag[top] = 1; //将其标志位置成1
    }
  }while(p!=NULL || top!=0);
  //当p为NULL且栈空时才停止循环
}

按层次遍历的广度优先算法

相对于深度优先算法而言，广度优先的算法要显得友好许多。

我们采用队列这种数据结构来遍历这棵二叉树，其思路为：

创建一个队列；
先将二叉树的根结点入队；
对任意一个队列中的结点，我们先将其出队并打印，同时将其左孩子和右孩子入队列。
依照上述过程循环，直到队列空为止

读者可以依照上面给过的二叉树的例子试着手过一遍这种算法，写过一遍的理解总是要比直接看代码要清晰许多，下面我们给出代码：

//广度优先遍历
void TransLevel(BiTree b){
  struct Queue{
    BiTree* vec = (BiTree*) malloc(sizeof(BiTree)*m); //一个道理，m够大就行
    int front, rear; //指示队列头尾的变量
  }q;
  BiTree* temp;
  q.front = 0;
  q.rear = 0;
  if(b == NULL){
    //树空，则直接返回
    return;
  }else{
    //否则，树根入队
    q.vec[q.rear] = b;
    q.rear++;
  }
  while(q.front!=q.rear){
    //当队列不空时，循环
    temp = q.vec[q.front];
    q.front++;
    printf("%d", temp->data); //队头的元素出队并打印
    if(temp->lchild!=NULL){
      //出队的元素有左孩子
      q.vec[q.rear] = temp->lchild;
      q.rear++;
    }
    if(temp->rchild!=NULL){
      //出队的元素有右孩子
      q.vec[q.rear] = temp->rchild;
      q.rear++;
    }
  }
}

好的，二叉树的遍历至此，就差不多讲完了。这部分难度不小，读者可以缓口气。

之所以这么重视这一部分，并且花费很大的篇幅来讲解，是为了下一个部分，二叉树的基础应用来做铺垫，没有二叉树的遍历，我们没法进入下一部分。

注：如果深度遍历的非递归算法读者未能理解，可以暂时跳过，递归算法先用着嘛，不寒碜。

二叉树的基础应用

统计叶子结点的个数

这应用在咱说完遍历算法之后应该不算很难了，我们只需要在算法中加入一个计数器，再把打印那一步改成一个判断语句，即如果这个结点没有左右孩子，则计数器+1即可。

这里就不写代码了，读者照着上面的代码自行改一改就好。

求二叉树的深度

求深度这一算法类似于后序遍历，我们根据二叉树的定义，应该能看出来树的深度等于其左子树与右子树深度的最大值+1；因此，这算法用递归相当好写：

int Depth(BiTree T){
  int depthval, depthleft, depthright;
  if(T == NULL){
    //树空，返回0
    return 0;
  }else{
    depthleft = Depth(T->lchild);
    depthright = Depth(T->rchild);
    depthval = 1 + (depthleft>depthright?depthleft:depthright);
  }
  return depthval;
}

线索二叉树

线索二叉树这玩意其实笔者没找到非常具体的应用场景，但是无可奈何这东西确实在数据结构的书上有，这里稍微提一嘴

线索二叉树 是为了提高遍历速度而建立的一种类似于链表的结构，因此也被称为线索链表，主要用于深度遍历，也分为以下三类：

先序线索链表
中序线索链表
后序线索链表

其与二叉树的具体区别在于，二叉树中的空节点就是空节点，但线索二叉树并不，它将所有的空结点连接上了它遍历时的前驱与后继。

但这里又产生了一个问题，即我们如何区分一个结点的左右指针指向的是孩子还是线索呢？
对喽，引入了两个标记位，它们一个用于标记左指针，另一个用于标记右指针，当标记位为0时，它正常指向左 / 右孩子，但当标记位为1时，则代表着它指向相应遍历顺序中的前驱与后继。

这里举一例：

线索二叉树例图

我们还是拿这棵树来举个例子，其中序遍历时的顺序为：

4, 2, 6, 5, 7, 1, 3

正常而言，6没有左右孩子，其两个指针都是NULL，但在线索二叉树中，6这个结点的两个标记位都为1，即其左右指针均指向其前驱与后继，在这里即6的左指针指向了2，右指针指向了5

线索链表的具体结点结构为：

typedef struct BiThrNode{
  TElemType data;
  BiThrNode* lchild, *rchild;
  int Ltag, Rtag; //新增加的左右标记位
}

线索二叉树的相关内容我们就写这么些。

树——回归

前面的二叉树是树的一种最基础的表现形式，现在让我们回到树，继续谈树的一些存储和应用。

树的存储

与二叉树相似，树的表示方式也有很多种，但其复杂性在于一个结点可能有多个孩子。这里介绍几种常见的存储方式。

孩子链表表示法

我们可以把每一个结点的孩子结点排列起来，以单链表作为存储结构。这也就代表着，一棵树有n个结点，也就有n个孩子链表。

又由于这n个头指针又形成了一个线性表，因此我们可以采取线性存储结构。

孩子链表表示法

在这种表示方式中，显然我们需要定义两种结点类型：

typedef struct CTNode{
  int child; //表示这个孩子所在的下标
  CTNode* next; //指向下一个孩子
}; //孩子结点

typedef struct PTNode{
  ElemType data; //结点内容
  CTNode* firstchild; //指向第一个孩子
}; //双亲结点

如果我们希望在双亲结点中能够直接找到自己的双亲结点，我们只需要在PTNode中增加一个变量即可：

带双亲的孩子链表

typedef struct PTNode{
  ElemType data; //结点内容
  int parent; //存储双亲结点的下标
  CTNode* firstchild; //指向第一个孩子
}; //双亲结点

树的二叉链表表示法（孩子-兄弟表示法）

前面铺垫了半天二叉树，这里肯定得用一下子。

我们如果想将一棵多叉树转换成一棵二叉树，应该怎么做呢？

比较通用的做法是将二叉树的左指针指向自己的第一个孩子，右指针指向自己下一个兄弟。

typedef struct CSNode{
  ElemType data; //结点内容
  CSNode *firstchild, *nextsibling; //分别存储自己的第一个孩子和下一个兄弟
};

举个例子，上图的树，我们如果利用这种方式进行存储：

树的二叉树存储

树的遍历

类似于二叉树，树也有不同的遍历法：

先根遍历（对应二叉树的先序遍历）：先访问根根结点，然后依次访问各棵子树
后根遍历（对应二叉树的中序遍历）：先依次访问各棵子树，再访问根结点
按层次遍历：类似于二叉树的广度优先遍历

这里先根遍历与对应二叉树的先序遍历对应；但后根遍历是与其对应二叉树的中序遍历对应的，举个例子：

我们还是以上面这棵树为例：

后根遍历的顺序：
B G E F C D A

我们再用之前讲的中序遍历二叉树顺序对上面转化完的二叉树来一遍：
B G E F C D A

可以发现完全一致。

树的应用

树的深度

树的深度写起来其实跟求二叉树的深度那个算法差别不大，我们需要先将树转化为二叉树（即孩子-兄弟表示），此后对这个二叉树求深，但需要额外考虑到走兄弟这条道路时深度不变。

//求树的深度
int TreeDepth(CSTree T){
  int h1, h2;
  if(T == NULL){
    树为空，则返回0
    return 0;
  }else{
    h1 = TreeDepth(T->firstchild)+1; //走左侧第一个孩子时，深度+1；
    h2 = TreeDepth(T->nextsibling); //走右侧兄弟结点时，深度不变
    return h1>h2?h1:h2; //返回其中最大的那个
  }
}