RootStack

06_树与二叉树

27分钟阅读

树与二叉树 (Tree & Binary Tree)

title: ""

章节概述

树（Tree）是一种层次化的非线性数据结构，每个节点可以有零个或多个子节点。二叉树是
最常见的树结构变体，每个节点最多有两个子节点。树在计算机科学中无处不在——文件系统、
数据库索引、编译器的抽象语法树、网络路由表等。

本节侧重底层实现与内存理解，与 CPP教程对应章节 形成互补——CPP教程侧重 std::set/std::map（基于红黑树）的STL使用、迭代器语义和算法，本教程侧重手动实现二叉搜索树和AVL树的插入/删除/旋转，深刻理解树节点间的指针关系。

在CPP教程中对应章节侧重 std::set/std::map 的 STL 用法与红黑树特性，本节侧重手动实现 BST 和 AVL 树——亲手操作每个节点的 left/right 指针与旋转。

第一节: 二叉树的基本概念与结构

1.1 二叉树的节点定义

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
 
typedef struct TreeNode {
 int val;
 struct TreeNode *left;
 struct TreeNode *right;
} TreeNode;

内存布局: 每个节点在堆上独立分配。节点间通过 left 和 right 指针连接——
本质上是一个有向无环图（DAG）的特殊形式。

graph TD
 root["root 1"] --> left["2"]
 root --> right["3"]
 left --> ll["4"]
 left --> lr["5"]
 right --> rl["6"]
 right --> rr["7"]

3 个节点间的关系：root->left->val == 2，root->right->right->val == 7。

1.2 二叉树的创建与基本操作

TreeNode* treenode_create(int val) {
 TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
 if (!node) return NULL;
 node->val = val;
 node->left = NULL;
 node->right = NULL;
 return node;
}
 
// 手动构建一棵树（用于测试）
TreeNode* build_sample_tree() {
 TreeNode *root = treenode_create(1);
 root->left = treenode_create(2);
 root->right = treenode_create(3);
 root->left->left = treenode_create(4);
 root->left->right = treenode_create(5);
 root->right->left = treenode_create(6);
 root->right->right = treenode_create(7);
 return root;
}
 
// 计算节点数 —— 递归
int tree_size(const TreeNode *root) {
 if (!root) return 0;
 return 1 + tree_size(root->left) + tree_size(root->right);
}
 
// 计算高度 —— 递归
int tree_height(const TreeNode *root) {
 if (!root) return 0;
 int left_h = tree_height(root->left);
 int right_h = tree_height(root->right);
 return 1 + (left_h > right_h ? left_h : right_h);
}
 
// 释放所有节点（后序遍历）
void tree_destroy(TreeNode *root) {
 if (!root) return;
 tree_destroy(root->left);
 tree_destroy(root->right);
 free(root);
}

练习 1.2.1: 为什么树的销毁使用后序遍历？如果用前序遍历（先 free 根节点），会出现什么问题？

1.3 树遍历：递归版

三种标准遍历方式，区别在于访问根节点的时机：

// 前序遍历: 根 → 左 → 右
void preorder(const TreeNode *root) {
 if (!root) return;
 printf("%d ", root->val);
 preorder(root->left);
 preorder(root->right);
}
 
// 中序遍历: 左 → 根 → 右
void inorder(const TreeNode *root) {
 if (!root) return;
 inorder(root->left);
 printf("%d ", root->val);
 inorder(root->right);
}
 
// 后序遍历: 左 → 右 → 根
void postorder(const TreeNode *root) {
 if (!root) return;
 postorder(root->left);
 postorder(root->right);
 printf("%d ", root->val);
}

对上面 sample tree 的结果：

  • 前序: 1, 2, 4, 5, 3, 6, 7
  • 中序: 4, 2, 5, 1, 6, 3, 7
  • 后序: 4, 5, 2, 6, 7, 3, 1
graph TD
 subgraph "前序: 根→左→右"
 p1["1"] --> p2["2"] --> p4["4"]
 p2 --> p5["5"]
 p1 --> p3["3"] --> p6["6"]
 p3 --> p7["7"]
 end

