根据给定的双亲孩子有序对创建树的二叉链表存储结构,并计算叶子结点个数、计算树的深度
时间: 2023-04-22 17:05:17 浏览: 123
二叉树的建立,遍历及计算叶子节点,深度计算
根据给定的双亲孩子有序对创建树的二叉链表存储结构,可以按照以下步骤进行:
1. 定义一个结构体,包含一个数据域和两个指针域,分别指向左右子树。
2. 定义一个数组,存储每个结点的双亲结点的下标。
3. 遍历数组,对于每个结点,创建一个新的结构体,并将其指针域初始化为NULL。
4. 遍历数组,对于每个结点,如果其双亲结点下标为-1,则将其作为根结点,否则将其挂在双亲结点的左右子树中。
5. 遍历整个树,统计叶子结点的个数,即没有左右子树的结点个数。
6. 计算树的深度,可以使用递归的方式,对于每个结点,计算其左右子树的深度,取最大值加1即可。
示例代码如下:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
int main() {
int n; // 结点个数
scanf("%d", &n);
int parent[n]; // 双亲结点数组
for (int i = ; i < n; i++) {
scanf("%d", &parent[i]);
}
TreeNode *root = NULL; // 根结点指针
TreeNode *nodes[n]; // 结点指针数组
for (int i = ; i < n; i++) {
TreeNode *node = (TreeNode *) malloc(sizeof(TreeNode));
node->data = i;
node->left = NULL;
node->right = NULL;
nodes[i] = node;
}
for (int i = ; i < n; i++) {
if (parent[i] == -1) {
root = nodes[i];
} else {
TreeNode *parent_node = nodes[parent[i]];
if (parent_node->left == NULL) {
parent_node->left = nodes[i];
} else {
parent_node->right = nodes[i];
}
}
}
int leaf_count = ; // 叶子结点个数
int depth = ; // 树的深度
void count_leaf(TreeNode *node) {
if (node == NULL) {
return;
}
if (node->left == NULL && node->right == NULL) {
leaf_count++;
}
count_leaf(node->left);
count_leaf(node->right);
}
void calc_depth(TreeNode *node, int d) {
if (node == NULL) {
return;
}
if (d > depth) {
depth = d;
}
calc_depth(node->left, d + 1);
calc_depth(node->right, d + 1);
}
count_leaf(root);
calc_depth(root, 1);
printf("叶子结点个数:%d\n", leaf_count);
printf("树的深度:%d\n", depth);
return ;
}
```
阅读全文