6.1 树的定义

树（Tree）是n(n大于等于0)个结点的有限集T
若n=0，称为空树
有且仅有一个特定的称为根Root的结点
其余结点可分为m(m>=0)个互不相交的有限集T1, T2, T3…Tm, 其中每个集合本身又是一棵树称为根的子树(SubTree)

基本术语：

• 结点(node): 包括一个数据元素及若干指向其子树的分支
• 结点的层次(level)：从根结点算起，根为第一层，它的孩子为第二层……
• 结点的祖先：从根到该结点所经分支上的所有结点
• 结点的度(degree)：结点拥有的子树个数
• 树的度：树内各结点的度的最大值
• 深度(depth)：树中结点的最大层次数
• 森林(forest)：m(m0)棵互不相交的树的集合
• 叶子(leaf)：度为0的结点（或称终端结点）
• 分支结点（非终端结点）：度不为0的结点
• 孩子(child)：结点的子树的根称为该结点的孩子
  • 结点 B、C、D 是结点 A 的孩子；
  • 结点 E、F 是结点 B 的孩子；
• 双亲(parents): (相对孩子)结点的上层结点
  • 结点 A 是结点 B、C、D 的双亲；
  • 结点 B 是结点 E、F 的双亲；
• 兄弟(sibling)：同一双亲的孩子之间互称兄弟
• 子孙：某结点为根的子树中的任意结点

6.2 二叉树

二叉树：是n个结点的有限集
特点：

• 每个结点至多有二棵子树(即不存在度大于2的结点)
• 二叉树的子树有左、右之分，且其次序不能任意颠倒

5种基本形态：

二叉树的性质

1. 在二叉树的第 i 层上至多有\(2^{i-1}\)个结点 (\(i\geq1\))
2. 深度为 k 的二叉树至多有\(2^k -1\)个结点 (\(k \geq 1\))
3. 对任何一棵二叉树 T，如果其终端结点数为\(n_0\)，度为 2 的结点数为\(n_2\)，则 \(n_0 = n_2 + 1\)
   • 二叉树里 “没孩子的结点” 数量，永远比 “有两个孩子的结点” 数量多 1 个。比如如果有 3 个度为 2 的结点，那终端结点就有 4 个
4. 具有 n 个结点的完全二叉树的深度为\(\lfloor \log_2 n \rfloor + 1\)

1证明

证明： 用归纳法证明
①当\(i=1\)时，只有一个根结点，\(2^{i-1}=2^0=1\)，是对的
②假设对所有\(j(1\leq j < i)\)命题成立，即第j层上至多有\(2^{j-1}\)个结点
那么，第\(i-1\)层至多有\(2^{i-2}\)个结点
又二叉树每个结点的度至多为 2
∴ 第i层上最大结点数是第\(i-1\)层的 2 倍，即\(2 \times 2^{i-2}=2^{i-1}\)

2证明

由性质 1 知深度为 k 的二叉树最大结点数为
\(\sum_{i=1}^{k}(\text{第}i\text{层上的最大结点数})= \sum_{i=1}^{k}2^{i-1}=2^k -1\)

3证明

证明： 设\(n_1\)为二叉树 T 中度为 1 的结点数

因为：二叉树中所有结点的度均小于或等于 2

所以：其结点总数\(n = n_0 + n_1 + n_2\)

又二叉树中，除根结点外，其余结点都只有一个分支进入

设 B 为分支总数，则\(n = B + 1\)

又：分支由度为 1 和度为 2 的结点射出，\( B = n_1 + 2n_2\)

于是，\(n = B + 1 = n_1 + 2n_2 + 1 = n_0 + n_1 + n_2\)

\( n_0 = n_2 + 1\)

4证明

设深度为 k，根据性质 2 和完全二叉树的定义有

\(2^{k-1} – 1 < n \leq 2^k – 1\)

或

\(2^{k-1} \leq n < 2^k\)

于是

\(k-1 \leq \log_2 n < k\)

因为 k 是整数，所以 \(k = \lfloor \log_2 n \rfloor + 1\)

5例子

（1）找 “爸爸” 的规律

