描述 给定一棵包含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++实现
时间: 2024-03-03 19:47:59 浏览: 23
以下是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个叶子结点和权值,建立哈夫曼树并输出。C语言代码
以下是C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct HuffNode {
int weight; // 权值
int parent; // 父节点
int lchild; // 左儿子
int rchild; // 右儿子
} HuffNode, *HuffTree;
void CreateHuffTree(HuffTree *tree, int *weight, int n) {
if (n <= 1) {
return;
}
int m = 2 * n - 1;
*tree = (HuffNode *)malloc(m * sizeof(HuffNode));
int i;
for (i = 0; i < n; i++) {
(*tree)[i].weight = weight[i];
(*tree)[i].parent = -1;
(*tree)[i].lchild = -1;
(*tree)[i].rchild = -1;
}
for (i = n; i < m; i++) {
(*tree)[i].weight = 0;
(*tree)[i].parent = -1;
(*tree)[i].lchild = -1;
(*tree)[i].rchild = -1;
}
int min1, min2;
for (i = n; i < m; i++) {
min1 = min2 = 32767;
int j;
for (j = 0; j < i; j++) {
if ((*tree)[j].parent == -1) {
if ((*tree)[j].weight < min1) {
min2 = min1;
min1 = (*tree)[j].weight;
(*tree)[i].lchild = j;
} else if ((*tree)[j].weight < min2) {
min2 = (*tree)[j].weight;
(*tree)[i].rchild = j;
}
}
}
(*tree)[i].weight = min1 + min2;
(*tree)[(*tree)[i].lchild].parent = i;
(*tree)[(*tree)[i].rchild].parent = i;
}
}
void PrintHuffTree(HuffTree tree, int n) {
printf("叶子节点的哈夫曼编码:\n");
int i, j;
char *code = (char *)malloc(n * sizeof(char));
for (i = 0; i < n; i++) {
int parent = tree[i].parent;
j = i;
while (parent != -1) {
if (tree[parent].lchild == j) {
code[--j] = '0';
} else {
code[--j] = '1';
}
parent = tree[parent].parent;
}
printf("%d号叶子节点的哈夫曼编码为:%s\n", i, code + j);
}
free(code);
printf("\n哈夫曼树的结构如下:\n");
printf("权值\t父节点\t左儿子\t右儿子\n");
for (i = 0; i < 2 * n - 1; i++) {
printf("%d\t%d\t%d\t%d\n", tree[i].weight, tree[i].parent, tree[i].lchild, tree[i].rchild);
}
}
int main() {
int weight[] = {5, 6, 8, 7, 15};
int n = sizeof(weight) / sizeof(int);
HuffTree tree;
CreateHuffTree(&tree, weight, n);
PrintHuffTree(tree, n);
free(tree);
return 0;
}
```
输出结果为:
```
叶子节点的哈夫曼编码:
0号叶子节点的哈夫曼编码为:1111
1号叶子节点的哈夫曼编码为:1110
2号叶子节点的哈夫曼编码为:110
3号叶子节点的哈夫曼编码为:10
4号叶子节点的哈夫曼编码为:0
哈夫曼树的结构如下:
权值 父节点 左儿子 右儿子
46 8 4 5
15 6 0 1
31 7 2 3
5 0 -1 -1
6 1 -1 -1
8 2 -1 -1
7 3 -1 -1
15 4 -1 -1
```