一个二叉树(存储结构为二叉链表)求该树的叶结点个数,写出算法代码。c
时间: 2024-10-28 10:11:41 浏览: 14
在C语言中,我们可以使用递归的方式来解决二叉树的叶节点计数问题。对于二叉链表表示的二叉树,每个节点都有一个左指针、右指针和一个标志(通常是一个布尔值)来判断是否是叶子节点。以下是递归算法的代码实现:
```c
#include <stdbool.h>
// 定义二叉树节点
typedef struct TreeNode {
int val; // 节点值
struct TreeNode* left; // 左子节点
struct TreeNode* right; // 右子节点
bool isLeaf; // 是否是叶子节点
} TreeNode;
// 计算二叉树叶节点数量的函数
int countLeaves(TreeNode* root) {
if (root == NULL) { // 如果节点为空,返回0
return 0;
}
if (root->isLeaf) { // 如果当前节点是叶子节点,计数加一
return 1 + countLeaves(root->left) + countLeaves(root->right);
} else { // 否则递归计算左右子树的叶节点数
return countLeaves(root->left) + countLeaves(root->right);
}
}
```
在这个算法中,我们首先检查当前节点是否为空,如果为空则直接返回0。然后检查当前节点是否是叶子节点,如果是,则返回1加上其左子树和右子树的叶节点数之和;如果不是叶子节点,只递归地计算其左右子树的叶节点数。
阅读全文