• 如果某个结点的编号是 1 → 它是树的根，没有爸爸；
• 如果编号不是 1 → 它的爸爸编号是 “自己编号除以 2，取整数部分”（比如编号 5 的爸爸是 5÷2=2.5，取整是 2）。

（2）找 “左孩子” 的规律

• 用自己的编号 ×2，如果结果超过了树的总结点数 n → 这个结点没有左孩子；
• 如果 ×2 的结果≤n → 这个结果就是左孩子的编号（比如编号 3，总结点数 n≥6，那左孩子是 3×2=6）。

（3）找 “右孩子” 的规律

• 用自己的编号 ×2+1，如果结果超过了总结点数 n → 这个结点没有右孩子；
• 如果 ×2+1 的结果≤n → 这个结果就是右孩子的编号（比如编号 3，总结点数 n≥7，那右孩子是 3×2+1=7）。

例题：若一颗二叉树共有n个结点，则二叉树的深度最小为多少，最大为多少

完全二叉树& 满二叉树

完全二叉树
定义：除了最后一层外，其他各层的结点数都达到最大值（即第i层有\(2^{i-1}\)个结点）
特点：

• 叶子结点只可能在层次最大的两层上出现只有当最后一层没填满时，倒数第二层的部分结点才会成为叶子）
• 对任一结点，其左子树深度，要么和右子树一样深，要么比右子树深 1 层

满二叉树
定义：
满二叉树是完全二叉树的一个特例
满二叉树的最后一层结点数也达到了最大值，即深度为k的满二叉树有\(2^k -1\)个结点
特点：每一层上的结点数都是最大结点数

二叉树的存储结构

顺序存储结构

浪费空间，适用于存满二叉树和完全二叉树

链式存储结构

二叉树链表中的结点至少包含3个域：数据域和左右指针域分别指向其左右子树（二叉链表）
有时为了便于找到双亲，增加一个指向其双亲结点的指针域（三叉链表）

在具有 n 个结点以二叉链表表示的二叉树中，其非空指针域的个数为n+1个

证明

二叉链表表示：每个结点有 2 个指针域（left、right），一共 2n 个指针域。

非空指针域指的是：真正指向某个孩子结点的指针。

在一棵树里，有 n 个结点就一定有 n-1 条边（因为从根到其余每个结点，都需要一条“父子连接”，总共 n-1次连接）。

而在二叉链表里：

• 每一条父子边 = 一个非空孩子指针所以非空指针域个数 = 边数 = n-1。

（顺带：空指针域个数 = 2n-(n-1)=n+1，这也是常考结论。）

遍历二叉树 Traversing Binary Tree

按某条搜索路径巡访树的每个结点，且使每个顶点仅被访问一次，输出树中所有结点的一个线性排列

由二叉树的递归定义可知：二叉树是由三个基本单元组成：根结点D、左子树L、右子树R
则可得到 6 种遍历方案：DLR、LDR、LRD、DRL、RDL、RLD

若限定先左后右则剩3种方案（命名由根节点的次序决定）

• 先序遍历：先看根节点，再把左子树整个逛完，最后逛右子树
• 中序遍历：先把左子树整个逛完，再看当前根节点，最后逛右子树
• 后序遍历：先把左子树整个逛完，再把右子树整个逛完，最后看当前根节点

• 若先序遍历此二叉树，可得到二叉树的先序序列为 – + a * b – c d / e f
• 类似地，中序遍历此二叉树，可得此二叉树的中序序列为 a + b * c – d – e / f 要逛完子树
• 后序遍历此二叉树，可得此二叉树的后序序列为 a b c d – * + e f / –

为了让输入唯一对应一棵二叉树，必须在输入时用 “空字符”（比如图里的 “Ø”）表示 “这个位置没有结点”
（就像图里右边那两棵树，结构不一样，但先序序列可能相同）

// 先序遍历二叉树 T：根-左-右
Status PreOrderTraverse(BiTree T)
{
    if (T) {                       // 当前结点存在
        Visit(T->data);            // ① 访问根
        PreOrderTraverse(T->lchild); // ② 遍历左子树
        PreOrderTraverse(T->rchild); // ③ 遍历右子树
    }
    // T 为空时什么都不做，直接返回（相当于递归终止条件）
}