第二节: 迭代遍历 —— 显式用栈

2.1 迭代前序遍历

递归遍历用系统栈，迭代版本显式用自定义栈：

// 需要包含之前实现的栈（这里用简单数组模拟）
#define MAX_STACK 1000
 
void preorder_iterative(TreeNode *root) {
 if (!root) return;
 
 TreeNode *stack[MAX_STACK];
 int top = -1;
 stack[++top] = root;
 
 while (top >= 0) {
 TreeNode *node = stack[top--];
 printf("%d ", node->val);
 
 // 先压右再压左（因为栈是LIFO）
 if (node->right) stack[++top] = node->right;
 if (node->left) stack[++top] = node->left;
 }
}

为什么先压右后压左？ 栈是后进先出——后压入的左子节点先弹出，实现”先左后右”的访问顺序。

2.2 迭代中序遍历 —— 经典的”左链入栈”法

void inorder_iterative(TreeNode *root) {
 TreeNode *stack[MAX_STACK];
 int top = -1;
 TreeNode *cur = root;
 
 while (cur || top >= 0) {
 // 沿左链一路到底
 while (cur) {
 stack[++top] = cur;
 cur = cur->left;
 }
 // 弹出栈顶并访问
 cur = stack[top--];
 printf("%d ", cur->val);
 // 转向右子树
 cur = cur->right;
 }
}

算法精髓: 先沿左子深入到底（将经过的节点压栈），然后弹出最后入栈的那个（最左深的节点），
访问后转向其右子。

sequenceDiagram
 participant traversal as 迭代中序
 participant stack as 栈

 Note over traversal: root = 1
 traversal->>stack: 沿左链: push 1, push 2, push 4
 Note over stack: [1,2,4] ← 栈顶
 traversal->>stack: pop 4 → 访问4
 Note over traversal: cur = 4->right = NULL
 traversal->>stack: pop 2 → 访问2
 Note over traversal: cur = 2->right = 5
 traversal->>stack: push 5
 traversal->>stack: pop 5 → 访问5
 Note over traversal: ...继续...

2.3 迭代后序遍历 —— 双栈法

后序遍历最复杂，经典解法使用两个栈：

void postorder_iterative(TreeNode *root) {
 if (!root) return;
 
 TreeNode *stack1[MAX_STACK], *stack2[MAX_STACK];
 int top1 = -1, top2 = -1;
 
 stack1[++top1] = root;
 while (top1 >= 0) {
 TreeNode *node = stack1[top1--];
 stack2[++top2] = node;
 
 if (node->left) stack1[++top1] = node->left;
 if (node->right) stack1[++top1] = node->right;
 }
 
 // stack2 中自顶向下恰好是后序遍历顺序
 while (top2 >= 0) {
 printf("%d ", stack2[top2--]->val);
 }
}

双栈法原理: Stack1 实现”根→右→左”的顺序（调整了压栈顺序），Stack2 将其反转得到”左→右→根”。

练习 2.3.1: 实现单栈后序遍历（更节省空间但更复杂）。

关于系统栈与自定义栈的对比——递归 vs 迭代，参见 。

第三节: 二叉搜索树（BST）

3.1 BST 定义与搜索

二叉搜索树（Binary Search Tree）满足：对任意节点，左子树所有值 ≤ 节点值 ≤ 右子树所有值。

graph TD
 bst8["8"] --> bst3["3"]
 bst8 --> bst10["10"]
 bst3 --> bst1["1"]
 bst3 --> bst6["6"]
 bst6 --> bst4["4"]
 bst6 --> bst7["7"]
 bst10 --> bst14["14"]
 bst14 --> bst13["13"]

BST 的查找等价于二分查找：每次比较决定走左子树还是右子树。

TreeNode* bst_search(TreeNode *root, int val) {
 TreeNode *cur = root;
 while (cur) {
 if (val == cur->val) return cur;
 if (val < cur->val)
 cur = cur->left;
 else
 cur = cur->right;
 }
 return NULL; // 未找到
}
 
