树的孩子兄弟表示法
用"孩子链表 + 兄弟链表"表示树:每个节点只保留两个指针——firstChild 指向第一个孩子,nextSibling 指向下一个兄弟。这种表示法把任意多叉树变成了二叉结构,空间和遍历都更优雅。
为什么需要它
普通多叉树用"孩子数组"表示,问题是每个节点的孩子数不固定:
// 方案一:定长孩子数组 —— 浪费空间
struct Node {
int val;
Node* child[100]; // 大多数节点只有 1~2 个孩子,浪费 98 个指针
};
孩子兄弟表示法只用两个指针就能表示任意多叉树,空间是 O(n),与树的形状无关。
结构定义
struct Node {
int val;
Node* firstChild; // 第一个孩子
Node* nextSibling; // 下一个兄弟
};
关键洞察:"长子 + 右兄弟"就能表示整棵树。每个节点的所有孩子串成一条链(通过 nextSibling),父节点只需指向链头(firstChild)。
A
/ | \
B C D
|
E
孩子兄弟表示:
A.firstChild -> B
B.nextSibling -> C
C.nextSibling -> D
C.firstChild -> E
A
|
B --→ C --→ D
|
E
建立孩子兄弟树
从"父节点列表"或"边列表"建树:
Node* buildTree(int n, const vector<pair<int,int>>& edges, int root) {
vector<Node*> node(n + 1);
for (int i = 1; i <= n; i++)
node[i] = new Node{i, nullptr, nullptr};
// 为保证兄弟顺序稳定,先把每个父节点的孩子收集起来
vector<vector<int>> children(n + 1);
for (auto& [u, v] : edges) // u 是父,v 是子
children[u].push_back(v);
for (int u = 1; u <= n; u++) {
// 逆序挂接:这样正序排列的孩子会按原顺序串联
for (int i = (int)children[u].size() - 1; i >= 0; i--) {
int v = children[u][i];
node[v]->nextSibling = node[u]->firstChild;
node[u]->firstChild = node[v];
}
}
return node[root];
}
遍历方式
1. 先根遍历(对应多叉树的 DFS)
访问自己 → 遍历第一个孩子 → 沿兄弟链遍历所有孩子:
void preOrder(Node* u) {
if (!u) return;
cout << u->val << " "; // 访问自己
preOrder(u->firstChild); // 第一个孩子
// 注意:兄弟是通过 firstChild 内部串联的,这里递归已覆盖
}
// 更清晰的双参数写法
void preOrder(Node* u) {
if (!u) return;
cout << u->val << " ";
for (Node* c = u->firstChild; c; c = c->nextSibling)
preOrder(c);
}
2. 求树的深度
int depth(Node* u) {
if (!u) return 0;
int mx = 0;
for (Node* c = u->firstChild; c; c = c->nextSibling)
mx = max(mx, depth(c));
return mx + 1;
}
3. 统计节点数
int countNodes(Node* u) {
if (!u) return 0;
int cnt = 0;
for (Node* c = u->firstChild; c; c = c->nextSibling)
cnt += countNodes(c);
return cnt + 1;
}
4. 求叶子节点
叶子 = 没有 firstChild 的节点:
void collectLeaves(Node* u, vector<int>& leaves) {
if (!u) return;
if (!u->firstChild) { leaves.push_back(u->val); return; }
for (Node* c = u->firstChild; c; c = c->nextSibling)
collectLeaves(c, leaves);
}
与其他表示法的对比
| 表示法 | 空间 | 找孩子 | 找父亲 | 特点 |
|---|---|---|---|---|
| 定长孩子数组 | O(n·k),浪费 | O(1) | O(n) | 简单,但 k 固定 |
| 孩子链表(vector) | O(n) | O(deg) | O(n) | C++ 中常用 |
| 孩子兄弟法 | O(n) | O(deg) | O(n) | 二叉化、唯一 |
| 父节点数组 | O(n) | O(n) | O(1) | 反向查方便 |
为什么它重要:树转二叉树
孩子兄弟表示法有一个漂亮的等价说法——任何多叉树都可以唯一地转换成二叉树:
- 二叉树的 左孩子 = 原树的 第一个孩子
- 二叉树的 右孩子 = 原树的 下一个兄弟
struct BiNode {
int val;
BiNode* left; // 原树的 firstChild
BiNode* right; // 原树的 nextSibling
};
转换规则:
BiNode* convert(Node* u) {
if (!u) return nullptr;
BiNode* b = new BiNode{u->val, nullptr, nullptr};
b->left = convert(u->firstChild); // 长子变左孩子
b->right = convert(u->nextSibling); // 兄弟变右孩子
return b;
}
这就解释了为什么"森林/多叉树的遍历可以先转成二叉树再处理"——任何树都能用二叉树的标准算法处理,不需要为多叉树单独设计算法。
在竞赛中的实际用途
1. 节省内存:节点数 10^6 的多叉树,用 vector<vector<int>> 每个 vector 有 24 字节开销,孩子兄弟法只有 2 个指针。
2. 树的同构判断:两个多叉树是否同构,转成孩子兄弟二叉树后直接比较结构即可。
3. 树的哈希:firstChild / nextSibling 的顺序固定,便于计算树的哈希值。
// 树哈希示例
unsigned long long treeHash(Node* u) {
if (!u) return 0;
unsigned long long h = 1;
for (Node* c = u->firstChild; c; c = c->nextSibling) {
h = h * 131 + treeHash(c); // 顺序敏感
}
return h;
}
4. 多叉树的 DP:很多树形 DP 用孩子兄弟结构写转移更简洁。
常见错误
- 兄弟链建反了:用头插法却忘记逆序,导致子节点顺序颠倒(如果题目要求顺序则答案错误)。
- 遍历时重复访问:
preOrder写成同时递归firstChild和nextSibling会导致兄弟被访问两次。 - 叶子判断错误:叶子是
firstChild == nullptr,不是nextSibling == nullptr。 - 忘记释放内存:
new出来的节点没有delete。
小结
孩子兄弟表示法用 firstChild + nextSibling 两个指针表示任意多叉树,空间 O(n)。它的价值在于把多叉树统一成二叉树结构,让所有二叉树的算法可以直接复用。遍历时记住:"进入孩子链,沿兄弟链走"是同一个循环结构。