树的常见表示方法（邻接表、父亲表示法等）
极难2语言版本：通用
概述：介绍除孩子表示法外多种树的存储方式，包括父亲表示法、孩子表示法、孩子兄弟表示法、邻接表，以及它们各自的优缺点。
树的四种存储方式：如何用代码表示你的家庭关系图？
想象你要用电脑记录一个班级的座位安排——每个同学前后左右是谁，或者记录你家的人物关系：爸爸妈妈、爷爷奶奶、兄弟姐妹。在计算机里，这种“一个节点可以有多个子节点”的结构叫做树。树有很多种存储方式，就像你可以用家谱图、Excel表格、或者链表来记录关系一样。不同的方式适合不同的工作：有的能快速找到爸爸是谁，有的方便列出所有孩子，有的最省内存。
在这篇文章里，我们会学习四种常见的树表示方法，包括父亲表示法、孩子表示法、孩子兄弟表示法和邻接表。每种方法都有各自的优缺点，就像你收拾书包：用文件袋装作业（方便找）、用笔袋装笔（快速拿取）、用文件夹装所有试卷（整齐）。学会它们，你就能根据实际需求挑选最合适的存储方式。
1. 父亲表示法：只记爸爸不记孩子
思想
用一个数组存储所有节点，每个节点只记录它的父节点在数组中的下标（或地址）。根节点没有爸爸，就记成 -1。
生活例子
老师让你写一张“谁是谁的组长”的纸条。你只写每个组员的组长是哪个同学，不记每个组长手底下有谁。这样纸条很小，但要想知道某个组长有哪些组员，你必须看遍所有人的纸条才能知道。
优点
- 找爸爸超快：只要知道一个人的下标，直接看数组就能得到爸爸的下标（O(1)时间）。
- 空间很省：只需要一个长度n的父节点数组（每个存储一个整数）。
缺点
- 找孩子很慢：必须遍历所有节点，检查谁的爸爸指向你（O(n)时间）。
- 不适合经常要枚举孩子的情况。
适用场景
并查集（Disjoint Set Union）中常用父亲表示法，因为并查集主要关心“哪个节点是老大”，很少需要找手下。
常见错误
- 忘记给根节点设父节点为 -1（或特殊值），导致后面查找根节点时出错。
- 在找孩子时，只找了一次，忘了可能有很多孩子（需要用循环遍历）。
代码示例（C++）
#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {
char data; // 节点数据，比如人的名字
int parent; // 父节点在数组中的下标，根节点为-1
TreeNode(char d, int p) : data(d), parent(p) {}
};
int main() {
// 创建节点数组：假设树结构为 A是根，B、C是A的孩子，D是B的孩子
// 编号：0:A, 1:B, 2:C, 3:D
vector<TreeNode> tree = {
TreeNode('A', -1), // 0:根，没有爸爸
TreeNode('B', 0), // 1:爸爸是0号A
TreeNode('C', 0), // 2:爸爸是0号A
TreeNode('D', 1) // 3:爸爸是1号B
};
// 查找节点A的子节点：遍历数组，找所有parent==0的
cout << "A的子节点: ";
for (const auto& node : tree) {
if (node.parent == 0) cout << node.data << " "; // 输出 B C
}
cout << endl;
// 查找节点D的父节点
int idx = 3; // 下标3对应D
int p = tree[idx].parent; // p=1
cout << "D的父节点: " << tree[p].data << endl; // 输出 B
return 0;
}
2. 孩子表示法：每个节点记下所有孩子
思想
每个节点用一个孩子列表（比如数组、链表）来存储所有孩子的地址或下标。就像你写作业记录表：在每个组长名字后面列出手下所有组员的名字。这样想知道组长带哪些人，直接看列表就行。
生活例子
学生会的部门：每个部长下面有一份干事名单。想知道部长管多少人，看名单就找到。但如果想知道某个干事的部长是谁，就得翻遍所有部门名单（或者额外记一个“我的部长是谁”）。
优点
- 找孩子非常容易：直接遍历节点内的孩子列表（O(孩子数)）。
- 如果树比较“瘦”（孩子数少），孩子列表不占太多空间。
缺点
- 找爸爸很慢：必须遍历所有节点的孩子列表，找到谁包含自己（除非额外存父指针）。
- 如果树很“胖”（一个节点有几百个孩子），孩子列表会很长，浪费指针空间（每个孩子要用一个指针或整数）。
常见错误
- 忘记在插入孩子时更新孩子列表的指针（比如没把新孩子加进去）。
- 使用动态数组（如vector）时频繁调整大小，导致性能下降（但问题不大）。
代码示例（C++ 孩子表示法，使用 vector 作为孩子列表）
#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {
char data; // 节点数据
vector<int> children; // 孩子节点在数组中的下标列表
TreeNode(char d) : data(d) {}
};
int main() {
// 假设有4个节点：0:A, 1:B, 2:C, 3:D
vector<TreeNode> nodes = {
TreeNode('A'), // 0
TreeNode('B'), // 1
TreeNode('C'), // 2
TreeNode('D') // 3
};
// 构建树：A的孩子是B和C，B的孩子是D
nodes[0].children = {1, 2};
nodes[1].children = {3};
// 找A的孩子
cout << "A的孩子: ";
for (int child : nodes[0].children) {
cout << nodes[child].data << " "; // 输出 B C
}
cout << endl;
// 找D的爸爸：需要遍历所有节点
for (int i = 0; i < nodes.size(); ++i) {
for (int child : nodes[i].children) {
if (child == 3) {
cout << "D的爸爸是: " << nodes[i].data << endl; // 输出 B
}
}
}
return 0;
}
3. 孩子兄弟表示法：左孩子右兄弟，把树变成二叉树
思想
每个节点只存两个指针：firstChild（第一个孩子）和 nextSibling（右边的兄弟）。这样任何一棵树都能表示成一棵二叉树（左指针指向第一个孩子，右指针指向右边的兄弟）。这种表示法也叫二叉链表表示法。
生活例子
想象你在教室里排座位：每个同学可以记住左边坐的是谁（如果他有同桌），右边坐的是谁（他的右边同学）。如果老师让你用这个方式记录整个班的座位，你只需要记住每个人的左边和右边，就能推导出所有人之间的前后左右关系。
优点
- 节省空间：每个节点固定两个指针，不像孩子表示法那样需要动态数组。
- 可以复用二叉树的算法（比如前序、中序、后序遍历，计算深度等）。
- 适合内存受限的环境（如嵌入式系统、C语言编程）。
缺点
- 找孩子不如孩子表示法直接：要遍历 firstChild 和 nextSibling 的链条才能拿到所有孩子，复杂度 O(孩子数)。
- 找爸爸依然需要额外遍历（除非再存一个父指针）。
常见错误
- 搞混 firstChild 和 nextSibling 的含义：firstChild 指向最左边的孩子，nextSibling 指向自己的右边兄弟。不要写成指向爸爸或别的。
- 构建树时忘记连接兄弟之间的链表，导致丢失节点。
代码示例（C++）
#include <iostream>
using namespace std;
struct CSNode {
char data; // 节点数据
CSNode *firstChild; // 第一个孩子指针
CSNode *nextSibling; // 下一个兄弟指针
CSNode(char val) : data(val), firstChild(nullptr), nextSibling(nullptr) {}
};
// 遍历孩子兄弟树（相当于二叉树的先序遍历）
void traverse(CSNode* root) {
if (!root) return;
cout << root->data << " ";
traverse(root->firstChild); // 先遍历第一个孩子及其兄弟链
traverse(root->nextSibling); // 再遍历右边的兄弟
}
int main() {
// 构建树：A(B(E,F),C,D(G))
// 想象这样的树：
// A
// / | \
// B C D
// / \ |
// E F G
CSNode* A = new CSNode('A');
CSNode* B = new CSNode('B');
CSNode* C = new CSNode('C');
CSNode* D = new CSNode('D');
CSNode* E = new CSNode('E');
CSNode* F = new CSNode('F');
CSNode* G = new CSNode('G');
// A的第一个孩子是B，B的右边兄弟是C，C的右边兄弟是D
A->firstChild = B;
B->nextSibling = C;
C->nextSibling = D;
// B的第一个孩子是E，E的右边兄弟是F
B->firstChild = E;
E->nextSibling = F;
// D的第一个孩子是G
D->firstChild = G;
cout << "孩子兄弟树遍历（先序）: ";
traverse(A);
// 输出: A B E F C D G
cout << endl;
return 0;
}
Python版本
class CSNode:
def __init__(self, data):
self.data = data
self.firstChild = None # 第一个孩子
self.nextSibling = None # 右边兄弟
def traverse(root):
if root is None:
return
print(root.data, end=' ')
traverse(root.firstChild)
traverse(root.nextSibling)
# 构建树
A = CSNode('A')
B = CSNode('B')
C = CSNode('C')
D = CSNode('D')
E = CSNode('E')
F = CSNode('F')
G = CSNode('G')
A.firstChild = B
B.nextSibling = C
C.nextSibling = D
B.firstChild = E
E.nextSibling = F
D.firstChild = G
print("孩子兄弟树遍历: ", end='')
traverse(A)
print()
4. 邻接表：像图一样存树
思想
用一个长度为n的数组，每个数组元素是一个链表（或向量），存放与这个节点相邻的所有节点。因为树是一种特殊的图（无环连通图），所以图论中的邻接表可以直接用来存树。如果是有向树（边从父指向子），邻接表只存孩子；如果是无向树，则双向存。
生活例子
把全班同学的关系画成一张图：每个同学手拉手，左边写邻桌的名字，右边写背后同学的名字。这样任何一个同学想知道自己旁边是谁，直接看自己的名单就行。
优点
- 非常灵活：支持任意度数的树，也适合图。
- 容易做深度优先（DFS）和广度优先（BFS）遍历，因为能快速拿到所有邻居。
- 如果树是无向的，可以配合 visited 数组从根开始遍历。
缺点
- 查找父节点需要遍历邻居列表（除非额外存父指针或者只存有向边）。
- 每个节点需要存储链表头，比固定指针稍稍多占一点空间（但通常可忽略）。
常见错误
- 用无向邻接表做遍历时忘记标记已访问节点，导致死循环（来回走）。
- 添加边时只加了一半（习惯只加 u->v，忘了加 v->u），导致图不连通。
代码示例（C++ 无向邻接表）
#include <iostream>
#include <vector>
#include <list>
using namespace std;
class TreeAdjList {
private:
vector<list<int>> adj; // 邻接表，每个list存放相邻节点的编号
int n; // 节点数（编号0~n-1）
public:
TreeAdjList(int size) : n(size), adj(size) {}
// 添加一条无向边
void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u); // 因为是树，双向添加
}
void print() {
for (int i = 0; i < n; ++i) {
cout << "节点 " << char('A' + i) << " 的邻居: ";
for (int neigh : adj[i]) {
cout << char('A' + neigh) << " ";
}
cout << endl;
}
}
};
int main() {
TreeAdjList tree(7); // 假设7个节点 A~G
// 添加边（按照之前 A(B(E,F),C,D(G)) 的树）
tree.addEdge(0, 1); // A-B
tree.addEdge(0, 2); // A-C
tree.addEdge(1, 3); // B-D
tree.addEdge(1, 4); // B-E
tree.addEdge(2, 5); // C-F
tree.addEdge(2, 6); // C-G
tree.print();
// 输出：
// 节点 A 的邻居: B C
// 节点 B 的邻居: A D E
// 节点 C 的邻居: A F G
// 节点 D 的邻居: B
// 节点 E 的邻居: B
// 节点 F 的邻居: C
// 节点 G 的邻居: C
return 0;
}
Python 版本（使用字典）
class TreeAdjList:
def __init__(self, n):
self.adj = {i: [] for i in range(n)} # 每个节点对应一个空列表
def add_edge(self, u, v):
self.adj[u].append(v)
self.adj[v].append(u) # 无向边双向添加
def print(self):
for node, neighbors in self.adj.items():
print(f"节点 {chr(ord('A') + node)} 的邻居: ", end='')
for nb in neighbors:
print(chr(ord('A') + nb), end=' ')
print()
tree = TreeAdjList(7)
edges = [(0,1),(0,2),(1,3),(1,4),(2,5),(2,6)]
for u,v in edges:
tree.add_edge(u,v)
tree.print()
总结：四种方法对比
| 表示方法 | 存储核心 | 查父节点速度 | 查孩子速度 | 空间复杂度 | 适用场景 |
|---|---|---|---|---|---|
| 父亲表示法 | 数组存父指针 | O(1) | O(n)遍历 | O(n) | 并查集、只需找爸爸的情况 |
| 孩子表示法 | 每个节点带孩子列表 | O(n)遍历 | O(度) | O(n+边数) | 经常要枚举孩子的树 |
| 孩子兄弟表示法 | 两个指针（左孩子、右兄弟） | O(深度)遍历兄弟链 | O(度)走兄弟链 | O(n)固定 | 节省内存、复用二叉树算法 |
| 邻接表 | 每个节点存相邻节点链表 | O(度) | O(度) | O(n+边数) | 图遍历、DFS/BFS |
如何选择？
- 如果你在写并查集（比如判断两个同学是否在同一个小组），父亲表示法最好。
- 如果要做树的前序/后序遍历，并且不关心内存，孩子表示法最直接。
- 如果内存紧张（比如单片机、老式电脑），用孩子兄弟表示法。
- 如果你已经在学图论，或者想用 BFS 找最短路径，邻接表最方便。
相关知识点延伸
- 树的基本遍历：掌握前序、中序、后序、层序遍历，能帮你更好地理解各种表示法下的遍历代码。
- 二叉树：孩子兄弟表示法本质上把任意树变成了二叉树，二叉树的很多算法（如计算高度、平衡判断）可以直接套用。
- 并查集：专门使用父亲表示法的高级数据结构，用于快速合并和查找集合。
- 图论基础：邻接表是图的标配，从树转到图只需把“无环”改为“可能有环”，并记得标记已访问。
现在，你已经掌握了四种存储树的“神器”。下次写代码时，根据你的需求选择最合适的，就能像整理书包一样顺手啦！
例题精讲
1单选题
在树的父亲表示法中，每个节点存储其父节点的索引（或指针）。若根节点的父节点索引存储为-1，则以下关于父亲表示法的描述正确的是？
A父亲表示法可以快速找到任意节点的所有子节点
B父亲表示法在寻找任意节点的父节点时时间复杂度为O(1)
C父亲表示法适合用于需要频繁查找兄弟节点的场景
D父亲表示法可以高效地遍历整棵树的所有节点
2判断题
使用邻接表存储一棵树时，若树的节点数为n，边的数量为n-1，则该邻接表所占用的空间与树的度数分布无关。
3判断题
在树的父亲表示法中，若将根节点的父节点指针指向自身（即 parent[root] = root），则编写函数 findRoot(x) 时，可以通过 while(parent[x] != x) x = parent[x]; 循环来正确找到根节点。
4填空题
已知一棵树采用父亲表示法存储，数组 parent[0..n-1] 中 parent[i] 表示节点 i 的父节点编号，根节点的 parent 值为 -1。下面函数的功能是找到节点 i 所在树的根节点编号。请补充循环体中的代码。
int findRoot(int i, int parent[]) {
while (parent[i] != -1) {
___
}
return i;
}5单选题
关于树的孩子兄弟表示法（二叉链表表示法），以下说法正确的是？
A孩子兄弟表示法将每个节点的所有子节点按顺序存放在一个连续数组中
B孩子兄弟表示法中的每个节点包含两个指针：分别指向第一个孩子和下一个兄弟
C孩子兄弟表示法无法表示二叉树，只能表示普通树
D孩子兄弟表示法中，根节点的 nextSibling 指针一定指向其第一个兄弟节点
6判断题
在树的孩子表示法中，查找某个节点的父节点的时间复杂度为O(n)，其中n为树的节点总数。