// 中序遍历二叉树 T：左-根-右
Status InOrderTraverse(BiTree T)
{
    if (T) {                         // 当前结点存在
        InOrderTraverse(T->lchild);  // ① 先遍历左子树（“左”）
        Visit(T->data);              // ② 再访问根结点（“根”）
        InOrderTraverse(T->rchild);  // ③ 最后遍历右子树（“右”）
    }
}

// 后序遍历二叉树 T：左-右-根
Status PostOrderTraverse(BiTree T)
{
    if (T) {                          // 当前结点存在
        PostOrderTraverse(T->lchild); // ① 先遍历左子树（“左”）
        PostOrderTraverse(T->rchild); // ② 再遍历右子树（“右”）
        Visit(T->data);               // ③ 最后访问根结点（“根”）
    }
}

这些函数背后的原理

递归理解为：函数自己调用自己。
每次调用函数，系统都要记住“等会儿回到哪里继续执行”
为什么树遍历非递归要自己写栈？
因为二叉树会“分叉”：你走进左子树后，还要回来走右子树。
递归是“系统帮你记路”（用调用栈）；非递归是“你自己记路”（写 st[] + top）。

例题：

树与森林

森林的定义：若干棵互不相交的树的集合（每棵树彼此独立，没有公共结点）

树的存储结构

双亲表示法(数组)

结构数组（数组）存放树的结点，每个结点含两个域：
数据域：存放结点本身信息，双亲域：指示本结点双亲结点在数组中位置

• 数组第 0 位是 A：A 是根节点（没有爸爸），所以 parent 写-1（表示无父）；
• 数组第 1 位是 B：B 的爸爸是 A（A 在 0 位），所以 parent 写0；
• 数组第 2 位是 C：C 的爸爸是 A（A 在 0 位），所以 parent 写0；
• 数组第 3 位是 D：D 的爸爸是 B（B 在 1 位），所以 parent 写1；

 特点：“找双亲容易，找孩子难”

• 想知道 G 的双亲是谁，看 G 在数组第 6 位，parent 是 4 → 数组第 4 位是 E，所以 G 的爸爸是 E；
• 想知道 B 有哪些孩子，得把整个数组扫一遍，看谁的 parent 是 1（B 的下标）→ 扫出来 D（3 位）、E（4 位），所以 B 的孩子是 D、E

// 1. 定义树的最大节点数（最多存100个节点）
#define MAX_TREE_SIZE 100  

// 2. 定义“单个节点的结构”（对应之前的“家庭关系卡”）
typedef struct PTNode {  
    TElemType data;  // 数据域：存节点自己的信息（比如A、B）
    int parent;      // 双亲域：存“爸爸在数组中的下标”（根节点的parent是-1）
} PTNode;  

// 3. 定义“整个树的结构”（用数组存所有节点）
typedef struct {  
    PTNode nodes[MAX_TREE_SIZE];  // 存所有节点的数组
    int r;  // 根节点在数组中的下标（比如根是A，r就是0）
    int n;  // 树的总节点数
} PTree;  


// 4. 函数：找节点t[i]的“第一个孩子”（长子）
Int FirstChild (PTree t, int i)  
{  
    // 遍历数组中i之后的节点（从i+1开始，因为节点一般按层次/顺序存）
    for (j = i+1; j < t.n; j++) {  
        // 如果某个节点的parent是i → 这个节点是t[i]的孩子
        if (t.nodes[j].parent == i)  
            return (j);  // 返回第一个找到的孩子的下标
    }  
    return (-1);  // 没找到孩子，返回-1
}

孩子表示法（多重链表）

它分两种形式：

1. 节点同构

• 规则：不管一个节点有多少个孩子，都给它固定数量的 “孩子指针”（数量等于树的最大孩子数，叫 “树的度 d”）。
• 缺点：浪费空间—— 比如某个节点只有 1 个孩子，剩下 2 个指针位就空着没用

2. 节点不同构

• 规则：按照节点 “自己有几个孩子（degree）”给对应数量的 “孩子指针”
• 比如节点 A 有 2 个孩子，就给 2 个指针位；节点 B 有 3 个孩子，就给 3 个指针位。
• 缺点：操作麻烦—— 每个节点的结构不一样，存、取的时候得先看 “degree”，再处理指针。