// 递归版
TreeNode* bst_search_recursive(TreeNode *root, int val) {
 if (!root || root->val == val) return root;
 if (val < root->val)
 return bst_search_recursive(root->left, val);
 else
 return bst_search_recursive(root->right, val);
}

练习 3.1.1: 为什么 BST 的有序遍历（中序）输出的是升序序列？写出证明思路。

3.2 BST 插入

TreeNode* bst_insert(TreeNode *root, int val) {
 if (!root) return treenode_create(val);
 
 if (val < root->val) {
 root->left = bst_insert(root->left, val);
 } else if (val > root->val) {
 root->right = bst_insert(root->right, val);
 }
 // val == root->val: 不插入重复值（也可根据需求处理）
 
 return root;
}
 
// 迭代版
TreeNode* bst_insert_iterative(TreeNode *root, int val) {
 TreeNode *new_node = treenode_create(val);
 if (!new_node) return root;
 
 if (!root) return new_node;
 
 TreeNode *cur = root;
 while (1) {
 if (val < cur->val) {
 if (!cur->left) {
 cur->left = new_node;
 break;
 }
 cur = cur->left;
 } else if (val > cur->val) {
 if (!cur->right) {
 cur->right = new_node;
 break;
 }
 cur = cur->right;
 } else {
 free(new_node); // 重复，释放新节点
 break;
 }
 }
 return root;
}

练习 3.2.1: 如果 BST 插入的元素是递增序列（1, 2, 3, 4, 5…），得到的 BST 是什么形状？这会导致什么问题？

3.3 BST 删除 —— 三种情况

// 找右子树的最小节点（后继）
TreeNode* bst_min_node(TreeNode *node) {
 while (node && node->left) {
 node = node->left;
 }
 return node;
}
 
TreeNode* bst_delete(TreeNode *root, int val) {
 if (!root) return NULL;
 
 if (val < root->val) {
 root->left = bst_delete(root->left, val);
 } else if (val > root->val) {
 root->right = bst_delete(root->right, val);
 } else {
 // 找到了删除目标
 
 // 情况1: 叶子节点
 if (!root->left && !root->right) {
 free(root);
 return NULL;
 }
 // 情况2: 只有一个子节点
 else if (!root->left) {
 TreeNode *temp = root->right;
 free(root);
 return temp;
 }
 else if (!root->right) {
 TreeNode *temp = root->left;
 free(root);
 return temp;
 }
 // 情况3: 有两个子节点
 else {
 // 找后继（右子树最小节点）
 TreeNode *successor = bst_min_node(root->right);
 root->val = successor->val; // 用后继的值替换
 // 递归删除后继节点
 root->right = bst_delete(root->right, successor->val);
 }
 }
 return root;
}

三种删除情况图解:

graph TD
 subgraph "情况1: 叶子节点——直接删除"
 leaf["删除 4"] -.-> leaf_result["父节点的 left/right 置 NULL"]
 end
 subgraph "情况2: 一个子节点——子承父业"
 one["删除 3"] -.-> one_result["父节点指向 3 的唯一子节点"]
 end
 subgraph "情况3: 两个子节点——找后继替换"
 two["删除 8"] -.-> two_result["用 8 的后继(右子树最小值)替换 8 的值\n然后删除后继节点"]
 end

练习 3.3.1: 实现 BST 删除的前驱版本（用左子树的最大节点替代）。分析前驱和后继两种策略在树退化为链表时的性能差异。

第四节: AVL 树 —— 自平衡二叉搜索树

4.1 为什么需要平衡？

BST 在最坏情况下（插入有序序列）退化为链表，操作复杂度从 O(log n) 退化为 O(n)。
AVL 树通过维护”平衡因子”（左子树高度 - 右子树高度）来保证树的高度始终为 O(log n)。

// AVL 节点
typedef struct AVLNode {
 int val;
 int height; // 以本节点为根的子树高度
 struct AVLNode *left;
 struct AVLNode *right;
} AVLNode;
 
int avl_height(const AVLNode *node) {
 return node ? node->height : 0;
}
 
