描述 给定一棵包含N个结点的树，结点编号1~N，其中1号结点是根。请你计算它每一个结点的深度是多少。 规定根结点的深度为0，其余结点的深度是其父节点深度+1。 输入 第一行包含一个整数N。(1 <= N <= 10000) 以下N行每行包含一个整数，其中第i行代表i号结点的父节点编号。(根的父节点编号为-1) 输出 输出N行每行一个整数，依次代表1~N号结点的深度。 样例输入 5 -1 1 1 2 2 样例输出 0 1 1 2 2 c++实现

以下是C++的实现代码：

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 10005;

vector<int> g[MAXN];
int depth[MAXN];

void dfs(int u, int d) {
    depth[u] = d;
    for (int v : g[u]) {
        dfs(v, d + 1);
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int p;
        cin >> p;
        if (p != -1) {
            g[p].push_back(i);
        }
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++) {
        cout << depth[i] << endl;
    }
    return 0;
}

在这个实现中，我们首先读入节点数n，并在下面的循环中读入每个节点的父节点。如果父节点不是根节点，则将当前节点加入其父节点的邻接表中。然后从根节点开始进行深度优先遍历，依次计算每个节点的深度，并保存在depth数组中。最后输出depth数组即可。

相关问题

使用Python语言，题目描述 对于一棵多叉树，我们可以通过 “左孩子右兄弟” 表示法，将其转化成一棵二叉树。 如果我们认为每个结点的子结点是无序的，那么得到的二叉树可能不唯一。 换句话说，每个结点可以选任意子结点作为左孩子，并按任意顺序连接右兄弟。 给定一棵包含 NN​​ 个结点的多叉树，结点从 11​​ 至 NN​ 编号，其中 11 号结点是根，每个结点的父结点的编号比自己的编号小。 请你计算其通过 “左孩子右兄弟” 表示法转化成的二叉树，高度最高是多少。 注：只有根结点这一个结点的树高度为 00​。 输入描述 输入的第一行包含一个整数 NN​​​。 以下 N −1N−1​​ 行，每行包含一个整数，依次表示 22​ 至 NN 号结点的父结点编号。 输出描述 输出一个整数表示答案。

在 Python 中，我们可以使用字典来表示多叉树的结构，字典的键表示结点的编号，值表示结点的子结点的编号列表。

为了计算二叉树的高度，我们需要对每个结点求出其左子树和右子树的高度。

下面是一个 Python 的代码实现，它使用递归的方法计算二叉树的高度：

def height(tree, node):
    # 如果当前结点没有子结点，则高度为 0
    if node not in tree:
        return 0

    # 递归计算左子树和右子树的高度
    left_height = height(tree, tree[node][0])
    right_height = height(tree, tree[node][1])

    # 返回当前结点的高度，它等于左子树和右子树高度的最大值加 1
    return max(left_height, right_height) + 1

我们可以使用以下代码来读入输入数据并调用 `height` 函数：

# 读入输入数据
n = int(input())
tree = {}
for i in range(2, n+1):
    parent = int(input())
    if parent in tree:
        tree[parent].append(i)
    else:
        tree[parent] = [i]

# 计算二叉树的高度
result = height(tree, 1)

# 输出结果
print(result)

希望这些信息对你有帮助。

使用图例表示这个题目描述 一棵树有n个结点，已知树上所有的父子结点关系，请问该树的根是几号结点，哪个结点的子结点最多，该结点有哪些子结点。 输入描述 第一行，有1个整数n代表结点数量（0<n≤100） 接下来若干行；每行两个结点x和y，表示y是x的孩子(1≤x,y≤1000) 请注意：树上结点的编号不一定是连续的 输出描述 第一行输出树根的编号。 第二行输出孩子最多的结点编号（如果有多个结点的子结点都是最多的，则输出编号最大的那个）。 第三行输出第二行求出的孩子最多的结点，有哪些孩子，按照编号从小到大，输出这些孩子的编号，用空格隔开。

假设给定的父子结点关系为：

1 --> 2
1 --> 3
2 --> 4
2 --> 5
3 --> 6
4 --> 7
5 --> 8

则可以画出如下的树形图：

    1
   / \
  2   3
 / \
4   5
   / \
  7   8

其中，根节点是1，2和3是根节点的子节点，2和3分别有2个子节点，其中2号节点的子节点最多，有2个，它的子节点列表为4和5，按照编号从小到大排列为4 5。因此，输出应为：

1
2
4 5