《数据结构》第五章 树与二叉树

5.1 树的基本概念

5.1.1 树的定义

树是 $n(n>=0)$ 个结点的有限集。

• 空树：$n=0$，即结点数为 0 的树，称为空树。

• 一颗非空树满足的特征：

  • 有且仅有一个根节点。
  • 叶子结点（终端结点）：没有后继的结点。
  • 分支结点（非终端结点）：有后继的结点。
  • 除了根节点外，任何一个结点都有且仅有一个前驱。（根节点无前驱）
  • 每个结点可以有 0 个或多个后继。

5.1.2 基本术语

• 属性

  • 结点的层次（深度）——从上往下数。
  • 结点的高度——从下往上数。
  • 树的高度（深度）——总共多少层。
  • 结点的度——有几个孩子（分支）。
  • 树的度——各结点的度的最大值。

• 有序树与无序树

  • 有序树——逻辑上看，树中结点的各子树从左至右是有次序的，不能互换。
  • 无序树——逻辑上看，树中结点的各子树从左至右是无次序的，可以互换。

• 路径和路径长度

  • 路径——两个结点之间所经过的结点序列。
  • 路径长度——路径上所经过的边的个数。
• 森林
  m棵互不相交的树的集合。

5.1.3 树的性质

• 考点1：结点数 = 总度数 + 1
• 考点2：度为 m 的树、m 叉树的区别

• 考点3：度为 $m$ 的树（或 $m$ 叉树）第 $i$ 层至多有 $m^{i-1}$ 个结点 $(i\ge 1)$
• 考点4：高度为 $h$ 的 $m$ 叉树至多有 $\frac{m^{h}-1}{m-1}$ 个结点

• 考点5：

  • 高度为 $h$ 的 $m$ 叉树至少有 $h$ 个结点
  • 高度为 $h$ 、度为 $m$ 的树至少有 $h+m-1$ 个结点
  • 可推出：度为 $m$ 、具有 $n$ 个结点的树最大高度为 $n-m+1$

• 考点6：具有 $n$ 个结点的 $m$ 叉树的最小高度为 $\left \lceil \log_{m}{(n(m-1)+1)} \right \rceil$ （向上取整）
  运算过程：高度最小的情况——所有结点都有 $m$ 个孩子（除叶结点）

  $$ \frac{m^{h-1}-1}{m-1}< n\le \frac{m^{h}-1}{m-1} $$

  $$ m^{h-1}< n(m-1)+1\le m^{h} $$

  $$ h-1< \log_{m}{n(m-1)+1} \le h $$

  $$ h_{min} = \left \lceil \log_{m}{(n(m-1)+1)} \right \rceil $$

5.2 二叉树的概念

5.2.1 二叉树的定义及其主要特性

1. 二叉树的定义

是一种特殊的树形结构，每个结点至多只有两颗子树。
二叉树是 $n(n>=0)$ 个结点的有限集合：

• 或者为空二叉树，即 $n = 0$。
• 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。
  特点：
• 每个结点至多只有两棵子树。
• 左右子树不能颠倒（二叉树是有序树）。

2. 几种特殊的二叉树

• 满二叉树：一棵高度为 $h$ ，且含有 $2^{h} - 1$ 个结点的二叉树。

  • 只有最后一层有叶子结点。
  • 不存在度为 1 的结点。
  • 按层序从 1 开始编号，结点 $i$ 的左孩子为 $2i$，右孩子为 $2i+1$；结点 $i$ 的父节点为 $\left \lfloor \frac{i}{2} \right \rfloor$（如果有的话）

• 完全二叉树：当且仅当其每个结点都与高度为 $h$ 的满二叉树中编号为 $1 ～ n$ 的结点一一对应时，称为完全二叉树。

  • 只有最后两层可能有叶子结点。
  • 最多只有一个度为1的结点。
  • 按层序从 1 开始编号，结点 $i$ 的左孩子为 $2i$，右孩子为 $2i+1$；结点 $i$ 的父节点为 $\left \lfloor \frac{i}{2} \right \rfloor$（如果有的话）
  • $i\le \left \lfloor \frac{n}{2} \right \rfloor$ 为分支结点，$i> \left \lfloor \frac{n}{2} \right \rfloor$ 为叶子结点。

• 二叉排序树：一棵二叉树或者是空二叉树。

  • 左子树上所有结点的关键字均小于根结点的关键字。
  • 右子树上所有结点的关键字均大于根结点的关键字。
  • 左子树和右子树又各是一棵二叉排序树。