int avl_balance_factor(const AVLNode *node) {
 return node ? avl_height(node->left) - avl_height(node->right) : 0;
}
 
void avl_update_height(AVLNode *node) {
 if (node) {
 int hl = avl_height(node->left);
 int hr = avl_height(node->right);
 node->height = 1 + (hl > hr ? hl : hr);
 }
}

4.2 四种旋转

不平衡分为四种情况，对应四种旋转：

情况条件旋转
LL（左-左）左子树的左边插入右旋
RR（右-右）右子树的右边插入左旋
LR（左-右）左子树的右边插入先左旋左子，再右旋根
RL（右-左）右子树的左边插入先右旋右子，再左旋根

4.3 右旋（LL 情况）

// 右旋：左子节点"升上来"成为新的根
AVLNode* avl_rotate_right(AVLNode *y) {
 AVLNode *x = y->left;
 AVLNode *T2 = x->right; // x 的右子树（需要挂到 y 的左子）
 
 // 执行旋转
 x->right = y;
 y->left = T2;
 
 // 更新高度（顺序重要：先子后父）
 avl_update_height(y);
 avl_update_height(x);
 
 return x; // 新的根
}

右旋过程:

graph TD
 subgraph "旋转前（LL不平衡）"
 pre_y["y (bf=2)"] --> pre_x["x (bf=1)"]
 pre_x --> pre_T1["T1"]
 pre_x --> pre_T2["T2"]
 pre_y --> pre_T3["T3"]
 end
 subgraph "旋转后（平衡）"
 post_x["x (bf=0)"] --> post_T1["T1"]
 post_x --> post_y["y (bf=0)"]
 post_y --> post_T2["T2"]
 post_y --> post_T3["T3"]
 end
 pre_y -.->|右旋| post_x

4.4 左旋（RR 情况）

AVLNode* avl_rotate_left(AVLNode *x) {
 AVLNode *y = x->right;
 AVLNode *T2 = y->left;
 
 y->left = x;
 x->right = T2;
 
 avl_update_height(x);
 avl_update_height(y);
 
 return y;
}
graph TD
 subgraph "旋转前（RR不平衡）"
 pre_x["x (bf=-2)"] --> pre_T1["T1"]
 pre_x --> pre_y["y (bf=-1)"]
 pre_y --> pre_T2["T2"]
 pre_y --> pre_T3["T3"]
 end
 subgraph "旋转后（平衡）"
 post_y["y (bf=0)"] --> post_x["x (bf=0)"]
 post_y --> post_T3["T3"]
 post_x --> post_T1["T1"]
 post_x --> post_T2["T2"]
 end
 pre_x -.->|左旋| post_y

4.5 LR 和 RL 旋转（双旋转）

// LR: 先在左子做左旋，再在根做右旋
AVLNode* avl_rotate_left_right(AVLNode *node) {
 node->left = avl_rotate_left(node->left);
 return avl_rotate_right(node);
}
 
// RL: 先在右子做右旋，再在根做左旋
AVLNode* avl_rotate_right_left(AVLNode *node) {
 node->right = avl_rotate_right(node->right);
 return avl_rotate_left(node);
}
graph TD
 subgraph "LR 双旋转过程"
 lr1["y bf=2"] --> lr2["x bf=-1"]
 lr2 --> lr3["T1"]
 lr2 --> lr4["z bf=1"]
 lr4 --> lr5["T2"]
 lr4 --> lr6["T3"]
 lr1 --> lr7["T4"]
 end

 subgraph "步骤1: 左旋x"
 step1["对x执行左旋"]
 end

 subgraph "步骤2: 右旋y"
 step2["对y执行右旋 → 平衡!"]
 end

 lr1 -.-> step1 -.-> step2

4.6 完整的 AVL 插入

