设计算法求二叉树所包含的叶结点的数目。(给出设计思想(10分)用c语言实现
时间: 2024-06-13 12:06:33 浏览: 9
设计思想:
1. 如果二叉树为空,则叶结点数为0。
2. 如果二叉树只有一个结点,则叶结点数为1。
3. 如果二叉树不为空且有左右子树,则叶结点数为左子树的叶结点数加上右子树的叶结点数。
C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 创建二叉树
TreeNode* createTree() {
int val;
scanf("%d", &val);
if (val == -1) {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = val;
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 main() {
// 创建二叉树
TreeNode* root = createTree();
// 计算叶结点数目
int count = countLeaf(root);
printf("叶结点数目为:%d\n", count);
// 释放内存
free(root);
return 0;
}
```