树

树是一种一对多的非线性数据结构。前面学的数组、链表、栈、队列都是"一对一"的线性表，而树是一个节点可以连多个子节点。

一、树

1.1 树的定义

树：由 n（n ≥ 0）个节点组成的有限集合。当 n = 0 时叫空树；否则有一个根节点，其余节点分成若干互不相交的子树。

graph TD  
 A --> B 
 A --> C 
 B --> D 
 B --> E 
 C --> F 
 D --> G 
 D --> H  

• 最上面 A 是根节点；
• B、C 是 A 的两棵子树；
• G、H、E、F 没有子节点，是叶子节点。

1.2 名词术语

对照上面这棵树：

二、二叉树

2.1 二叉树的定义

二叉树：每个节点最多只有两个子节点，且分左、右，左右不能随意颠倒。

graph TD  
 A --> B 
 A --> C 
 B --> D 
 B --> E 
 C --> F 
 C --> G  

💡 注意：二叉树的"左孩子"和"右孩子"是不同位置。即使只有一个孩子，也要分清是左还是右。

2.2 二叉树的五种基本形态

（1）空树：没有节点。

（2）只有根节点：一个孤立的节点。

（3）只有左孩子：根有一个左孩子，没有右孩子。

（4）只有右孩子：根有一个右孩子，没有左孩子。

（5）左右孩子都有：根同时有左孩子和右孩子。

💡 这五种形态的要点：左右孩子是不同位置。只有左孩子和只有右孩子，是两种不同的二叉树。

2.3 节点编号

把二叉树按层从上到下、从左到右编号（根是 1 号）：

graph TD  
 1 --> 2 
 1 --> 3 
 2 --> 4 
 2 --> 5 
 3 --> 6 
 3 --> 7  

编号为 i 的节点，满足：

例：

节点 2：左孩子 = 4（2×2），右孩子 = 5（2×2+1），父亲 = 1（2/2）  
节点 5：父亲 = 2（5/2 向下取整）  
节点 7：父亲 = 3（7/2 向下取整）  

💡 这个性质对完全二叉树 / 满二叉树成立（因为编号连续、中间不断号）。它是堆（后面会学）的基础——堆就靠这个性质用数组顺序存储，快速找父子。

2.4 最多节点数量计算

• 第 i 层最多有 2^{i-1} 个节点（根是第 1 层）；
• 深度为 k 的二叉树，最多有 2^k - 1 个节点（也就是满二叉树）。

规律：每一层最多是上一层的 2 倍；深度 k 最多 2^k - 1 个节点。

2.5 满二叉树与完全二叉树

满二叉树：每一层都填满，节点数 = 2^k - 1。

graph TD  
 A --> B 
 A --> C 
 B --> D 
 B --> E 
 C --> F 
 C --> G  

完全二叉树：除了最后一层，其他层都满；最后一层的节点靠左排列。

graph TD  
 A --> B 
 A --> C 
 B --> D 
 B --> E 
 C --> F  

反例（不是完全二叉树，最后一层 C 的右孩子位置空了）：

graph TD  
 A --> B 
 A --> C 
 B --> D 
 B --> E 
 C --> G  

💡 判断技巧：把完全二叉树按层编号（从上到下、从左到右），编号是连续的 1、2、3、…，中间不跳号。这也是它能用数组顺序存储的原因。

「靠左」和「空洞」用 ASCII 图更容易看出来（Mermaid 会自动布局，反而看不出位置关系）。

三、二叉树遍历

3.1 三种遍历方式

前序（先序）、中序、后序的区别，只在于根节点的访问时机：

💡 记住："前中后"指的是"根"在什么时候访问。左孩子永远在右孩子之前。

3.2 以三个节点为例

graph TD  
 根A --> 左B 
 根A --> 右C  

3.3 更多节点的遍历

树（A 是根，B、C 是左右孩子，B 有 D、E，C 有 F）：

graph TD  
 A --> B 
 A --> C 
 B --> D 
 B --> E 
 C --> F  

前序遍历（根左右）：每到一棵子树，先访问根，再去左边，最后去右边。

节点里括起来的数字，是「第几个访问到」：

graph TD  
 A["A (1)"] 
 B["B (2)"] 
 C["C (5)"] 
 D["D (3)"] 
 E["E (4)"] 
 F["F (6)"] 
 A --> B 
 A --> C 
 B --> D 
 B --> E 
 C --> F  

结果：A B D E C F

中序遍历（左根右）：先去左边，再访问根，最后去右边。

graph TD  
 A["A (4)"] 
 B["B (2)"] 
 C["C (5)"] 
 D["D (1)"] 
 E["E (3)"] 
 F["F (6)"] 
 A --> B 
 A --> C 
 B --> D 
 B --> E 
 C --> F  

结果：D B E A C F

后序遍历（左右根）：先去左边，再去右边，最后访问根。

graph TD  
 A["A (6)"] 
 B["B (3)"] 
 C["C (5)"] 
 D["D (1)"] 
 E["E (2)"] 
 F["F (4)"] 
 A --> B 
 A --> C 
 B --> D 
 B --> E 
 C --> F  

结果：D E B F C A

💡 手算技巧：前序先写根，中序把根夹在中间，后序把根放最后，左右子树各自同样处理。

3.4 根据遍历结果还原二叉树