在基础版的数组条目里，加一个parent域（记爸爸在数组中的下标）。

// 1. 定义【孩子链表的单个节点】（存某个孩子在数组中的下标，以及下一个孩子的地址）
typedef struct CTNode {  
    int child;                  // 存“孩子节点在数组中的下标”（比如A的孩子B在数组第1位，这里就存1）
    struct CTNode *next;        // 指向下一个孩子的指针（链表的下一个节点）
} *ChildPtr;  // ChildPtr是这个结构的指针类型


// 2. 定义【数组中的单个节点】（存自己的信息+第一个孩子的链表入口）
typedef struct {  
    TElemType data;             // 存节点自己的信息（比如A、B）
    ChildPtr firstchild;        // 指向第一个孩子的链表指针（比如A的firstchild指向B对应的链表节点）
} CTBox;  


// 3. 定义【整个树的结构】（用数组存所有节点，记录总节点数和根的位置）
typedef struct {  
    CTBox nodes[MAX_TREE_SIZE]; // 存所有节点的数组（每个元素是CTBox类型）
    int n, r;                   // n：树的总节点数；r：根节点在数组中的下标（比如根A在数组第0位，r就是0）
} CTree;  

孩子兄弟表示法

“二叉链表” ，存储结构： 链表（链式存储） ，逻辑结构，二叉树，命名为list容易造成困惑

存储方式	核心特点	优点	缺点
双亲表示法	每个节点记 “爸爸的位置”	找爸爸方便	找孩子要遍历全树
孩子链表法	每个节点用 “链表记所有孩子”	找孩子方便	找爸爸要遍历全树（改进版加 parent 后才方便）
孩子兄弟表示法	每个节点记 “第一个孩子 + 下一个兄弟”	用二叉链表就能存任意树，结构统一（所有节点都是 2 个指针）	找爸爸需要额外遍历（得从根开始找）

森林与二叉树的转换

树转化为二叉树

树可以用二叉树存储，树的每个节点可以有多个孩子（比如 A 有 3 个孩子 B、C、E），但二叉链表每个节点只有 2 个指针 ， 如果直接存 “所有孩子”，指针数量不够，所以我们想了个办法：“左孩子，右兄弟”

• 左指针→第一个孩子：负责 “向下” 的父子关系
• 右指针→下一个兄弟：负责 “横向” 的兄弟关系

树转换为二叉树的操作步骤：

方法	描述	优点
三步法 (图形化)	1. 加线：兄弟间加线2. 删线：只留与长子的线3. 调整：顺时针旋转	直观易懂，适合在纸上画图分析，一步步引导你理解转换过程。
左孩子右兄弟法 (规则化)	对树中任意一个结点：1. 其第一个孩子作为它的左孩子。2. 其紧邻的右兄弟作为它的右孩子。	规则清晰，是算法的本质，非常适合用程序代码来实现。

从树与二叉树的转换可知：任何一棵和树对应的二叉树，其右子树必为空
（根节点的右子树为空，不是说整个二叉树所有节点都没有右子树）

二叉树和树，都能用 “二叉链表”（每个节点有 2 个指针）来存。从物理存储上看，它们用的是同一个二叉链表结构，但对指针的 “解释逻辑” 不一样

将n个二叉树转化为森林

• 将各棵树分别转换成二叉树
• 将每棵树的根结点用线相连
• 以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构

看出森林由哪些二叉树构成

给定一个森林可以唯一确定由哪些树构成

若把森林中第二棵树的根结点看成是第一棵树根结点的兄弟，则可导出森林和二叉树的对应关系
森林转换成二叉树
具体来说，每棵树对应 “当前节点 + 它的左子树”，而 “当前节点的右子树” 是下一棵树的起始（因为由上森林的树是普通树，只是转成二叉树存储森林的树互为兄弟，对应二叉树的右分支）：

