有根树【东北大学oj数据结构7-1】C语言

创建一个程序，为给定的有根树 T 的每个节点 u 输出以下信息。

u的节点号
u的父节点号
u的深度
u的节点类型（根、内部节点或叶）
u的孩子名单
这里我们假设给定的树有n个节点，每个节点都分配了一个从0到n-1的数字。

输入

输入的第一行给出节点数 n。在接下来的第 n 行，每个节点的信息按以下格式在一行中给出。
idkc1​c2​...ck​

id 是节点号，k 是顺序。 c1​c2​...ck​ 表示第一个子节点的节点号，... 表示第k 个子节点的节点号。

输出

按照以下格式输出节点信息。按编号升序输出节点信息。

node id: parent = p, depth = d, type, [c1...ck]

p 表示父编号。但是，如果您没有父级，请将其设置为 -1。 d 表示节点的深度。
type 是分别代表根、内部节点和叶的根、内部节点或叶字符串之一。但是，如果根满足叶子和内部节点的条件，则应该是根。
c1​c2​...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);
 
    // 初始化所有节点的父节点、左子节点、右子节点为 NIL
    for (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;
}

 

 

原文地址：https://blog.csdn.net/2401_84017541/article/details/144404917

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！