数据结构：树

⚠ 转载请注明出处：作者：ZobinHuang，更新日期：Mar.5 2021

    本作品由 ZobinHuang 采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可，在进行使用或分享前请查看权限要求。若发现侵权行为，会采取法律手段维护作者正当合法权益，谢谢配合。

1. 树的一些术语

(1) 结点

    ① 根结点：没有前驱，仅有后继的树结点
    ② 分支结点：有且仅有一个前驱，可以有多个后继的树结点
    ③ 叶结点：没有前驱，仅有后继的树结点

(2) 度与深度

    ① 结点的度：该结点拥有的子树数目
    ② 树的度：最大的结点度
    ③ 深度：最大的层次数

2. 二叉树 (Binary Tree)

(1) 定义（递归定义）

    或为空（空二叉树，结点数为0），或由根的两棵互不相交的左、右子树组成，其左右子树又分别是二叉树。

(2) 性质

    (a) 在第i层上最多有 `2^(i-1)` 个结点（i从1开始）

    (b) 深度为 `k` 的二叉树，最多有 `\sum_{i=1}^{k}2^k = (a_1(1-q^n))/(1-q) = (2^0(1-2^k))/(1-2) = 2^k-1` 个结点

    (c) 设叶结点的个数为 `n_0`，度为2的结点个数为 `n_2`，则存在关系： `n_0 = n_2 + 1`，即叶结点比度为2的结点的个数多一个。证明如下：

    设叶结点的个数为 `n_0`，有一个孩子的结点的个数为 `n_1`，有两个孩子的结点的个数为 `n_2`，结点总个数为 `n`，则可以得到条件：
        `n = n_0 + n_1 + n_2`
        `n = 分支的个数 + 1`
    设分支个数为 `B`，则可以得到条件：
        `B = 2n_2 + n_1`
    综合上述三式，可以得到：
        `n = 2n_2 + n_1 + 1 = n_0 + n_1 + n_2`
        故 `n_0 = n_2 + 1`

    (d) 满二叉树 (full binary tree)和半满二叉树 (half-full binary tree)：

    满二叉树：所有的结点要么有两个孩子，要么一个也没有。所有的叶结点都位于同一层。

    半满二叉树：深度为 `K` 的二叉树，`K－1` 层是满二叉树，`K` 层节点个数不足`2^(K－1)` 个。其中，完全二叉树是一种特殊的半满二叉树，这种半满二叉树最后一层节点从左至右依次排列，没有间断。

    (e) 具有n个节点的完全二叉树，深度为 `[\log_2n]+1`，其中 `[ ]` 是取整符号。且如果对结点数为 `n` 的完全二叉树自上而下，从左至右依次编号，如上图所示，则节点 `i` 的父结点为 `[i/2]`，且：
    如果 `2i\leqn`，则节点 `i` 的左后继是 `2i`；如果 `2i\geqn`，则 `i`无左后继；
    如果 `2i+1\leqn`，则结点 `i` 的右后继是 `2i+1`；如果 `2i+1\geqn`，则结点 `i`无左后继。

(3) 二叉树的存储

    (a) 顺序存储结构：所有结点依次存放在一块连续的内存空间中，将完全二叉树从上到下，从左到右编号后，结点号码可作为数组的下标，从而将完全二叉树顺序存储下来。基于上面讨论的性质(e)，当给出任意结点 `i`，则可知道它的父结点为 `[i/2]`，两个孩子分别为 `2i` 和 `2i＋1` （如果存在的话）。一般的二叉树相对于同样深度的完全二叉树，缺失了部分结点，在顺序存储时，这些位置要空出来。以维持结点编号之间的父子换算关系。顺序存储结构只适合存满二叉树和完全二叉树，对其他树的存储将会造成空间的浪费。具体的实现方法是用一维数组来实现。

    (b) 链式存储结构：如上图所示，也可以用链表实现二叉树，即二叉链表。

(4) 二叉树的遍历