1. 第 1 棵树 = 二叉树的根节点 + 根的左子树（因为树转二叉树后根的右子树为空，这里的右子树是下一棵树）；
2. 第 2 棵树 = 第 1 棵树根的右子树的根节点 + 这个根的左子树；
3. 第 3 棵树 = 第 2 棵树根的右子树的根节点 + 这个根的左子树；… 以此类推，直到右子树为空。

画图直观理解

树和森林的遍历

树的遍历（其实和二叉树一样）

先根（序）遍历，若T非空，则：
1、访问根结点R
2、依次先序遍历根的各子树

后根（序）遍历，若T非空，则：
1、依次后序遍历根的各子树
2、访问根结点R

此外，树的先根 / 后根遍历，和它对应的二叉树的先序 / 中序遍历，结果是完全一样的

遍历森林

1. 先序遍历森林

• 先访问第一棵树的根；
• 再先序遍历这棵树的子树（子树组成的小森林）；
• 最后先序遍历剩下的树组成的森林。→ 对应森林转成的二叉树的先序遍历。

2. 中序遍历森林

• 先中序遍历第一棵树的子树（子树组成的小森林）；
• 再访问这棵树的根；
• 最后中序遍历剩下的树组成的森林。→ 对应森林转成的二叉树的中序遍历

森林的先序 / 中序遍历，和它转成的二叉树的先序 / 中序遍历，结果完全一致；而二叉树的后序遍历，则是森林特有的遍历序列。

赫夫曼(Huffman)树

赫夫曼(Huffman)树，又称最优树，是带权路径长度最短的树，有着广泛的应用。本节先讨论最优二叉树

路径，路径长度：
从树中一个结点到另一个结点路径上的分支数目称做路径长度。
树的路径长度是从树根到每一结点的路径长度之和
若将上述概念推广到一般情况，考虑带权的结点。
结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积。
树的带权路径长度为树中所有叶子结点的带权路径长度之和，通常记作WPL

例：从 A 到 B，C，D，E，F，G，H，I 的路径长度分别为：1，1，2，2，2，3，3，3
树的路径长度：1+1+2+2+2+3+3+3=17

赫夫曼树——最优二叉树定义
设有n个权值w1 w2 …… wn ，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,
则wpl最小的那棵二叉树叫最优二叉树或Huffman树.

注意计算带权路径长度只需考虑最后的结点✖️路径长度即可

在解某些判定问题时，利用赫夫曼树可以得到最佳判定算法。例如，要编制一个将百分制转换成五级分制的程序。显然，此程序很简单，只要利用条件语句便可完成。如：

def score_to_grade(a):
    # 先验证输入是否为有效分数（0-100）
    if not isinstance(a, (int, float)) or a < 0 or a > 100:
        return "无效分数"
    # 按条件判定
    if a < 60:
        b = "bad"
    elif a < 70:
        b = "pass"
    elif a < 80:
        b = "general"
    elif a < 90:
        b = "good"
    else:
        b = "excellent"
    return b

这个判定过程可以图 6.23 (a) 的判定树来表示。如果上述程序需反复使用，而且每次的输入量很大，则应考虑上述程序的质量问题，即其操作所需时间。因为在实际生活中，学生的成绩在 5 个等级上的分布是不均匀的。假设其分布规律如下表所示：

分数	0—59	60—69	70—79	80—89	90—100
比例数	0.05	0.15	0.40	0.30	0.10

则 80% 以上的数据需进行 3 次或 3 次以上的比较才能得出结果。假定以 5,15,40,30 和 10 为权构造一棵有 5 个叶子结点的赫夫曼树，则可得到如图 6.23 (b) 所示的判定过程，它可使大部分的数据经过较少的比较次数得出结果。但由于每个判定框都有两次比较，将这两次比较分开，我们得到如图 6.23 (c) 所示的判定树，按此判定树可写出相应的程序。

假设现有 10 000 个输入数据，若按图 6.23 (a) 的判定过程进行操作，则总共需进行 31 500 次比较；而若按图 6.23 (c) 的判定过程进行操作，则总共仅需进行 22 000 次比较。

构造赫尔曼树

假设最优树的叶子权值从小到大是 \(w_1 \leq w_2 \leq … \leq w_n\)，则：

