写一个c语言代码按先序遍历序列根据外部输入建立一个二叉树的二叉链表,统计二叉树中叶子结点个数和二叉树的深度。
时间: 2024-01-23 08:42:47 浏览: 80
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *left;
struct Node *right;
} Node;
Node *createNode(int data) {
Node *node = (Node *)malloc(sizeof(Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
Node *buildTree(int preorder[], int *index, int min, int max, int size) {
if (*index >= size) {
return NULL;
}
int val = preorder[*index];
if (val < min || val > max) {
return NULL;
}
Node *node = createNode(val);
(*index)++;
node->left = buildTree(preorder, index, min, val, size);
node->right = buildTree(preorder, index, val, max, size);
return node;
}
int countLeaves(Node *root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
return countLeaves(root->left) + countLeaves(root->right);
}
int maxDepth(Node *root) {
if (root == NULL) {
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
}
int main() {
int preorder[] = {5, 3, 1, 4, 7, 6, 8};
int size = sizeof(preorder) / sizeof(preorder[0]);
int index = 0;
Node *root = buildTree(preorder, &index, 0, 10000, size);
int leaves = countLeaves(root);
int depth = maxDepth(root);
printf("Leaves: %d\n", leaves);
printf("Depth: %d\n", depth);
return 0;
}
```
这里以先序遍历序列为例,根据外部输入建立二叉树。函数 `buildTree` 递归地建立二叉树,每次将序列中的第一个元素作为当前节点的值,然后继续递归建立左右子树。 `countLeaves` 和 `maxDepth` 分别用于统计二叉树的叶子结点个数和深度。
阅读全文