(a) 基本概念

    二叉树的遍历即按某种次序访问树中每一个结点且每一个结点只访问一次。根据对根的访问顺序，可以有3种遍历方式：先序遍历（先根遍历），中序遍历（中根遍历），以及后序遍历（后根遍历），具体如下所示，忘记的时候可以自己推一推。

(b) 中序遍历算法的实现

    · 基本思路：从根x开始，
        1. 找到B，但不访问B
        2. 根据B找到A，访问A
        3. 回溯B，访问B
        4. 根据B找到C，访问C
        5. C访完了，回溯X

    · 实现法一：利用栈实现回溯

    利用栈实现的算法步骤：
        STEP 1. 树（子树）根入栈，不访问
        STEP 2. 左子树入栈，左子树的各子树根依次入栈即反复进行步骤1
        STEP 3. 当左子树为空时，出栈，访问根结点
        STEP 4. 根节点右子树入栈（新树入栈，到步骤1去遍历右子树）
        STEP 5. 当右子树为空时，出栈，访问（祖先）爷结点，将爷结点的右子树入栈（新树入栈，回到步骤1)

    实际上，如上图所示，根据上面的5个步骤，若结点 `A_1` 的左子树为空，结点 `A_1` 就会作为栈顶元素会被 ①出栈 并 ②访问，随后就会 ③前往结点 `A_1` 的右子树。而当结点 `A_1` 的右子树也为空时（即 `A_2` 不存在时），实际上对以 `A_1` 为根节点的子树的访问已经结束，需要回溯到 `A_1` 的父节点 `A_0`。结点 `A_1` 出栈后，此时栈中的栈顶实际上就变成了 `A_1` 的右子树根节点 `A_2` 的爷结点 `A_0`，因此接下来的操作是将栈顶元素（此时是 `A_0` ）①出栈 ②访问 ③前往右子树三步。此时我们发现规律，只要结点的左子树或者右子树不存在，对栈的操作都是 ①出栈 ②访问 ③前往右子树 三步，因此我们可以将上面的 STEP 3 和 STEP 5合并，变成：
        STEP 1. 树（子树）根入栈，不访问
        STEP 2. 左子树入栈，左子树的各子树根依次入栈即反复进行步骤1
        STEP 3. 当子树为空时，出栈，访问根结点
        STEP 4. 根节点右子树入栈（新树入栈，到步骤1去遍历右子树）
    根据上面的分析，下面我们来看看具体的实现方式：

p = tree->root;
while( !end_of(tree) ){
  if( p != NULL ){
    push(stack, p)
    p = p->Lchild;
  }
  else{
    p = pop(stack); //出栈
    process(p);     //访问
    p = p->Rchild;  //前往右子树
  }
}

    此时我们就剩下一个遗留问题，上面代码中的 end_of(tree) 该如何实现呢？即如何判断树已经被我们遍历完了呢？

    首先，是否能用 栈空 作为等价条件呢？若我们使用它作为结束条件，我们以上图的二叉树为例子，当结点A的左子树遍历完时，此时A会被 ①出栈，②访问，遍历指针p会 ③前往右子树（即结点K），此时栈为空。当重新回到循环进入条件时，栈空 的条件成立，循环退出。但是很明显，A的右子树全部都没有被访问到，因此 栈空 不能简单地作为退出循环的条件。
    若要 使用 栈空 作为判断条件，最简单的解决办法就是在初始化的时候在栈中就加入一个假的元素，即在遍历的过程中，栈底一直是有一个假元素存在的，这样在经历上面A被弹出的情况时，仍然可以继续循环将A的右子树遍历完，最后在弹出K时，紧随其后的就会把这个假元素也弹出来（K的右子树为空），然后再退出循环。
    我们也可以使用另一种更简单的方法，基于我们上面的讨论我们发现，当A被弹出栈时，虽然栈已经为空，但是此时遍历指针p指向的是A的右子树根节点K；而当K被弹出栈时，此时栈也为空，且访问指针p指向的是K的右子树根节点，但是K已经没有右子树，所以p为nullptr。即当二叉树真正被遍历完时，需要同时满足 栈空 和 访问节点为空 两个条件，因此我们可以将循环退出条件做相应修改，得到：

