Chapter 3 Trees¶
§1 Preliminaries¶
1. Terminology¶
【定义】树（Tree） 是节点的集合。集合可以为空；若非空，则由以下两部分组成：
(1) 一个特殊节点r，称为根（Root）；
(2) 零个或多个非空子树T₁, T₂, …, Tₖ，每个子树的根都通过一条有向边与r相连。
注意：
子树之间不能相互连接，因此树中的每个节点都是某个子树的根。
包含
N个节点的树有N-1条边。通常将根节点画在顶部。
-
节点的度（Degree of a Node）：节点拥有的子树个数。例如，若节点A有3个子树，则
degree(A)=3；叶子节点的度为0。 -
树的度（Degree of a Tree）：树中所有节点的度的最大值。例如，若树中最大节点度为3，则该树的度为3。
-
父节点（Parent）：拥有子树的节点。
-
子节点（Children）：父节点的子树的根节点。
-
兄弟节点（Siblings）：同一父节点的所有子节点。
-
叶子节点（Leaf / Terminal Node）：度为0的节点（没有子节点）。
-
路径（Path from n₁ to nₖ）：唯一的节点序列
n₁, n₂, …, nₖ，满足对于1 ≤ i < k，nᵢ是nᵢ₊₁的父节点。 -
路径长度（Length of Path）：路径上的边数。
-
节点的深度（Depth of nᵢ）：从根节点到
nᵢ的唯一路径的长度。规定Depth(Root) = 0。 -
节点的高度（Height of nᵢ）：从
nᵢ到某个叶子节点的最长路径的长度。规定Height(Leaf) = 0。 -
树的高度/深度（Height / Depth of a Tree）：等于根节点的高度，也等于最深叶子节点的深度。
-
祖先节点（Ancestors of a Node）：从该节点向上到根节点的路径上的所有节点。
-
后代节点（Descendants of a Node）：该节点的所有子树中的节点。
2. Implementation¶
List Representation¶
用嵌套列表表示树的层次结构，示例：
- 空树：()
-
仅根节点A：
(A) -
根A有子节点B、C、D：
(A (B, C, D)) -
完整示例：
(A (B (E (K, L), F), C (G), D (H (M), I, J)))
缺陷：每个节点的大小取决于其分支数，结构不统一，实现复杂。
FirstChild-NextSibling Representation¶
每个节点包含三个固定字段，所有节点结构统一：
- Element：存储节点元素
-
FirstChild：指向第一个子节点 -
NextSibling：指向下一个兄弟节点
特点： - 表示不唯一，因为子节点的顺序可以任意
- 将该结构顺时针旋转45°，即可得到二叉树的结构（
FirstChild对应左孩子，NextSibling对应右孩子）
§2 Binary Trees¶
【定义】二叉树（Binary Tree） 是一种特殊的树，其中每个节点最多有两个子节点。
注意： - 普通树中孩子节点的顺序无关紧要，但二叉树中左孩子（Left Child）和右孩子（Right Child）是不同的。例如，只有左孩子的节点和只有右孩子的节点是两棵不同的二叉树。
Special Types of Binary Trees¶
-
左斜树（Skewed to the Left）：所有节点都只有左子树的二叉树。
-
右斜树（Skewed to the Right）：所有节点都只有右子树的二叉树。
-
完全二叉树（Complete Binary Tree）：所有叶子节点都位于最后两层，且最后一层的叶子节点都靠左排列的二叉树。
Properties of Binary Trees¶
- 第
i层（i ≥ 1）的最大节点数为2ⁱ⁻¹。 - 深度为
k（k ≥ 1）的二叉树的最大节点数为2ᵏ - 1。 - 对于任意非空二叉树，若
n₀为叶子节点数，n₂为度为2的节点数，则n₀ = n₂ + 1。
证明： 设
n₁为度为1的节点数，n为总节点数，则：n = n₀ + n₁ + n₂（总节点数=叶子数+度1节点数+度2节点数） 设B为总边数，则n = B + 1（树的基本性质） 所有边都来自度1或度2的节点，因此B = n₁ + 2n₂联立得：n₀ + n₁ + n₂ = n₁ + 2n₂ + 1，化简得n₀ = n₂ + 1
Expression Trees (Syntax Trees)¶
表达式树是用于表示算术表达式的二叉树，其中： - 叶子节点存储操作数（Operand）
- 非叶子节点存储运算符（Operator）
Example¶
中缀表达式 A + B * C / D 对应的表达式树：
+
/ \
A /
/ \
* D
/ \
B C
Constructing an Expression Tree from Postfix Expression¶
通过后缀表达式（逆波兰表示法）构建表达式树的算法： 1. 创建一个空栈 2. 遍历后缀表达式的每个token： - 若为操作数，创建一个单节点树并压入栈
- 若为运算符，弹出栈顶的两个树（先弹出的为右子树，后弹出的为左子树），创建以该运算符为根的新树，将新树压入栈
- 遍历结束后，栈中仅剩一个树，即为最终的表达式树
示例：中缀表达式
(a + b) * (c * (d + e))对应的后缀表达式为a b + c d e + * *，构建后得到完整的表达式树。
Tree Traversals¶
树的遍历：访问树中的每个节点恰好一次。二叉树有四种常用遍历方式：
1. Preorder Traversal（前序遍历）¶
访问顺序：根节点 → 左子树 → 右子树
void preorder(tree_ptr tree) {
if (tree) {
visit(tree);
preorder(tree->Left);
preorder(tree->Right);
}
}
2. Inorder Traversal（中序遍历）¶
访问顺序：左子树 → 根节点 → 右子树
// 递归实现
void inorder(tree_ptr tree) {
if (tree) {
inorder(tree->Left);
visit(tree->Element);
inorder(tree->Right);
}
}
// 迭代实现（借助栈）
void iter_inorder(tree_ptr tree) {
Stack S = CreateStack(MAX_SIZE);
for (;;) {
for (; tree; tree = tree->Left)
Push(tree, S);
tree = Top(S); Pop(S);
if (!tree) break;
visit(tree->Element);
tree = tree->Right;
}
}
3. Postorder Traversal（后序遍历）¶
访问顺序：左子树 → 右子树 → 根节点
void postorder(tree_ptr tree) {
if (tree) {
postorder(tree->Left);
postorder(tree->Right);
visit(tree);
}
}
4. Levelorder Traversal（层序遍历）¶
访问顺序：按层次从上到下、同一层从左到右访问节点
void levelorder(tree_ptr tree) {
enqueue(tree);
while (queue is not empty) {
visit(T = dequeue());
if (T->Left) enqueue(T->Left);
if (T->Right) enqueue(T->Right);
}
}
Example: Traversal Results of Expression Tree¶
对于表达式 A + B * C / D 的表达式树：
- 中序遍历：A + B * C / D（还原为中缀表达式）
-
后序遍历：
A B C * D / +（后缀表达式） -
前序遍历：
+ A / * B C D（前缀表达式）
Applications of Tree Traversals¶
1. Hierarchical File System Directory Listing¶
按层次缩进打印文件系统目录结构，使用前序遍历实现：
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);
}
}
// 对外接口
void ListDirectory(DirOrFile D) {
ListDir(D, 0);
}
时间复杂度：
T(N) = O(N)，N为文件和目录的总数
2. Calculating the Size of a Directory¶
计算目录及其所有子文件、子目录的总大小，使用后序遍历实现：
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;
}
时间复杂度：
T(N) = O(N)
Threaded Binary Trees（线索二叉树）¶
Why We Need Threaded Binary Trees?¶
-
一棵有
n个节点的二叉树共有2n个链接（每个节点有左、右两个指针） -
其中有
n+1个链接是NULL（空指针），造成空间浪费 -
线索二叉树将这些空指针替换为线索（Thread），指向节点的中序前驱或后继，从而简化遍历操作，无需使用栈
Threading Rules¶
- 若节点的左指针
Left为空，则将其替换为指向该节点的中序前驱（Inorder Predecessor）的线索 - 若节点的右指针
Right为空，则将其替换为指向该节点的中序后继（Inorder Successor）的线索 - 必须添加一个头节点（Head Node），其左孩子指向二叉树的第一个节点，避免出现悬空线索
Node Structure Definition (C)¶
typedef struct ThreadedTreeNode *PtrToThreadedNode;
typedef PtrToThreadedNode ThreadedTree;
typedef struct ThreadedTreeNode {
int LeftThread; // 若为TRUE，则Left是线索，不是孩子指针
ThreadedTree Left;
ElementType Element;
int RightThread; // 若为TRUE，则Right是线索，不是孩子指针
ThreadedTree Right;
} ThreadedTreeNode;
§3 The Search Tree ADT -- Binary Search Trees¶
1. Definition¶
【定义】二叉搜索树（Binary Search Tree, BST） 是一种二叉树，可以为空。若非空，则满足以下性质： 1. 每个节点有一个唯一的整数键值（Key） 2. 任意非空左子树中的所有键值都小于该子树根节点的键值 3. 任意非空右子树中的所有键值都大于该子树根节点的键值 4. 左子树和右子树也都是二叉搜索树
2. ADT¶
-
数据对象：零个或多个元素的有限有序列表
-
核心操作集：
SearchTree MakeEmpty(SearchTree T);：将树置空Position Find(ElementType X, SearchTree T);：查找键值为X的节点Position FindMin(SearchTree T);：查找键值最小的节点Position FindMax(SearchTree T);：查找键值最大的节点SearchTree Insert(ElementType X, SearchTree T);：插入键值为X的节点SearchTree Delete(ElementType X, SearchTree T);：删除键值为X的节点ElementType Retrieve(Position P);：获取节点P的键值
3. Implementations¶
Find Operation¶
查找键值为X的节点，从根节点开始比较： - 若X < 当前节点键值，递归查找左子树
-
若X > 当前节点键值，递归查找右子树
-
若相等，返回当前节点；若树为空，返回NULL
// 递归实现
Position Find(ElementType X, SearchTree T) {
if (T == NULL)
return NULL; // 未找到
if (X < T->Element)
return Find(X, T->Left);
else if (X > T->Element)
return Find(X, T->Right);
else
return T; // 找到
}
// 迭代实现
Position Iter_Find(ElementType X, SearchTree T) {
while (T) {
if (X == T->Element)
return T;
if (X < T->Element)
T = T->Left;
else
T = T->Right;
}
return NULL;
}
时间复杂度：
O(d)，d为节点X的深度
FindMin and FindMax Operations¶
-
最小节点：二叉搜索树中最左边的节点
-
最大节点：二叉搜索树中最右边的节点
// 递归实现FindMin
Position FindMin(SearchTree T) {
if (T == NULL)
return NULL;
else if (T->Left == NULL)
return T;
else
return FindMin(T->Left);
}
// 迭代实现FindMax
Position FindMax(SearchTree T) {
if (T != NULL)
while (T->Right != NULL)
T = T->Right;
return T;
}
时间复杂度：
O(d)，d为树的深度
Insert Operation¶
插入键值为X的节点，步骤： 1. 从根节点开始查找X的插入位置 2. 若X已存在，不做任何操作 3. 若不存在，在查找路径的最后一个节点下创建新节点
SearchTree Insert(ElementType X, SearchTree T) {
if (T == NULL) { // 创建新节点
T = malloc(sizeof(struct TreeNode));
if (T == NULL)
FatalError("Out of space!!!");
else {
T->Element = X;
T->Left = T->Right = NULL;
}
}
else if (X < T->Element)
T->Left = Insert(X, T->Left);
else if (X > T->Element)
T->Right = Insert(X, T->Right);
// X已存在，不做操作
return T;
}
时间复杂度：
O(d)，d为插入节点的深度
Delete Operation¶
删除键值为X的节点，分三种情况： 1. 删除叶子节点：直接将其父节点的对应指针置为NULL 2. 删除度为1的节点：用其唯一的子节点替换该节点 3. 删除度为2的节点： - 用其左子树中的最大节点或右子树中的最小节点替换该节点
- 删除替换节点（该节点度最多为1）
SearchTree Delete(ElementType X, SearchTree T) {
Position TmpCell;
if (T == NULL)
Error("Element not found");
else if (X < T->Element)
T->Left = Delete(X, T->Left);
else if (X > T->Element)
T->Right = Delete(X, T->Right);
else { // 找到要删除的节点
if (T->Left && T->Right) { // 度为2的节点
// 用右子树的最小节点替换
TmpCell = FindMin(T->Right);
T->Element = TmpCell->Element;
T->Right = Delete(T->Element, T->Right);
}
else { // 度为1或0的节点
TmpCell = T;
if (T->Left == NULL)
T = T->Right;
else if (T->Right == NULL)
T = T->Left;
free(TmpCell);
}
}
return T;
}
时间复杂度：
O(h)，h为树的高度
Lazy Deletion（惰性删除）¶
当删除操作不频繁时，可以使用惰性删除： - 为每个节点添加一个标志位，标记该节点是否被删除
-
删除节点时，仅将标志位置为"已删除"，不实际释放内存
-
重新插入已删除的键值时，只需将标志位置为"活跃"，无需重新申请内存
注意：当删除节点数与活跃节点数相当时，会显著影响操作效率
4. Average-Case Analysis¶
二叉搜索树的高度取决于元素的插入顺序：
- 最优情况：插入顺序使树保持平衡，高度为O(log N)
- 最坏情况：按升序或降序插入，形成斜树，高度为
O(N)
示例：插入元素
1,2,3,4,5,6,7- 插入顺序4,2,1,3,6,5,7：树高为2（平衡树）
- 插入顺序
1,2,3,4,5,6,7：树高为6（右斜树）