C语言:按先序遍历序列建立一个二叉树的二叉链表,统计二叉树中叶子结点个数和二叉树的深度。
时间: 2024-01-23 21:44:42 浏览: 88
求二叉树的建立、遍历、叶子结点树、深度
5星 · 资源好评率100%
实现思路:
1. 先根据先序遍历序列创建二叉树,如果当前的字符不为 #,则新建一个结点,并将其插入到树中;如果为 #,则返回上一层结点。
2. 统计二叉树中叶子结点的个数,只需要判断当前结点是否为空,如果为空则返回 0;如果不为空,则判断当前结点的左右子树是否为空,如果左右子树都为空,则说明当前结点为叶子结点,返回 1;否则递归遍历左右子树。
3. 求二叉树的深度,只需要判断当前结点是否为空,如果为空则返回 0;否则分别递归遍历左右子树,取左右子树深度的最大值,再加上 1,即为当前结点所在子树的深度。
代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
char data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 根据先序遍历序列创建二叉树
TreeNode* createTree() {
char ch;
scanf("%c", &ch);
if (ch == '#') {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->data = ch;
root->left = createTree();
root->right = createTree();
return root;
}
// 统计二叉树中叶子结点的个数
int countLeaf(TreeNode* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
return countLeaf(root->left) + countLeaf(root->right);
}
// 求二叉树的深度
int maxDepth(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
int main() {
printf("请输入先序遍历序列:\n");
TreeNode* root = createTree();
int numLeaf = countLeaf(root);
int depth = maxDepth(root);
printf("二叉树中叶子结点的个数为:%d\n", numLeaf);
printf("二叉树的深度为:%d\n", depth);
return 0;
}
```
阅读全文