编写c语言算法,计算一棵二叉树的叶子结点总数.
时间: 2024-12-02 07:17:21 浏览: 31
在C语言中,我们可以编写一个递归算法来计算一棵二叉树的叶子节点总数。二叉树的叶子节点是没有子节点的节点,所以我们在遍历过程中只要检查当前节点是否为空,或者它的左右子节点是否都为空即可。
下面是一个简单的示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
int val; // 节点值
struct TreeNode* left; // 左子节点
struct TreeNode* right; // 右子节点
} TreeNode;
// 计算叶子节点函数
int countLeaves(TreeNode* root) {
if (root == NULL) { // 如果根节点为空,结束递归
return 0;
} else if (root->left == NULL && root->right == NULL) { // 如果节点是叶子节点
return 1; // 返回1
} else { // 否则,递归计算左、右子树的叶子节点数并相加
return countLeaves(root->left) + countLeaves(root->right);
}
}
int main() {
// 创建一个二叉树示例
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->val = 2;
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->val = 3;
root->right->left = (TreeNode*)malloc(sizeof(TreeNode));
root->right->left->val = 4;
root->right->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->right->val = 5;
// ...继续添加其他节点
int leafCount = countLeaves(root);
printf("这棵二叉树有 %d 个叶子节点.\n", leafCount);
return 0;
}
```
在这个程序中,我们首先检查根节点,如果是叶子节点就直接返回1;如果不是,则递归地计算左右子树的叶子节点数量,并将结果相加。
阅读全文