困难C++4 分钟1,286 字

树的孩子兄弟表示法

用"孩子链表 + 兄弟链表"表示树:每个节点只保留两个指针​——firstChild 指向第一个孩子,nextSibling 指向下一个兄弟。这种表示法把任意多叉树变成了二叉结构​​,空间和遍历都更优雅。

为什么需要它

普通多叉树用"孩子数组"表示,问题是每个节点的孩子数不固定:

cpp
// 方案一:定长孩子数组 —— 浪费空间
struct Node {
    int val;
    Node* child[100];   // 大多数节点只有 1~2 个孩子,浪费 98 个指针
};

孩子兄弟表示法只用两个指针就能表示任意多叉树,​空间是 O(n)​​,与树的形状无关。

结构定义

cpp
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

建立孩子兄弟树

从"父节点列表"或"边列表"建树:

cpp
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)

访问自己 → 遍历第一个孩子 → 沿兄弟链遍历所有孩子:

cpp
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. 求树的深度

cpp
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. 统计节点数

cpp
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 的节点:

cpp
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) 反向查方便

为什么它重要:树转二叉树

孩子兄弟表示法有一个漂亮的等价说法——任何多叉树都可以唯一地转换成二叉树​​:

  • 二叉树的 左孩子 = 原树的 第一个孩子
  • 二叉树的 右孩子 = 原树的 下一个兄弟
cpp
struct BiNode {
    int val;
    BiNode* left;    // 原树的 firstChild
    BiNode* right;   // 原树的 nextSibling
};

转换规则:

cpp
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 的顺序固定,便于计算树的哈希值。

cpp
// 树哈希示例
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)。它的价值在于把多叉树统一成二叉树结构​​,让所有二叉树的算法可以直接复用。遍历时记住:"进入孩子链,沿兄弟链走"是同一个循环结构。

同类知识点