• 平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过1。
• 正则二叉树：树种每个分支结点都有 2 个孩子，即树种只有度为 0 或 2 的结点。

3. 二叉树的性质

• 二叉树

  • 考点1：设非空二叉树中度为0、1 和 2 的结点个数分别为 $n_0$、$n_1$ 和 $n_2$ ，则 $n_0=n_2+1$。（叶子结点比度为二的分支结点多一个）
  • 考点2：二叉树第 $i$ 层至多有 $2^{i-1}$ 个结点 $(i\ge 1)$。
  • 考点3：二叉树至多有 ${2^{h}-1}$ 个结点

• 完全二叉树

  • 考点1：具有 $n$ 个结点的完全二叉树的高度 $h$ 为 $\left \lceil \log_{2}{(n+1)} \right \rceil$ 或 $\left \lfloor \log_{2}{n} \right \rfloor+1$

  • 考点2：对于完全二叉树，可以由结点数 $n$ 推出度为 0、1和 2 的结点个数为 $n_0$、$n_1$和 $n_2$完全二叉树最多只有一个度为1的结点，即$n_1=0或1$。由此 $n_0=n_2+1\Rightarrow n_0+n_2$ 一定是奇数。

    • 若完全二叉树有 $2k$ 个（偶数）结点，则必有 $n_1=1,n_0=k,n_2=k-1$
    • 若完全二叉树有 $2k-1$ 个（奇数）结点，则必有 $n_1=0,n_0=k,n_2=k-1$

5.2.2 二叉树的存储结构

1. 顺序存储结构

#define MaxSize 100
struct TreeNode {
    ElemType value;
    bool isEmpty;
};

对于顺序存储的二叉树：

• $i$ 的左孩子—— $2i$
• $i$ 的右孩子—— $2i+1$
• $i$ 的父结点—— $\left \lfloor \frac{i}{2} \right \rfloor$
• $i$ 所在的层次——$\left \lceil \log_{2}{(i+1)} \right \rceil$ 或 $\left \lfloor \log_{2}{i} \right \rfloor+1$
  若完全二叉树中共有 $n$ 个结点，则：
• 判断 $i$ 是否有左孩子？—— $2i\le n$?
• 判断 $i$ 是否有右孩子？—— $2i+1\le n$?
• 判断 $i$ 是否是叶子/分支结点？—— $i> \left \lfloor \frac{n}{2} \right \rfloor$?

2. 链式存储结构

typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

• $n$ 个结点的二叉链表共有 $n+1$ 个空链域。（可以将这些空链域组成线索链表 见5.3.2）

插入根节点

root = (BiTree) malloc (sizeof(BiTNode));
root->data = {1};
root->lchild = NULL;
root->rchild = NULL;

插入新结点

BiTNode *p = (BiTNode*) malloc (sizeof(BiTNode));
p->data = {2};
p->lchild = NULL;
p->rchild = NULL;
root->lchild = p;

5.3 二叉树的遍历和线索二叉树

5.3.1 二叉树的遍历

1. 先序遍历（NLR）