AVLNode* avl_insert(AVLNode *node, int val) {
 // 1. 标准 BST 插入
 if (!node) {
 AVLNode *new_node = (AVLNode*)malloc(sizeof(AVLNode));
 new_node->val = val;
 new_node->height = 1;
 new_node->left = new_node->right = NULL;
 return new_node;
 }
 
 if (val < node->val) {
 node->left = avl_insert(node->left, val);
 } else if (val > node->val) {
 node->right = avl_insert(node->right, val);
 } else {
 return node; // 不插入重复值
 }
 
 // 2. 更新高度
 avl_update_height(node);
 
 // 3. 检查平衡因子并旋转
 int bf = avl_balance_factor(node);
 
 // LL 情况
 if (bf > 1 && val < node->left->val) {
 return avl_rotate_right(node);
 }
 // RR 情况
 if (bf < -1 && val > node->right->val) {
 return avl_rotate_left(node);
 }
 // LR 情况
 if (bf > 1 && val > node->left->val) {
 return avl_rotate_left_right(node);
 }
 // RL 情况
 if (bf < -1 && val < node->right->val) {
 return avl_rotate_right_left(node);
 }
 
 return node; // 已平衡
}

关键理解: 旋转不改变 BST 的性质（左小右大），只改变树的形状（高度）。
旋转操作只修改少量指针，时间复杂度 O(1)。

练习 4.6.1: 实现 AVL 树的删除操作。AVL 删除比插入更复杂——可能删除后某个节点需要多次旋转才能恢复平衡。

第五节: 树的实际应用

5.1 在 C 中模拟文件系统树

typedef struct FSNode {
 char *name;
 int is_directory; // 0=文件, 1=目录
 struct FSNode *parent;
 struct FSNode *first_child;
 struct FSNode *next_sibling; // 左儿子右兄弟表示法
} FSNode;
 
// 左儿子右兄弟: 将任意树表示为二叉树
// first_child 指向第一个孩子
// next_sibling 指向下一个兄弟
graph TD
 root["/"] --> var["var/"]
 root --> home["home/"]
 root --> etc["etc/"]
 var --> log["log/"]
 home --> user["user/"]
 home --> admin["admin/"]

 subgraph "左儿子右兄弟二叉树表示"
 b_root["/"] --> b_var["var/"]
 b_root --> b_home["home/"]
 b_home --> b_etc["etc/"]
 b_var --> b_log["log/"]
 b_home --> b_user["user/"]
 b_user --> b_admin["admin/"]
 end

练习 5.1.1: 实现 fs_find() —— 在文件系统树中按路径查找节点（如 /home/user/docs）。

5.2 表达式树

// 表达式树的节点
typedef struct ExprNode {
 char op; // 运算符: '+', '-', '*', '/' 或 '\0' 表示数字
 int value; // 数字值（op='\0'时有效）
 struct ExprNode *left;
 struct ExprNode *right;
} ExprNode;
 
// 后序遍历计算表达式树的值
int expr_eval(const ExprNode *root) {
 if (!root->left && !root->right) { // 叶子 = 数字
 return root->value;
 }
 int left_val = expr_eval(root->left);
 int right_val = expr_eval(root->right);
 switch (root->op) {
 case '+': return left_val + right_val;
 case '-': return left_val - right_val;
 case '*': return left_val * right_val;
 case '/': return left_val / right_val;
 default: return 0;
 }
}

表达式 (3 + 4) * 5 的表达式树：

graph TD
 mul["*"] --> add["+"]
 mul --> five["5"]
 add --> three["3"]
 add --> four["4"]

练习 5.2.1: 实现将后缀表达式转换为表达式树（非递归，用栈）。

章节测试

判断题（10题）

判断题 1

二叉树中每个节点最多有两个子节点。

判断题 2

BST 的中序遍历结果一定是升序的。

判断题 3

AVL 树的平衡因子必须在 [-1, 0, 1] 范围内。

判断题 4

树的高度和节点数 n 的关系是 O(n)。

判断题 5

BST 的查找操作平均时间复杂度是 O(log n)，最坏是 O(n)。

判断题 6

先序（preorder）遍历等价于 DFS，也等价于 BFS。

判断题 7

删除 AVL 树节点后，可能需要进行多次旋转才能恢复平衡。

判断题 8

迭代中序遍历中，栈的最大深度等于树的高度。

判断题 9