p = tree->root;
while( p!=nullptr || !isEmpty(stack) ){
  if( p != NULL ){
    push(stack, p)
    p = p->Lchild;
  }
  else{
    p = pop(stack); //出栈
    process(p);     //访问
    p = p->Rchild;  //前往右子树
  }
}

    · 实现法二：利用递归实现回溯
    使用递归的实现理解起来比较简单，如下所示：

void inorder( root ){
  if( root->Lchild != NULL)
    inorder (root->Lchild);
  process(root);
  if( root->Rchild != NULL)
    inorder(root->Rchild);
}

(c) 先序遍历算法的实现

    基于上述对中序遍历算法的讨论，我们可以轻松得到先序遍历算法的实现如下：
    · 实现法一：利用栈实现回溯

p = tree->root;
while( p!=nullptr || !isEmpty(stack) ){
  if( p != NULL ){
    process(p);     //访问
    push(stack, p)
    p = p->Lchild;
  }
  else{
    p = pop(stack); //出栈
    p = p->Rchild;  //前往右子树
  }
}

    · 实现法二：利用递归实现回溯

void preorder( root ){
  process(root);
  if( root->Lchild != NULL)
    preorder (root->Lchild);
  if( root->Rchild != NULL)
    preorder(root->Rchild);
}

(d) 后序遍历算法的实现

    和之前中序和前序算法不同，后续遍历的root节点要最后才能被访问，因此，若想访问某节点，就需要知道该节点的右节点是否已经被访问过。只有该节点的右节点为nullptr，或者已被访问过，那么该节点才能被访问，否则需要先将右节点访问完。为了判断该节点的右节点是否已经被访问过，需另外设一个记录指针tag来指示已经访问过的节点，如果之前访问过的节点tag恰为该节点的右节点，说明其右子树已经访问完，应该访问该节点。
    · 实现法一：利用栈实现回溯

tnode_type *tag = nullptr;
while( p != NULL || !isEmpty(stack) ){
  if( p != NULL ){
    push(stack, p);
    p = p->Lchild;
  }
  else{
    p = gettop(stack);//弹栈前先判断栈顶节点的右孩子是否为空及其是否被访问
    if(p->Rchild!=NULL && p->Rchild!=tag) p = p->Rchild;//当栈顶节点有右孩子并且没有被访问过，则移到栈顶节点的右孩子
    else{
      process(p);
      p=pop(stack);
      tag=p;
      p=NULL;
    }
  }
}

    · 实现法二：利用递归实现回溯

void postorder( root ){
  if( root->Lchild != NULL)
    postorder (root->Lchild);
  if( root->Rchild != NULL)
    postorder(root->Rchild);
  process(root);
}

(5) 二叉树的建立

    以上图为例，我们输入一串序列，其中用“_”（空格）代表空元素。下面以先序为例，列出二叉树具体构造方法：
    思路一：

void create_tree_preorder(tnode* root){
  char ch = 0;
  char* temp = nullptr;
  
  /*------------结点左子树的构建------------*/
  /*读取输入，若不为空则创建结点*/
  scanf(&ch);
  if(ch != ' '){
    temp = create_node(ch);
  }

  /*将创建的结点（或空指针）挂载在左孩子下*/
  root->Lchild = temp;

  /*若左孩子不为空，则前往左孩子*/
  if(root->Lchild != nullptr){
    create_tree_preorder(root->Lchild);
  }

  /*------------结点右子树的构建------------*/
  /*读取输入，若不为空则创建结点*/
  scanf(&ch);
  if(ch != ' '){
    temp = create_node(ch);
  }

  /*将创建的结点（或空指针）挂载在左右孩子下*/
  root->Rchild = temp;

  /*若左孩子不为空，则前往右孩子*/
  if(root->Rchild != nullptr){
    create_tree_preorder(root->Rchild);
  }
}

    思路二：