规则：

• 已知 前序 + 中序，或 后序 + 中序，可以唯一还原二叉树；
• 只有 前序 + 后序，不能唯一确定（分不清左右，除非是满二叉树）。

还原方法（以前序 + 中序为例）：

1. 前序的第一个节点是根；
2. 在中序里找到根，根左边是左子树，右边是右子树；
3. 左右子树各自递归同样的步骤。

例：前序 A B D E C F，中序 D B E A C F

第 1 步：确定整棵树的根

前序第一个是 A，所以 A 是整棵树的根。在中序里找到 A，A 左边是左子树，右边是右子树：

中序：D B E | A | C F  
根:A   
左子树：D B E 
右子树：C F  

这一步只确定了根 A，左右子树还是没拆开的"一坨"：

graph TD  
 A --> L["左子树 D B E"] 
 A --> R["右子树 C F"]  

第 2 步：还原左子树

左子树的前序是 B D E，中序是 D B E。前序第一个是 B，所以 B 是左子树的根。中序里 B 左边是 D、右边是 E：

中序：D | B | E  
根 B  
B 的左子树：D      
B 的右子树：E  

左子树已经拆开（B 是根，D 左、E 右），右子树还是一坨：

graph TD  
 A --> B 
 A --> R["右子树 C F"] 
 B --> D 
 B --> E  

第 3 步：还原右子树

右子树的前序是 C F，中序是 C F。前序第一个是 C，所以 C 是右子树的根。中序里 C 右边是 F：

中序：C | F  
根 C 
C 的右子树：F
（C 没有左孩子）  

全部还原完毕：

graph TD  
 A --> B 
 A --> C 
 B --> D 
 B --> E 
 C --> F  

💡 关键：每一步都「前序第一个定根，中序切左右子树」，再对左右子树递归重复。

四、哈夫曼树

4.1 带权路径长度（WPL）

• 路径长度：从根到某个节点的边数；
• 带权路径长度 WPL：所有叶子节点的 权值 × 路径长度 之和。

graph TD  
 A --> B 
 A --> C 
 B --> D[2] 
 B --> E[3] 
 C --> F[4] 
 C --> G[5]  

叶子 2、3 在第 3 层（路径长度 2），4、5 在第 3 层（路径长度 1）：

WPL = 2×2 + 3×2 + 4×2 + 5×2 = 4 + 6 + 8 + 10 = 28  

💡 哈夫曼树：在叶子权值固定的前提下，让 WPL 最小的二叉树。做法是权值小的放得深、权值大的放得浅。

4.2 构建哈夫曼树

方法：每次挑最小的两个节点合并成一个新节点，直到只剩一个根。

例：叶子权值 2, 3, 5, 7, 9

第 1 步：最小两个 2、3 合并成 5
第 2 步：剩下 5(新)、5、7、9，最小两个 5、5 合并成 10
第 3 步：剩下 7、9、10，最小两个 7、9 合并成 16
第 4 步：剩下 10、16 合并成 26

最终哈夫曼树：

graph TD  
 26 --> 10 
 26 --> 16 
 10 --> 5a[5] 
 10 --> 5b[5] 
 16 --> 7 
 16 --> 9 
 5a --> 2 
 5a --> 3  

💡 口诀：每次挑两个最小的，合并起来，再放回去，重复到只剩一个。

（图里两个 5 节点用 5a、5b 区分，显示出来都是「5」。）

4.3 字母频率与哈夫曼编码

把字母出现频率当作权值，构建哈夫曼树，就得到变长编码——频率高的字母编码短，频率低的字母编码长，总长度最短。

例：字母频率 A=5, B=7, C=2, D=4, E=9

① 最小两个 C(2)、D(4) 合并成 6
② 最小两个 A(5)、6 合并成 11
③ 最小两个 B(7)、E(9) 合并成 16
④ 11、16 合并成 27

graph TD  
 27 --> 11 
 27 --> 16 
 11 --> A[5] 
 11 --> 6 
 16 --> B[7] 
 16 --> E[9] 
 6 --> C[2] 
 6 --> D[4]  

给边定方向（左 0 右 1），从根走到叶子，沿途数字就是该字母的编码：

💡 频率高的 B、E、A 编码短，频率低的 C、D 编码长。

答案不唯一，但总长度一致：

1. 左右 0/1 互换：把"左 0 右 1"改成"左 1 右 0"，所有编码的 0、1 互换，编码变了，但每个编码长度不变；
2. 相同权值顺序不同：合并时如果两个权值相同，谁在左谁在右可以换，树形不同，但 WPL 相同。

所以哈夫曼编码的具体结果可能不同，但总编码长度（WPL）一定相同，这是唯一的。

4.4 编码和解码

编码：把每个字母换成它的哈夫曼编码。

编码表：A=01, B=10, C=000, D=001, E=11  
  
要编码的文本： A B E D → 011011001

解码：从根开始，0 走左、1 走右，走到叶子就输出字母，再回到根继续。

解码串：011011001  
  
① 01 → A（走到叶子 A）  
② 10 → B
③ 11 → E
④ 001 → D  
结果：A B E D  

💡 哈夫曼编码是前缀编码：任何一个编码都不是另一个编码的前缀，所以解码时不会歧义，读一遍就能唯一还原。

五、易错点汇总