创建一个程序，为给定的有根树 T 的每个节点 u 输出以下信息。
u的节点号
u的父节点号
u的深度
u的节点类型（根、内部节点或叶）
u的孩子名单
这里我们假设给定的树有n个节点，每个节点都分配了一个从0到n-1的数字。
输入
输入的第一行给出节点数 n。在接下来的第 n 行，每个节点的信息按以下格式在一行中给出。
idkc1c2...ck
id 是节点号，k 是顺序。 c1c2...ck 表示第一个子节点的节点号，... 表示第k 个子节点的节点号。
输出
按照以下格式输出节点信息。按编号升序输出节点信息。
node id: parent = p, depth = d, type, [c1...ck]
p 表示父编号。但是，如果您没有父级，请将其设置为 -1。 d 表示节点的深度。
type 是分别代表根、内部节点和叶的根、内部节点或叶字符串之一。但是，如果根满足叶子和内部节点的条件，则应该是根。
c1c2...ck 是一个孩子的列表。请将其视为一个序列树，并按照输入的顺序输出。请注意逗号空格分隔符。检查输出示例中的输出格式。
数据约束
1 ≤ n ≤ 100,000
节点深度不超过20。
任何两个节点之间总是有一条路径。
输入样例
13
0 3 1 4 10
1 2 2 3
2 0
3 0
4 3 5 6 7
5 0
6 0
7 2 8 9
8 0
9 0
10 2 11 12
11 0
12 0
输出样例
node 0: parent = -1, depth = 0, root, [1, 4, 10]
node 1: parent = 0, depth = 1, internal node, [2, 3]
node 2: parent = 1, depth = 2, leaf, []
node 3: parent = 1, depth = 2, leaf, []
node 4: parent = 0, depth = 1, internal node, [5, 6, 7]
node 5: parent = 4, depth = 2, leaf, []
node 6: parent = 4, depth = 2, leaf, []
node 7: parent = 4, depth = 2, internal node, [8, 9]
node 8: parent = 7, depth = 3, leaf, []
node 9: parent = 7, depth = 3, leaf, []
node 10: parent = 0, depth = 1, internal node, [11, 12]
node 11: parent = 10, depth = 2, leaf, []
node 12: parent = 10, depth = 2, leaf, []
#include <stdio.h>
#define MAX 100005
#define NIL -1// 定义树的节点结构
struct Node {int p, l, r; // p 是父节点, l 是子节点, r 是右侧兄弟节点
};struct Node T[MAX]; // 树节点数组
int D[MAX]; // 存储每个节点的深度
int n; // 节点的数量// 打印一个节点的信息
void print(int u) {int i, c;printf("node %d: ", u);printf("parent = %d, ", T[u].p);printf("depth = %d, ", D[u]);if (T[u].p == NIL) {printf("root, ");} else if (T[u].l == NIL) {printf("leaf, ");} else {printf("internal node, ");}printf("[");for (i = 0, c = T[u].l; c != NIL; i++, c = T[c].r) {if (i) {printf(", ");}printf("%d", c);}printf("]\n");
}// 递归计算每个节点的深度
void rec(int u, int p) {D[u] = p;if (T[u].r != NIL) {rec(T[u].r, p); // 先递归右子树}if (T[u].l != NIL) {rec(T[u].l, p + 1); // 再递归左子树}
}int main() {int i, j, d, v, c, l, r;// 读入节点数量scanf("%d", &n);// 初始化所有节点的父节点、左子节点、右子节点为 NILfor (i = 0; i < n; i++) {T[i].p = T[i].l = T[i].r = NIL;}// 构建树for (i = 0; i < n; i++) {scanf("%d %d", &v, &d); // 输入当前节点编号和子节点数量l = NIL; // 初始化左子节点的指针for (j = 0; j < d; j++) {scanf("%d", &c); // 输入当前节点的子节点if (j == 0) {T[v].l = c; // 第一个子节点是左子节点} else {T[l].r = c; // 后续子节点是右子节点}l = c; // 更新左子节点T[c].p = v; // 设置当前子节点的父节点}}// 找到根节点（父节点是 NIL）for (i = 0; i < n; i++) {if (T[i].p == NIL) {r = i; // 根节点break;}}// 计算每个节点的深度rec(r, 0);// 输出每个节点的信息for (i = 0; i < n; i++) {print(i);}return 0;
}
