已知一颗树的结点序列以及每个结点的度,构造树的兄弟孩子链表,请给我这道题的C语言代码
时间: 2024-02-03 18:11:39 浏览: 67
以下是构造树的兄弟孩子链表的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_NODE_NUM 100
typedef struct Node {
int val;
struct Node* parent;
struct Node* left_child;
struct Node* right_sibling;
} Node;
Node nodes[MAX_NODE_NUM]; // 存储所有结点
int node_num; // 结点个数
Node* create_node(int val) { // 创建结点
Node* node = (Node*)malloc(sizeof(Node));
node->val = val;
node->parent = NULL;
node->left_child = NULL;
node->right_sibling = NULL;
return node;
}
void construct_tree(int* degrees, int n, int* vals) { // 构造树
node_num = n;
for (int i = 0; i < n; i++) {
nodes[i] = *create_node(vals[i]);
}
for (int i = 1; i < n; i++) {
int d = degrees[i];
Node* parent = &nodes[d];
Node* child = &nodes[i];
child->parent = parent;
child->right_sibling = parent->left_child;
parent->left_child = child;
}
}
void print_tree(Node* node, int depth) { // 打印树
for (int i = 0; i < depth; i++) {
printf(" ");
}
printf("%d\n", node->val);
Node* child = node->left_child;
while (child != NULL) {
print_tree(child, depth + 1);
child = child->right_sibling;
}
}
int main() {
int degrees[] = {-1, 0, 1, 2, 2, 3}; // 每个结点的度
int vals[] = {0, 1, 2, 3, 4, 5}; // 结点序列
construct_tree(degrees, 6, vals);
print_tree(&nodes[0], 0);
return 0;
}
```
在该代码中,我们使用了一个`Node`结构体来表示树的结点,其中包含了结点的值、父结点指针、左孩子指针和右兄弟指针。`create_node`函数用于创建结点,`construct_tree`函数用于构造树,`print_tree`函数用于打印树。在`construct_tree`函数中,我们依次遍历每个结点,将其作为其父结点的孩子结点插入到树中。具体来说,我们先找到该结点的父结点,并将该结点的父结点指针和右兄弟指针设置为其父结点的左孩子和当前结点的右兄弟。在`print_tree`函数中,我们先打印该结点的值,然后遍历它的每个孩子结点,并递归打印它们。
阅读全文