后序遍历释放树是唯一安全的方式——因为释放父节点前必须先释放子节点。

判断题 10

表达式树的后序遍历结果恰好是中缀表达式。

选择题（10题）

选择题 1

一棵包含 15 个节点的完全二叉树，其高度是多少？

  • A. 3

  • B. 4

  • C. 5

  • D. 15

选择题 2

向空的 BST 依次插入 5, 3, 7, 2, 4, 6, 8 后，树的高度是？

  • A. 2

  • B. 3

  • C. 4

  • D. 7

选择题 3

AVL 树中，对于 LL 不平衡（bf=2, 左子的 bf=1），应执行什么操作？

  • A. 左旋

  • B. 右旋

  • C. 先左旋再右旋

  • D. 先右旋再左旋

选择题 4

在 64 位系统上，一个 TreeNode（含 val/left/right+填充）占用多少字节？

  • A. 16

  • B. 20

  • C. 24

  • D. 32

选择题 5

寻找 BST 中某个节点的”前驱”（preorder predecessor），正确的方法是？

  • A. 右子树的最小值

  • B. 左子树的最大值

  • C. 父节点

  • D. 右子树的最大值

选择题 6

以下哪种说法是正确的？

  • A. 所有二叉树都是 BST

  • B. 所有 BST 都是 AVL 树

  • C. AVL 树是一种自平衡 BST

  • D. BST 总是 O(log n) 查找

选择题 7

后序遍历”4 5 2 6 7 3 1”中，1 是什么节点？

  • A. 某个叶子节点

  • B. 根节点

  • C. 某个左子节点

  • D. 无法确定

选择题 8

一棵高度为 h 的满二叉树有多少个节点？

  • A. h

  • B. 2

  • C. 2^h - 1

  • D. h

选择题 9

AVL 旋转后需要更新高度的顺序是？

  • A. 先父后子

  • B. 先子后父

  • C. 无所谓

  • D. 同时更新

选择题 10

二叉搜索树退化为链表时，删除一个节点的复杂度是多少？

  • A. O(1)

  • B. O(log n)

  • C. O(n)

  • D. O(n²)

编程大题

编程题 1：实现完整的 AVL 树库

要求：

  1. 实现 AVL 树的 insert、delete、search、min、max
  2. 实现四种旋转（LL, RR, LR, RL）
  3. 实现增量式高度更新
  4. 实现 is_balanced() 函数——遍历整棵树验证平衡条件
  5. 实现 print_tree() —— 递归打印树结构（带缩进，显示每个节点的值和高度）

提示: 删除操作比插入复杂——删除后每个回溯的祖先节点都可能需要旋转。

编程题 2：基于 BST 实现简单的 key-value 数据库

要求：

  1. 节点存储 char *key 和 int value
  2. 支持插入、查找、删除、范围查询（给定 [low, high] 返回所有在此范围内的 key-value）
  3. 范围查询利用 BST 中序遍历的升序特性
  4. 讨论为什么不直接用 AVL 树？（提示：AVL 删除的多次旋转比 BST 费时，对于读多写少的场景 BST 可能更快？）

提示: 范围查询是 BST 相对于哈希表的绝对优势所在。

编程题 3：实现并对比三种自平衡树

要求：

  1. 分别实现 AVL 树和最简单的”替罪羊树”（Scapegoat Tree，不平衡时暴力重建子树）
  2. 两种树接收相同的 100 万随机插入序列
  3. 对比：总旋转次数（AVL）、总重建次数（替罪羊树）、最终树高度、插入总耗时
  4. 分析结果并解释为什么实际工程中常用红黑树而不是 AVL 树

提示: 红黑树比 AVL 树旋转更少（但平衡度稍差），更适合写密集型应用。

推荐练习题（力扣）

知识点题目建议
二叉树、递归力扣二叉树
二叉树遍历力扣二叉树遍历
中序+后序求先序力扣二叉树重构
前序+中序求后序力扣二叉树重构
BST、平衡树力扣平衡树
对顶堆+BST力扣堆

知识网络

关系图谱

反向链接