void PreOrder(BiTree T){
    if(T != NULL){
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

2. 中序遍历（LNR）

void InOrder(BiTree T){
    if(T != NULL){
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

3. 后序遍历（LRN）

void PostOrder(BiTree T){
    if(T != NULL){
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }
}

4. 层次遍历（使用队列）

void LevelOrder(BiTree T){
    InitQueue(Q);
    BiTree P;
    EnQueue(Q, T);
    while(!IsEmpty(Q)){
        DeQueue(Q, p);
        visit(p);
        if(p->lchild != NULL)
            EnQueue(Q, p->lchild);
        if(p->rchild != NULL)
            EnQueue(Q, p->rchild);
    }
}

5. 由遍历序列构造二叉树

任选前、后、层，三选二，不能构造二叉树，一定要有中序序列。
因此有以下组合：

• 先序序列+中序序列
• 后序序列+中序序列
• 层序序列+中序序列

5.3.2 线索二叉树

1. 线索二叉树的基本概念

传统的二叉链表存储不能直接得到结点的前驱或后继。因此引入线索二叉树加快查找结点前驱或后继的速度。

规定：

• 若无左子树，令lchild指向其前驱结点。
• 若无右子树，令rchild指向其后继结点。

• 增加两个标志域ltag和rtag：

  • 当tag=0时，child指针将表示指向孩子。
  • 当tag=1时，child指针将表示指向前驱或后继。

typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;
}ThreadNode, *ThreadTree;

2. 中序线索二叉树的构造

中序遍历对二叉树线索化的递归算法：

void InThread(ThreadTree &p, ThreadTree &pre){
    if(p != NULL){
        InThread (p->lchild, pre);
        if(p->lchild == NULL){
            p->lchild = pre;
            p->ltag = 1;
        }
        if(pre != NULL && pre->rchild == NULL){
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p;
        InThread(p->rchild, pre);
    }
}

中序遍历建立中序线索二叉树：

void CreateInThread(ThreadTree T){
    ThreadTree pre = NULL;
    if(T != NULL){
        InThread(T, pre);
        pre->rchild = NULL;//处理遍历的最后一个结点
        pre->rtag = 1;
    }
}

3. 中序线索二叉树的遍历

• 通过中序线索二叉树找中序序列的第一个结点：

  ♾️ C 代码:

  ThreadNode *Firstnode(ThreadNode *p){
    while(p->ltag == 0)
        p = p->lchild; //找最左下结点
        return p;
  }

• 通过中序线索二叉树找中序序列中 p 结点的后继：

  ♾️ C 代码:

  ThreadNode *Nextnode(ThreadNode *p){
    if(p->rtag == 0)
        return Firstnode(p->rchild); //右子树最左下结点
    else
        return p->rchild;
  }

• 通过中序线索二叉树找中序序列的最后一个结点：

  ♾️ C 代码:

  ThreadNode *Lastnode(ThreadNode *p){
    while(p->rtag == 0)
        p = p->rchild; //找最右下结点
        return p;
  }

• 通过中序线索二叉树找中序序列中 p 结点的前驱：

  ♾️ C 代码:

  ThreadNode *Prenode(ThreadNode *p){
    if(p->ltag == 0)
        return Lastnode(p->lchild);
    else
        return p->lchild;
  }

• 对中序线索二叉树进行中序遍历：

  ♾️ C 代码:

  void Inorder(ThreadNode *T){
    for(ThreadNode *p = Firstnode(T); p != NULL; p = Nextnode(p))
        visit(p);
  }

• 对中序线索二叉树进行逆中序遍历：

  ♾️ C 代码:

  void RevInorder(ThreadNode *T){
    for(ThreadNode *p = Lastnode(T); p != NULL; p = Prenode(p))
        visit(p);
  }

4. 先序线索二叉树和后序线索二叉树

• 先序线索二叉树

  ♾️ C 代码:

  void PreThread(ThreadTree &p, ThreadTree &pre){
    if(p != NULL){
    //和中序类似，改变访问根的先后顺序即可
        if(p->lchild == NULL){
            p->lchild = pre;
            p->ltag = 1;
        }
        if(pre != NULL && pre->rchild == NULL){
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p;
        
        //需注意转圈问题，若ltag=1，则前驱指向父结点，父结点的左孩子又是该结点，会导致转圈
        if(p->ltag == 0)
            PreThread (p->lchild, pre);
            
        PreThread(p->rchild, pre);
    }
  }

• 后序线索二叉树

  ♾️ C 代码:

  void PostThread(ThreadTree &p, ThreadTree &pre){
    if(p != NULL){
        PostThread (p->lchild, pre);
        PostThread(p->rchild, pre);
        if(p->lchild == NULL){
            p->lchild = pre;
            p->ltag = 1;
        }
        if(pre != NULL && pre->rchild == NULL){
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p;
    }
  }

5. 总结

5.4 树、森林

5.4.1 树的存储结构

1. 双亲表示法（顺序存储）

适用于找“父亲”多，找“孩子”少。

#define MaxSize 100
typedef struct {
    ElemType data;
    int parent;
}PTNode;

typedef struct {
    PTNode nodes[MaxSize];
    int n; //结点数
}

2. 孩子表示法（顺序+链式存储）

适用于找”孩子“多，找”父亲“少。

typedef struct CTNode {
 int child;
 struct CTNode *next;
}CTNode;

typedef struct {
    ElemType data;
    struct CTNode *firstChild;
}CTBox;

typedef struct {
    CTBox nodes[MaxSize];
    int n; //结点数
    int r; //根的位置
}

3. 孩子兄弟表示法（链式存储）

最大的优点是 可以方便实现树转换成二叉树的操作。

typedef struct CSNode {
    ElemType data;
    struct CSNode *firstchild, *nextsibling; //分别是 指向第一个孩子，指向右边一个兄弟
}CSNode, *CSTree;

5.4.2 树、森林与二叉树的转换

1. 树转换成二叉树

• 在兄弟结点之间加一连线。
• 对每个结点，只保留它与第一个孩子的连线，而与其他孩子的连线全部抹掉。

2. 森林转换为二叉树

• 将森林的每棵树转换成二叉树。
• 将每棵树的根视为兄弟结点，然后加一连线。

3. 二叉树转换成森林

• 画出树的根结点。
• 从树的根节点开始，按“树的层序”恢复每个结点的孩子。

5.4.3 树和森林的遍历

1. 树的遍历

与二叉树的遍历思路基本相同：

• 先根遍历（深度优先遍历）
• 后根遍历（深度优先遍历）
• 层次遍历（广度优先遍历）

2. 森林的遍历

• 先序遍历森林 （等效二叉树的先序遍历）
• 中序遍历森林 （等效二叉树的中序遍历）

3. 树、森林、二叉树遍历对应关系

5.5 树与二叉树的应用

5.5.1 哈夫曼树和哈夫曼编码

1. 哈夫曼树的定义

• 结点的权：结点被赋予某种意义的值。
• 结点的带权路径长度：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积。

• 树的带权路径长度（WPL）：树中所有叶结点的带权路径长度之和。

  $$ WPL=\sum_{i=1}^{n} w_i l_i $$

  哈夫曼树：WPL 最小的二叉树。

2.哈夫曼树的构造

• 构造步骤：

  • 将这 $n$ 个结点分别作为 $n$ 棵仅含一个结点的二叉树，构成森林 $F$。
  • 构造一个新结点，从 $F$ 中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。
  • 从 $F$ 中删除刚才选出的两棵树，同时将新得到的树加入 $F$ 中。
  • 重复步骤 2 和 3，直至F中只剩下一棵树为止。

• 性质：

  • 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大。
  • 哈夫曼树的结点总数为 $2n − 1$ ，新建了 $n-1$ 个结点。
  • 哈夫曼树中不存在度为 1 的结点。
  • 哈夫曼树并不唯一，但WPL必然相同且为最优。

3. 哈夫曼编码

• 固定长度编码：每个字符用相等长度的二进制位表示。
  
  A：00；
  B：01；
  C：10；
  D：11
• 可变长度编码：允许对不同字符用不等长的二进制位表示。
  
  C：0；
  A：10；
  B：111；
  D：110
• 前缀编码：若没有一个编码是另一个编码的前缀。

5.5.2 并查集

1. 并查集的概念

一种简单的集合表示。

• Initial(S)：将集合 $S$ 中的每个元素都初始化为只有一个单元的子集合。
• Union(S, Root1, Root2)：把集合 $S$ 中的子集合 $Root2$ 并入子集合 $Root1$。要求这两集合不相交。
• Find(S, x)：查找集合 $S$ 中单元素 $x$ 所在的子集合，并返回该子集合的根结点。

2. 并查集的存储结构

通常使用树的双亲表示法作为并查集的存储结构。

typedef struct {
    ElemType data;
    int parent;
}UFSets;

3. 并查集的基本实现

• 初始化

  ♾️ C 代码:

  void Initial(int S[]){
    for(int i = 0; i<MaxSize; i++)
        S[i] = -1;
  }

• Find操作（查）

  ♾️ C 代码:

  int Find(int S[], int x){
    while(S[x] >= 0)
        x = S[x];
    return x;
  }

  时间复杂度为 $O(d)$（ d 为树的深度）

• Union操作（并）

  ♾️ C 代码:

  void Union(int S[], int Root1, int Root2){
    if(Root1 == Root2)
        return;
    S[Root2] = Root1;
  }

  时间复杂度为 $O(1)$

4. 并查集实现的优化

• 改进的 Union操作

  ♾️ C 代码:

  void Union(int S[], int Root1, int Root2){
    if(Root1 == Root2)
        return
    //注：S[]为根时的值为负数，所以比值越大的，表示为小树
    //优化目标：小树合并到大树
    if(S[Root2] > S[Root1]){
        S[Root1] += S[Root2];
        S[Root2] = Root1;
    }
    else{
        S[Root2] += S[Root1];
        S[Root1] = Root2;
    }
  }

  时间复杂度为 $O(1)$

• 改进的 Find操作

  ♾️ C 代码:

  int Find(int S[], int x){
    int root = x;
    while(S[root] > =0)
        root = S[root];
    while(x != root){
        int t = S[x];
        S[x] = root;
        x = t;
    }
    return root;
  }

  时间复杂度为 $O(\alpha (n))$，$\alpha (n)$是一个增长极其缓慢的函数，对于常见的正整数 $n$，通常 $\alpha (n)\le 4$。