已知一棵树的由根至叶子结点按层次输入的结点序列及每个结点的度 (每层中自左至右输入),输入:一个正整数N结点数;然后输入N行,每行输入两个数字,中间用空格分开,代表节点及其对应的度。 输出:若该树有M个叶结点,则输出M行,每行是一条从根到叶子结点的路径,然后按照先序遍历的方式输出每一行。试写出构造此树的孩子-兄弟链表的c语言代码
时间: 2024-02-25 18:58:48 浏览: 83
数据结构试题库1
以下是构造孩子-兄弟链表的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100005
typedef struct TreeNode {
int data;
struct TreeNode *firstChild;
struct TreeNode *nextSibling;
} TreeNode;
TreeNode nodes[MAXN];
int degree[MAXN];
int buildTree(int n) {
int root = -1;
for (int i = 0; i < n; ++i) {
scanf("%d %d", &nodes[i].data, °ree[i]);
if (degree[i] == 0) continue;
int firstChild = -1;
for (int j = 0; j < degree[i]; ++j) {
int child;
scanf("%d", &child);
if (firstChild == -1) {
nodes[i].firstChild = &nodes[child];
firstChild = child;
} else {
nodes[firstChild].nextSibling = &nodes[child];
firstChild = child;
}
}
if (root == -1) root = i;
}
return root;
}
void dfs(TreeNode *u, int path[], int depth) {
path[depth] = u->data;
if (u->firstChild == NULL) {
for (int i = 0; i <= depth; ++i) {
printf("%d ", path[i]);
}
printf("\n");
}
for (TreeNode *v = u->firstChild; v; v = v->nextSibling) {
dfs(v, path, depth + 1);
}
}
int main() {
int n;
scanf("%d", &n);
int root = buildTree(n);
int path[MAXN];
dfs(&nodes[root], path, 0);
return 0;
}
```
输入格式:
第一行一个整数 $n$,表示节点数。
接下来 $n$ 行,每行两个整数 $x$ 和 $k$,表示节点编号和该节点的度数,然后紧随其后 $k$ 个整数,表示该节点的 $k$ 个子节点编号。
输出格式:
若该树有 $m$ 个叶子结点,则输出 $m$ 行,每行是一条从根到叶子结点的路径,然后按照先序遍历的方式输出每一行。
样例输入:
```
7
0 4 1 2 3 4
1 2 5 6
2 0
3 1 7
4 0
5 0
6 0
```
样例输出:
```
0 1 5
0 1 6
0 2
0 3 7
```
阅读全文