二叉树
这一页整理 Ch04 Binary Trees。重点是树的基本术语、树的实现、二叉树、表达式树、树遍历、目录递归，以及线索二叉树。
1. 树 Tree
树是一组结点的集合。这个集合可以为空；如果非空，则由下面两部分组成：
- 一个特殊结点
r，称为根结点（root）。 - 零个或多个非空子树
T1, T2, ..., Tk，每棵子树的根都由一条从r出发的边连接。
树的递归定义很重要：一棵树由根和若干棵子树组成，而每棵子树本身又是一棵树。
注意：
- 子树之间不能互相连接。
- 一棵有
N个结点的树有N - 1条边。 - 通常画树时，根在最上面。
2. 树的基本术语
假设有一棵树：
结点的度
一个结点的 degree 是它的子树个数，也就是孩子个数。
例如：
树的度
树的 degree 是所有结点 degree 的最大值。
上面这棵树中，A 和 D 都有 3 个孩子，所以：
父亲、孩子、兄弟
- parent：有子树的结点。
- children：某个 parent 的子树根结点。
- siblings：同一个 parent 的孩子。
- leaf / terminal node：degree 为
0的结点，也就是叶子。
例如：
A是B, C, D的 parent。B, C, D是 siblings。F, G, I, J, K, L, M都是 leaves。
度数和叶子数公式
对任意非空树，边数有两种数法。
第一种：有 n 个结点的树有：
条边。
第二种：把所有结点的孩子数加起来，也就是把所有结点的 degree 加起来。
如果 ni 表示 degree 为 i 的结点个数，那么：
总节点数是：
两式相减，可以得到普通树常用公式：
也就是：
例题：树的 degree 和叶子数
Given a tree of degree 3. Suppose that there are 3 nodes of degree 2 and 2 nodes of degree 3. Then the number of leaf nodes must be ___.
A. 5
B. 6
C. 7
D. 8
点拨：普通树用公式 n0 = 1 + n2 + 2n3。这里 n2 = 3，n3 = 2。
答案：
3. 路径、深度和高度
路径 Path
从 n1 到 nk 的路径是一串结点：
其中每个 ni 都是 n(i+1) 的 parent。
树中从根到任意结点的路径是唯一的。
路径长度是路径上的边数。
深度 Depth
结点 x 的 depth 是从根到 x 的路径长度。
例如上图：
高度 Height
结点 x 的 height 是从 x 到叶子的最长路径长度。
例如：
树的高度就是根结点的高度，也等于最深叶子的深度。
Ancestors 和 Descendants
- ancestors：从当前结点往上到根路径上的所有结点。
- descendants：当前结点所有子树中的结点。
4. 树的普通表示为什么麻烦
如果每个结点直接保存所有孩子指针，那么不同结点的孩子数不同，结点结构就很难统一。
例如：
如果给每个结点都开很多指针，会浪费空间。
如果每个结点结构大小不一样，实现又会很麻烦。
这就引出一种很重要的统一表示法：FirstChild-NextSibling。
5. FirstChild-NextSibling 表示法
每个结点只保留两个指针：
含义：
FirstChild：指向第一个孩子。NextSibling：指向右边下一个兄弟。
例如：
可以理解成：
A.FirstChild = B
B.NextSibling = C
C.NextSibling = D
B.FirstChild = E
E.NextSibling = F
C.FirstChild = G
这个表示法的好处是：无论树的度是多少，每个结点都只需要两个指针。
注意：普通树中孩子之间没有固定顺序，所以 FirstChild-NextSibling 表示不唯一；孩子顺序不同，表示也不同。
6. 二叉树 Binary Tree
二叉树是每个结点最多有两个孩子的树。
在二叉树中，这两个孩子有明确含义：
- left child
- right child
常见结点结构：
二叉树和普通树的区别不只是“最多两个孩子”。
二叉树的左右孩子有顺序，左和右不能随便交换。
7. 二叉树补充性质
在普通树里，孩子之间的顺序通常不重要。
但在二叉树里，左孩子和右孩子是不同的。
例如：
这两棵是不同的二叉树。
8. 斜树和完全二叉树
斜树
如果每个结点都只有左孩子，或者都只有右孩子，就会形成斜树。
斜树虽然是二叉树，但形状接近链表。
很多二叉树操作的复杂度会退化到 O(N)。
完全二叉树
完全二叉树（complete binary tree）可以这样定义：
一棵有
n个结点、高度为h的二叉树是完全二叉树，当且仅当它的结点正好对应高度为h的满二叉树中按层序编号1到n的那些结点。
更直观地说：
- 除最后一层外，前面的层都是满的。
- 最后一层可以不满，但必须从左到右连续填充，不能中间空着。
完全二叉树比较“矮”，高度大约是 O(log N)。
9. 二叉树结点数量性质
每层最多结点数
如果根在第 1 层，那么第 i 层最多有：
个结点。
深度为 k 的二叉树最多结点数
深度为 k 的二叉树最多有：
个结点。
这里课件采用的是“第 1 层为根，深度 k 表示有 k 层”的写法。
如果你用“root depth = 0”的定义，公式会相应写成高度为 h 最多有：
个结点。
10. 叶子数和二度结点数
对任意非空二叉树：
其中：
n0：叶子结点数，即 degree 为0的结点数。n1：degree 为1的结点数。n2：degree 为2的结点数。
证明：
总节点数：
树有 n - 1 条边。
另一方面，所有边都从父结点连向孩子：
所以：
代入 n = n0 + n1 + n2：
这个公式很常考，记住“叶子数 = 二度结点数 + 1”。
11. 普通树转二叉树
FirstChild-NextSibling 表示法天然可以看成一棵二叉树：
FirstChild变成LeftNextSibling变成Right
也就是：
可视化：
这也是课件里说“把 FirstChild-NextSibling 树顺时针旋转 45°”的直觉来源。
普通树和二叉树遍历对应关系
普通树 T 转成 FirstChild-NextSibling 二叉树 BT 后，有两个常用对应关系：
为什么 T 的 postorder 对应 BT 的 inorder？
在普通树中，postorder 是：
转成 BT 后：
- 左孩子表示 first child。
- 右孩子表示 next sibling。
所以对 BT 做 inorder：
正好对应普通树里“先处理当前结点的孩子们，再处理当前结点，然后处理兄弟”。
例题：普通树转二叉树后的遍历
If a general tree T is converted into a binary tree BT, then which of the following BT traversals gives the same sequence as that of the post-order traversal of T?
A. Pre-order traversal
B. In-order traversal
C. Post-order traversal
D. Level-order traversal
点拨：普通树转 FirstChild-NextSibling 二叉树后，普通树的 postorder 对应二叉树的 inorder。
答案：
12. 表达式树 Expression Tree
表达式树用树表示表达式：
- 叶子结点通常是操作数。
- 内部结点通常是运算符。
例如中缀表达式：
对应表达式树可以看成：
这棵树的含义是：
表达式树和遍历关系非常密切：
| 遍历 | 得到的表达式 |
|---|---|
| inorder | 中缀表达式 |
| preorder | 前缀表达式 |
| postorder | 后缀表达式 |
对上面这棵树：
13. 用后缀表达式构造表达式树
给定后缀表达式：
用栈构造表达式树：
- 遇到操作数：创建单结点树，入栈。
- 遇到运算符：弹出两棵树，作为左右子树，创建新树再入栈。
注意弹出顺序：
- 先弹出的是右子树。
- 后弹出的是左子树。
例如遇到 +，如果先弹出 b，再弹出 a，则新树是：
最后栈中唯一的树就是表达式树。
14. 树遍历
遍历就是访问树中每个结点一次，且只访问一次。
常见遍历：
- preorder：先序遍历。
- inorder：中序遍历，主要用于二叉树。
- postorder：后序遍历。
- levelorder：层序遍历。
15. 先序和后序遍历
Preorder
顺序：
伪代码：
void preorder(tree_ptr tree) {
if (tree) {
visit(tree);
for (each child C of tree) {
preorder(C);
}
}
}
Postorder
顺序：
伪代码：
void postorder(tree_ptr tree) {
if (tree) {
for (each child C of tree) {
postorder(C);
}
visit(tree);
}
}
16. 二叉树中序遍历
中序遍历只对二叉树有自然定义：
递归代码：
void inorder(tree_ptr tree) {
if (tree) {
inorder(tree->Left);
visit(tree->Element);
inorder(tree->Right);
}
}
对表达式树来说，中序遍历通常对应中缀表达式。
但严格输出时，有时需要补括号来避免歧义。
17. 中序遍历的非递归写法
递归本质上使用系统栈。
所以中序遍历也可以手动用栈写出来。
核心思想：
- 一路向左走，把沿途结点压栈。
- 左边走到底后，弹出栈顶并访问。
- 转向它的右子树。
- 重复以上过程。
代码：
void iter_inorder(tree_ptr tree) {
Stack S = CreateStack(MAX_SIZE);
for (;;) {
for (; tree; tree = tree->Left) {
Push(tree, S);
}
if (IsEmpty(S)) {
break;
}
tree = Top(S);
Pop(S);
visit(tree->Element);
tree = tree->Right;
}
}
课件中的伪代码在 Top(S) 前需要保证栈非空；否则空栈取顶会出错。
18. 层序遍历 Levelorder
层序遍历按照从上到下、从左到右访问结点。
它需要队列：
void levelorder(tree_ptr tree) {
enqueue(tree);
while (queue is not empty) {
T = dequeue();
visit(T);
for (each child C of T) {
enqueue(C);
}
}
}
可视化：
队列保证：先看到的结点先被访问，所以可以一层一层推进。
19. 目录树例子
文件系统可以看成树：
- 目录是内部结点。
- 文件通常是叶子。
- 子目录和文件是某个目录的孩子。
列出目录
目录列表可以用先序遍历：先打印当前目录/文件，再递归打印孩子。
static void ListDir(DirOrFile D, int Depth) {
if (D is a legitimate entry) {
PrintName(D, Depth);
if (D is a directory) {
for (each child C of D) {
ListDir(C, Depth + 1);
}
}
}
}
Depth 用来控制缩进：
注意：Depth 是内部变量，不应该暴露给用户。
可以再包一层接口：
复杂度：
因为每个目录或文件只访问一次。
计算目录大小
目录大小可以用后序遍历：先算完所有孩子，再汇总当前目录。
static int SizeDir(DirOrFile D) {
int TotalSize = 0;
if (D is a legitimate entry) {
TotalSize = FileSize(D);
if (D is a directory) {
for (each child C of D) {
TotalSize += SizeDir(C);
}
}
}
return TotalSize;
}
复杂度同样是：
因为每个结点只处理一次。
20. 二叉树中的空指针数量
线索二叉树前有一个经典问题：一棵有 n 个结点的二叉树中，有多少个空指针？
每个结点有两个指针域：
所以总指针域数量是：
一棵有 n 个结点的树有 n - 1 条边。每条边会占用一个非空指针。
所以非空指针有：
空指针数量为：
这说明普通二叉树里有很多空指针域。
线索二叉树就是想利用这些空指针。
二叉树结点数例题
例题：二叉树是否存在
There exists a binary tree with 2016 nodes in total, and with 16 nodes having only one child.
判断这句话是否正确。
点拨：二叉树满足 n0 = n2 + 1，且 n = n0 + n1 + n2。已知 n = 2016，n1 = 16。
答案：
n2 = 999.5 不是整数，所以这样的二叉树不存在。原命题是 false。
21. 线索二叉树 Threaded Binary Tree
线索二叉树把部分空指针替换成遍历意义上的前驱/后继指针。
以中序线索二叉树为例：
- 如果
Tree->Left为空，就让它指向中序前驱。 - 如果
Tree->Right为空，就让它指向中序后继。
规则：
Rule 1: Left 为空时，替换为 inorder predecessor
Rule 2: Right 为空时，替换为 inorder successor
Rule 3: 不能有 loose threads，所以通常需要 head node
22. 线索二叉树结点结构
因为 Left 和 Right 有时是真孩子，有时是线索，所以需要标记位：
typedef struct ThreadedTreeNode *ThreadedTree;
struct ThreadedTreeNode {
int LeftThread;
ThreadedTree Left;
ElementType Element;
int RightThread;
ThreadedTree Right;
};
含义：
LeftThread == TRUE：Left是线索，指向中序前驱。LeftThread == FALSE：Left是真正的左孩子。RightThread == TRUE：Right是线索，指向中序后继。RightThread == FALSE：Right是真正的右孩子。
线索二叉树的目的：让中序遍历更方便，减少对递归栈或显式栈的依赖。
23. 考点速记
| 考点 | 必会内容 |
|---|---|
| 树定义 | 根 + 若干互不相交子树 |
| 边数 | N 个结点的树有 N - 1 条边 |
| degree(node) | 结点孩子数 |
| degree(tree) | 最大结点度 |
| depth | 根到该结点的路径长度 |
| height | 该结点到叶子的最长路径长度 |
| FirstChild-NextSibling | 普通树统一成两个指针 |
| 二叉树 | 每个结点最多两个孩子，左右有区别 |
| 完全二叉树 | 层序编号对应满二叉树的 1..n 位置 |
| 每层最多结点 | 第 i 层最多 \(2^{i-1}\) 个 |
| 深度为 k 最多结点 | \(2^k - 1\) |
| 叶子公式 | n0 = n2 + 1 |
| 表达式树 | 叶子是操作数，内部结点是运算符 |
| preorder | 根 -> 子树 |
| inorder | 左 -> 根 -> 右 |
| postorder | 子树 -> 根 |
| levelorder | 用队列逐层访问 |
| 目录列表 | 先序思想 |
| 目录大小 | 后序思想 |
| 空指针数量 | n + 1 |
| 线索二叉树 | 空指针改成前驱/后继线索 |
24. 易错点
- 树可以为空，但非空树必须有 root。
- depth 从根往下数，height 从结点往叶子方向数。
- 叶子的 height 是
0，不是1。 - 普通树孩子顺序不唯一，FirstChild-NextSibling 表示也不唯一。
- 二叉树左右孩子不能随便交换。
- BST 前的二叉树性质属于二叉树基础，不依赖搜索树。
- 完全二叉树最后一层必须从左到右连续填充。
- 后缀表达式构造表达式树时，先弹出的是右子树。
- 层序遍历用队列，不是栈。
- 中序遍历主要是二叉树概念，普通多叉树没有唯一自然中序。
- 线索指针不是孩子指针，必须用
LeftThread/RightThread区分。