C++ 中的树的父亲表示法

C++ 中的树的父亲表示法（Parent Representation）是一种使用数组来表示树的数据结构，其中数组的下标表示节点的编号，数组的元素表示该节点的父节点编号。

下面是一个示例代码，展示如何使用父亲表示法来表示一棵树：

const int MAXN = 100010;
int fa[MAXN]; // 父亲数组
vector<int> son[MAXN]; // 存储每个节点的子节点

// 建立树的函数，root 表示根节点编号
void build_tree(int root) {
    queue<int> q;
    q.push(root);
    fa[root] = -1; // 根节点的父节点设为 -1
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < son[u].size(); ++i) {
            int v = son[u][i];
            if (v != fa[u]) { // 避免重复入队
                fa[v] = u; // v 的父节点为 u
                q.push(v);
            }
        }
    }
}

在上面的代码中，使用了一个 fa 数组来表示每个节点的父节点，其中 fa[root] = -1 表示根节点的父节点为特殊值 -1。同时，使用一个 son 数组来存储每个节点的子节点。

在建立树的函数中，首先将根节点入队，然后进行 BFS 遍历。对于每个节点 u，遍历其所有子节点 v，如果 v 的父节点不是 u，则将 v 的父节点设为 u，并将 v 入队，以便遍历其子节点。

使用父亲表示法可以有效地节省存储空间，同时还能够支持一些特殊的树算法，如 LCA（最近公共祖先）等。但是需要注意，使用父亲表示法表示一棵树时，不支持快速查找某个节点的子节点，需要进行线性遍历。

如果使用父亲表示法来实现一个二叉树，可以使用一个包含 val 和 fa 两个成员变量的结构体来表示二叉树的节点，其中 val 表示节点的值，fa 表示节点的父节点编号。

下面是一个示例代码，展示如何使用父亲表示法来表示一棵二叉树：

struct TreeNode {
    int val;
    int fa;
};

const int MAXN = 100010;
TreeNode node[MAXN];

// 建立二叉树的函数，root 表示根节点编号
void build_binary_tree(int root) {
    queue<int> q;
    q.push(root);
    node[root].fa = -1; // 根节点的父节点设为 -1
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        int lson = u * 2, rson = u * 2 + 1;
        if (lson <= n) {
            node[lson].fa = u;
            q.push(lson);
        }
        if (rson <= n) {
            node[rson].fa = u;
            q.push(rson);
        }
    }
}

在上面的代码中，使用了一个包含 val 和 fa 两个成员变量的结构体来表示二叉树的节点。同时，使用一个 node 数组来存储所有节点的信息。

在建立二叉树的函数中，首先将根节点入队，然后进行 BFS 遍历。对于每个节点 u，分别遍历其左右儿子 lson 和 rson，如果它们的编号在节点个数 n 的范围内，则将它们的父节点设为 u，并将它们入队，以便遍历它们的子节点。

使用父亲表示法来表示二叉树可以有效地节省存储空间，并且可以支持一些特殊的二叉树算法，如 Morris 遍历等。但是需要注意，使用父亲表示法表示二叉树时，不支持快速查找某个节点的左右儿子，需要进行线性遍历。

在父亲表示法中，每个节点都存储了它的父节点编号。这种表示法在一些情况下比较方便，比如可以方便地找到一个节点的父节点，也可以比较方便地实现一些算法，如 LCA（最近公共祖先）等。

但是，使用父亲表示法存储一棵树也存在一些缺点，例如：

1. 插入、删除节点时需要更新父节点指针，而且需要保证更新完毕之后整棵树依然合法，否则会导致程序出错。

2. 在进行节点查找时，需要从根节点开始遍历整棵树才能找到目标节点，这样的时间复杂度是 $O(n)$ 的。

3. 父亲表示法并不支持高效的树的重构操作。当需要重构一棵树时，需要重新构建整棵树，而无法利用已有的部分信息来高效地进行重构。

因此，在实际应用中，应根据具体的需求来选择合适的树的表示方法。当需要高效地进行节点查找或树的重构操作时，可能需要使用其他的树的表示方法，如孩子表示法、邻接表等。

另外，需要注意的是，父亲表示法有一些限制和约束条件，如：

1. 父节点编号必须唯一。即每个节点的父节点编号不能相同，否则无法正确地表示树的结构。

2. 根节点的父节点编号必须为一个特定值。根节点没有父节点，因此需要为其指定一个特殊的父节点编号，通常为 $-1$ 或 $0$ 等。

3. 节点的编号必须连续。如果使用数组来存储节点信息，则节点的编号必须从 $1$ 开始连续编号，否则无法正确地使用数组来访问节点信息。

4. 树的深度不能太大。由于父亲表示法需要存储每个节点的父节点编号，因此树的深度不能太大，否则会占用过多的存储空间，导致程序出错。

综上所述，父亲表示法是一种比较简单的树的表示方法，可以方便地实现一些算法，但也有一些限制和缺点，需要根据实际情况进行选择和权衡。