c++ - 计算存储为向量数组 C++ 的通用树的每个节点的高度

Question

我在 C++ 中以向量数组的形式存储了一棵树，这样每行的第一列由该节点的子节点总数组成，然后每行的后续列由所有子节点的索引组成那个节点的。

vector <long long int> nodes[N];

例如 - 有N=8节点，如果v是 的直接子节点，则u给定树的节点是

u v
1 2
1 3
2 4
2 5
4 6
4 7
6 8

那么向量数组nodes将是

0. 2 2 3
1. 2 4 5
2. 0
3. 2 6 7
4. 0
5. 1 8
6. 0
7. 0

现在，我想将每个节点的高度保存在一个大小为 N 的新数组中。如何为此开发算法？

标签： c++algorithmdata-structurestree

Answer 1

您可以使用此函数计算树中每个节点的高度。

它是一个简单的树的 DFS，根为0.

int height(vector<int> nodes[], vector<int> &arr, int u, int p){
    int ans = 0;
    for(int i=1;i<=nodes[u][0];i++){
        if(nodes[u][i]!=p){
            ans=max(ans, height(nodes, arr, nodes[u][i], u));
        }
    }
    return arr[u] = 1 + ans;
}

该函数可以如下调用：height(nodes, arr, 0, -1)其中arr是一个大小为空的向量，n即，vector<int> arr(n, 0);