本课时有配套视频讲解，购买后即可观看（永久有效）
树与二叉树的转换
一、课上练习
编程练习
- 树的二叉树转换：L49946
二、知识总结
✨ 核心思想
在计算机科学中，一般的多叉树（每个节点可以有任意多个子节点）在存储和处理上不如二叉树方便。左孩子右兄弟表示法（Left-Child Right-Sibling Representation） 提供了一种巧妙的方法，将任意一棵多叉树转换为一棵二叉树，同时保留原树的全部结构信息。
核心思想：
- 二叉树的左指针指向该节点的第一个孩子
- 二叉树的右指针指向该节点的下一个兄弟
这种表示法在竞赛中非常常见，因为它使得多叉树可以用二叉树的遍历算法来处理。
✨ 算法原理
多叉树 → 二叉树的转换规则
- 保留长子关系：每个节点的第一个孩子成为它在二叉树中的左孩子
- 兄弟变右孩子：同一层的兄弟节点通过右指针串联
- 根节点无右孩子：转换后的二叉树根节点没有右子树（因为根没有兄弟）
二叉树 → 多叉树的还原规则
- 二叉树节点的左孩子是原树中该节点的第一个孩子
- 从左孩子出发，沿右指针链走到底，依次遇到的都是原树中的兄弟节点
- 这些兄弟节点都是原节点的孩子
森林 → 二叉树
当有多棵树组成的森林需要转换时：
- 先将每棵树各自转换为二叉树
- 将第一棵树的根作为整棵二叉树的根
- 后续每棵树的根依次作为前一棵树根节点的右孩子
✨ 代码实现
多叉树转二叉树
tree_to_binary.cpp
1#include <iostream>
2#include <vector>
3using namespace std;
4
5const int MAXN = 100005;
6
7// 多叉树的邻接表表示
8vector<int> children[MAXN]; // children[u] 存储 u 的所有孩子（有序）
9
10// 二叉树节点
11struct BinaryNode {
12 int left; // 左孩子（= 原树的第一个孩子）
13 int right; // 右兄弟（= 原树的下一个兄弟）
14} bt[MAXN];
15
16// 将以 u 为根的多叉子树转换为二叉树
17// siblings 是 u 的下一个兄弟列表的起始位置
18void convert(int u) {
19 bt[u].left = bt[u].right = 0;
20
21 if (!children[u].empty()) {
22 bt[u].left = children[u][0]; // 第一个孩子 → 左孩子
23 // 将所有孩子用右指针串起来
24 for (int i = 0; i < (int)children[u].size() - 1; i++) {
25 bt[children[u][i]].right = children[u][i + 1];
26 }
27 // 递归处理每个孩子
28 for (int child : children[u]) {
29 convert(child);
30 }
31 }
32}
33
34// 输出二叉树（先序遍历验证）
35void preorder(int u) {
36 if (u == 0) return;
37 cout << u << " ";
38 preorder(bt[u].left);
39 preorder(bt[u].right);
40}
41
42int main() {
43 int n;
44 cin >> n;
45 // 读入每个节点的父亲（0表示根）
46 int root = 0;
47 for (int i = 1; i <= n; i++) {
48 int fa;
49 cin >> fa;
50 if (fa == 0) root = i;
51 else children[fa].push_back(i);
52 }
53
54 convert(root);
55
56 cout << "二叉树先序遍历: ";
57 preorder(root);
58 cout << endl;
59
60 return 0;
61}二叉树还原为多叉树
binary_to_tree.cpp
1#include <iostream>
2#include <vector>
3using namespace std;
4
5const int MAXN = 100005;
6
7struct BinaryNode {
8 int left, right;
9} bt[MAXN];
10
11vector<int> children[MAXN]; // 还原后的多叉树
12
13// 还原：将二叉树节点 u 的左子树链还原为 u 的孩子列表
14void restore(int u) {
15 if (u == 0) return;
16
17 // u 的左孩子是原树的第一个孩子
18 // 从左孩子出发，沿右链走到底，都是 u 的孩子
19 int child = bt[u].left;
20 while (child != 0) {
21 children[u].push_back(child);
22 restore(child); // 递归还原每个孩子
23 child = bt[child].right; // 下一个兄弟
24 }
25}
26
27// 打印多叉树结构
28void printTree(int u, int depth) {
29 for (int i = 0; i < depth; i++) cout << " ";
30 cout << u << endl;
31 for (int child : children[u]) {
32 printTree(child, depth + 1);
33 }
34}
35
36int main() {
37 int n;
38 cin >> n;
39 for (int i = 1; i <= n; i++) {
40 cin >> bt[i].left >> bt[i].right;
41 }
42
43 int root = 1; // 假设根为 1
44 restore(root);
45
46 cout << "还原后的多叉树:" << endl;
47 printTree(root, 0);
48
49 return 0;
50}森林转二叉树
forest_to_binary.cpp
1#include <iostream>
2#include <vector>
3using namespace std;
4
5const int MAXN = 100005;
6vector<int> children[MAXN];
7
8struct BinaryNode {
9 int left, right;
10} bt[MAXN];
11
12// 将单棵多叉树转为二叉树（同前）
13void convertTree(int u) {
14 bt[u].left = bt[u].right = 0;
15 if (!children[u].empty()) {
16 bt[u].left = children[u][0];
17 for (int i = 0; i < (int)children[u].size() - 1; i++) {
18 bt[children[u][i]].right = children[u][i + 1];
19 }
20 for (int child : children[u]) {
21 convertTree(child);
22 }
23 }
24}
25
26int main() {
27 int n, treeCount;
28 cin >> n >> treeCount;
29
30 // 读入每个节点的父亲，0 表示某棵树的根
31 vector<int> roots;
32 for (int i = 1; i <= n; i++) {
33 int fa;
34 cin >> fa;
35 if (fa == 0) roots.push_back(i);
36 else children[fa].push_back(i);
37 }
38
39 // 每棵树各自转换
40 for (int r : roots) {
41 convertTree(r);
42 }
43
44 // 将多棵树的根通过右指针串起来
45 for (int i = 0; i < (int)roots.size() - 1; i++) {
46 bt[roots[i]].right = roots[i + 1];
47 }
48
49 cout << "森林转二叉树完成，根节点: " << roots[0] << endl;
50 return 0;
51}✨ 执行示例
多叉树 → 二叉树
原始多叉树：
1
/ | \
2 3 4
/ \ |
5 6 7转换过程：
1步骤1: 节点1的孩子为 [2, 3, 4]
2 → bt[1].left = 2（第一个孩子）
3 → bt[2].right = 3（2的下一个兄弟是3）
4 → bt[3].right = 4（3的下一个兄弟是4）
5
6步骤2: 节点2的孩子为 [5, 6]
7 → bt[2].left = 5
8 → bt[5].right = 6
9
10步骤3: 节点4的孩子为 [7]
11 → bt[4].left = 7
12
13转换结果（二叉树）:
14 1
15 /
16 2
17 / \
18 5 3
19 \ \
20 6 4
21 /
22 7验证：二叉树先序遍历
二叉树先序: 1 → 2 → 5 → 6 → 3 → 4 → 7
对应原树先序: 1 → 2 → 5 → 6 → 3 → 4 → 7 ✓ 一致！✨ 解题步骤详解
何时使用此技巧
- 多叉树需要用二叉树算法处理：如 LCA、树形 DP 等
- 森林问题统一处理：将多棵树转为一棵二叉树
- 节省存储空间：不需要动态数组存储不定数量的孩子
转换步骤总结
多叉树 → 二叉树：
- 对每个节点，将其第一个孩子作为左孩子
- 将所有兄弟节点沿右指针串联
- 递归处理每个子树
二叉树 → 多叉树：
- 左孩子是该节点的第一个孩子
- 从左孩子沿右链走到底，收集所有孩子
- 递归还原每个子节点
重要性质
- 多叉树的先序遍历 = 对应二叉树的先序遍历
- 多叉树的后序遍历 = 对应二叉树的中序遍历
- 这两个性质在竞赛中非常有用
✨ 常见错误
- 混淆左孩子和右孩子的含义：左 = 第一个孩子，右 = 下一个兄弟，不能搞反
- 忘记初始化：
bt[u].left = bt[u].right = 0必须在转换前设置 - 森林转换时忘记串联根节点：多棵树的根需要通过右指针依次连接
- 还原时只取了左孩子：还原时必须沿右链遍历，收集所有兄弟
- 递归爆栈：对于深度很大的树，考虑使用非递归实现
- 孩子顺序错误：兄弟链的顺序必须与原树中孩子的顺序一致
✨ 算法评价
时间复杂度
- 转换：$O(n)$，每个节点恰好被访问一次
- 还原：$O(n)$，每个节点恰好被访问一次
空间复杂度
- $O(n)$，存储二叉树结构
- 递归调用栈的深度为树的高度
适用场景
- 将多叉树问题转化为二叉树问题，利用成熟的二叉树算法
- 存储结构统一化：用固定的两个指针代替不定长的孩子列表
- 森林的统一表示和处理
局限性
- 转换后的二叉树形态可能很不平衡（若原树某节点有大量孩子，右链会很长）
- 某些操作在转换后的二叉树上不如在原树上直观
- 需要理解两种表示之间的对应关系，增加了思维负担
三、课后练习
编程练习
- 二叉树转换为树：L49947