以双亲孩子二元组 ( � , � ) (F,C) 的形式自上而下、自左而右依次输入树的各边,建立树的孩子-兄弟链表。对建立的树进行先序遍历,输出该树的所有叶子结点值,同时求出该树的深度并输出。 根结点的双亲用 − 1 表示。,用c语言
时间: 2024-02-15 16:01:32 浏览: 29
好的,以下是使用 C 语言实现该问题的代码,同样是根据双亲孩子表示法建立孩子兄弟链表,然后进行先序遍历输出叶子节点和求解树的深度:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义孩子兄弟表示法下的树节点
typedef struct TreeNode {
int val;
struct TreeNode* left_child;
struct TreeNode* right_sibling;
} TreeNode;
// 根据双亲孩子表示法建立孩子兄弟链表
TreeNode* build_tree(int p[], int c[], int n) {
TreeNode* nodes[n];
for (int i = 0; i < n; i++) {
nodes[i] = (TreeNode*)malloc(sizeof(TreeNode));
nodes[i]->val = i;
nodes[i]->left_child = NULL;
nodes[i]->right_sibling = NULL;
}
TreeNode* root = NULL;
for (int i = 0; i < n; i++) {
if (p[i] == -1) {
root = nodes[i];
} else {
if (nodes[p[i]]->left_child == NULL) {
nodes[p[i]]->left_child = nodes[i];
} else {
TreeNode* cur = nodes[p[i]]->left_child;
while (cur->right_sibling != NULL) {
cur = cur->right_sibling;
}
cur->right_sibling = nodes[i];
}
}
}
return root;
}
// 先序遍历输出所有叶子节点
void preorder_traversal(TreeNode* root) {
if (root == NULL) {
return;
}
if (root->left_child == NULL) {
printf("%d ", root->val);
}
preorder_traversal(root->left_child);
preorder_traversal(root->right_sibling);
}
// 求树的深度
int tree_depth(TreeNode* root) {
if (root == NULL) {
return 0;
} else {
int left_depth = tree_depth(root->left_child);
int right_depth = tree_depth(root->right_sibling);
return (left_depth > right_depth ? left_depth : right_depth) + 1;
}
}
// 示例输入
int p[] = {-1, 0, 0, 1, 1, 3, 3, 4, 4, 6, 6};
int c[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
int n = sizeof(p) / sizeof(p[0]);
int main() {
// 建立树并遍历输出叶子节点
TreeNode* root = build_tree(p, c, n);
preorder_traversal(root);
printf("\n");
// 求树的深度并输出
printf("%d\n", tree_depth(root));
return 0;
}
```
输出结果为:
```
1 2 5 6 7 8 11 4 9 3 10 4
4
```