void create_tree_preorder(){
  tnode* p;
  char ch;

  scanf(&ch);
  if(ch != ' '){
    p = create_node(ch);
  }
  else{
    return nullptr;
  }

  p->Lchild = create_tree_preorder();
  p->Rchild = create_tree_preorder();
}

(5) 二叉树的插入和删除

    (a) 插入：

    对于二叉树的插入，我们遵守的原则是保证插入后按照规定的遍历顺序遍历出来的树结点序列除了多了一个新结点外，其它结点在遍历顺序上连续且保持和原有不变。以上图为例，倘若我们采用中序遍历的方式，则插入前的遍历顺序是 左 根 右，那么在根节点的右孩子处插入新结点的话，我们应该把根节点原来的右子树挂载到新节点的左边，才能保证遍历顺序是 左 根 右 new。类比，如果插入的位置是在根节点的左孩子处，那么则需要把根节点原来的左子树挂载到新结点的右边，才能保证原有树遍历顺序保持连续且不变。

    (b) 删除：

    对于二叉树的删除，我们遵守的原则是保证删除后二叉树的结点遍历顺序与删除前保持不变。以上图为例，倘若我们按照中序遍历的顺序，在删除之前，遍历顺序是 爷 左 del 右，我们在删除爷结点右子树的根，即del结点后，为了保证遍历顺序是 爷 左 右，则必须把从del上“剪”下来的左子保证树 `T_L` 挂在爷结点的右子树位置，把从del上“剪”下来的右子树 `T_R` 挂在 `T_L` 的右子树位置。类比，如果删除的位置是爷结点的左子树根节点del的话，则必须把从del上“剪”下来的右子树 `T_R` 挂在爷结点的左子树位置，把从del上“剪”下来的左子树 `T_L` 挂在 `T_R` 的左子树位置，才能保证删除后二叉树的结点遍历顺序与删除前保持不变。

(6) 二叉树的重构

    在没有使用空格标明空孩子的情况下，我们无法根据单一序列来重构二叉树。只有在给出 先序遍历序列&中序遍历序列 或 后序遍历序列&中序遍历序列 的情况下（总之一定要有中序序列），我们才可以对一个二叉树进行重构。具体例子如下所示：

(7) 树的二叉表示

    如下图所示，是将非二叉树转化为二叉树的方法

(8) 森林转化为二叉树

    将森林转化为二叉树的原则是：
        (a) 先将森林的每颗树都转换为二叉树
        (b) 选定其中的一颗树，将其它树的根结点以右孩子的方式串起来。

(9) 二叉排序树

    · 定义（递归定义）：
        (a) 或为空树，或具有如下性质；
        (b) 左子树上所有结点的关键字均小于根结点的关键字，右子树上所有结点的关键字均大于或等于根结点的关键字；
        (c) 左、右子树又各是一棵二叉排序树。
    · 建立二叉排序树算法：
        对于二叉排序树建立算法，算法的输入是一组无序元素，输出是一颗二叉排序树，算法（元素插入）的基本思路如下：
        (a) 先将新元素与根结点比较，若小于根节点，则插入左子树中；若大于等于根结点，则插入右子树中；
        (b) 再将新元素与子树的根结点比较，直到某结点k，使得下面有一种情况发生：
            新元素小于k，且k左子树为空，则成为k的左孩子；
            新元素大于等于k，且k右子树为空，则成为k的右孩子。
    具体代码如下所示：

p = tree->root;
while(p != nullptr){
  if(new_node->data < p->data){
    if(p->Lchild == nullptr){
      p->Lchild = new_node;
      break;
    }else{
      p = p->Lchild;
    }
  }else{
    if(p->Rchild == nullptr){
      p->Rchild = new_node;
      break;
    }else{
      p = p->Rchild;
    }
  }
}

附录：参考源

1. 电子科技大学, 数据结构与算法 课程课件（2018秋季）