C语言 按先序遍历序列建立一个二叉树的二叉链表,统计二叉树中叶子结点个数和二叉树的深度。
时间: 2024-01-23 13:39:29 浏览: 97
可以使用递归实现先序遍历序列建立二叉树的过程,同时统计叶子节点个数和深度。
具体实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
char data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 先序遍历序列建立二叉树
TreeNode *create_tree() {
char c;
scanf("%c", &c);
if (c == '#') { // '#'表示空节点
return NULL;
}
TreeNode *node = (TreeNode *) malloc(sizeof(TreeNode));
node->data = c;
node->left = create_tree();
node->right = create_tree();
return node;
}
// 统计叶子节点个数
int count_leaf(TreeNode *root) {
if (root == NULL) {
return 0;
} else if (root->left == NULL && root->right == NULL) {
return 1;
} else {
return count_leaf(root->left) + count_leaf(root->right);
}
}
// 计算二叉树深度
int depth(TreeNode *root) {
if (root == NULL) {
return 0;
} else {
int left_depth = depth(root->left);
int right_depth = depth(root->right);
return (left_depth > right_depth ? left_depth : right_depth) + 1;
}
}
int main() {
printf("请输入先序遍历序列(空节点用 # 表示):");
TreeNode *root = create_tree();
printf("叶子节点个数为:%d\n", count_leaf(root));
printf("二叉树深度为:%d\n", depth(root));
return 0;
}
```
注意,输入先序遍历序列时需要在每个节点后输入一个空格,最后一个节点后不需要输入空格,否则会导致程序出错。例如,如果要输入先序遍历序列 A B # # C # D E # # #,则应该输入 A B # # C # D E # # #(没有空格)。
阅读全文