• a) 权值最小的两个叶子（\(w_1\)、\(w_2\)）是兄弟：最优树要让整体路径长度最小，就得让 “权值小的叶子” 放在路径最长的位置（这样 “权值 × 路径长度” 的总和才小）；而路径最长的位置，就是二叉树的最底层，所以最小的两个权值会作为兄弟节点放在最底层。
• b) 这两个叶子的父节点（分枝点），路径长度最长：因为这两个叶子在最底层，它们的父节点也在相对靠下的位置，所以从根到这个父节点的路径长度，是所有分枝点中最长的。

如果把 “\(w_1\)、\(w_2\) 这两个叶子的父节点”，替换成一个权值为 \(w_1 + w_2\) 的新叶子，得到的新树 \(T’\) 也是最优树。

这其实是赫夫曼树的构造方法：每次选两个最小的权值合并成一个新权值，重复这个过程直到只剩一个节点 —— 因为合并后新树的 WPL 依然是最小的，所以是最优树

Huffman 树的构造：

1. 根据给定的 n 个权值 {w1,w2,……wn} 构成 n 棵二叉树的集合 F={T1,T2,……Tn}，其中每棵二叉树 Ti 中只有一个带权为 Wi 的结点，其左右子树均为空。（构造森林全是根）
2. 在 F 中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，且置新的二叉树根结点的权值为其左右子树根结点权值之和。（选用两小造新树）
3. 在 F 中删除这两棵树，同时将新得到的二叉树加入森林中。（删除两小添新人）
4. 重复 2、3 上述两步，直到 F 只含一棵树为止，这棵树即为赫夫曼树

Huffman编码

// 函数功能：构造赫夫曼树，并为其生成赫夫曼编码
// 参数说明：
// - HT：赫夫曼树（输出参数，存储树的结构）
// - HC：赫夫曼编码（输出参数，存储每个叶子的编码）
// - w：存储n个叶子权值的数组
// - n：叶子结点的数量
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
{
    // 若只有0个或1个叶子，无需构造赫夫曼树（赫夫曼树至少需要2个叶子）
    if (n <= 1) return;

    // 赫夫曼树的总结点数公式：m = 2*n - 1（n个叶子 + n-1个分支结点）
    m = 2 * n - 1;

    // 为赫夫曼树分配内存：结点下标从1开始（共m+1个空间，0号不用）
    // HTNode是赫夫曼树结点的结构体（包含weight、parent、lchild、rchild四个字段）
    HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));

    // 初始化前n个结点（叶子结点）：
    // p指向HT的当前结点，i是循环变量，w是权值数组
    for (p = HT, i = 1; i <= n; ++i, ++p, ++w)
        // 叶子结点的权值为*w，parent/lchild/rchild初始化为0（无父/子结点）
        *p = {*w, 0, 0, 0};

    // 初始化剩余m-n个结点（分支结点）：权值、父、左右子均初始化为0
    for (; i <= m; ++i, ++p) *p = {0, 0, 0, 0};

    // 构造赫夫曼树的核心循环：生成n-1个分支结点（从n+1到m）
    for (i = n + 1; i <= m; ++i) {
        // 从当前森林（前i-1个结点）中，选择权值最小的两个结点，下标存入s1、s2
        select(HT, i - 1, s1, s2);

        // 将选中的两个结点的parent设为当前分支结点i（标记为已合并）
        HT[s1].parent = i;
        HT[s2].parent = i;

        // 当前分支结点i的左孩子是s1，右孩子是s2
        HT[i].lchild = s1;
        HT[i].rchild = s2;

        // 当前分支结点i的权值 = 两个孩子结点的权值之和
        HT[i].weight = HT[s1].weight + HT[s2].weight;
    }
}

例题：

遍历二叉树

已知一棵非空二叉树 T，以二叉链表方式存储。存储结构为：

// 统计二叉树 T 中“右孩子为空”的结点个数
int CountRightNull(BiTree T)
{
    if (T == NULL) return 0;                 // 空树：0

    int cnt = (T->rchild == NULL) ? 1 : 0;   // 当前结点右孩子为空 -> +1

    // 递归统计左右子树
    return cnt + CountRightNull(T->lchild) + CountRightNull(T->rchild);
}