以二叉链表为存储结构,统计二叉树的叶结点个数,用c语言实现
时间: 2024-02-29 08:53:10 浏览: 74
JAVA 实现二叉树(链式存储结构)
好的,以下是用C语言实现统计二叉树叶节点个数的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 统计叶节点个数
int countLeafNodes(TreeNode* root) {
// 如果树为空,返回0
if (root == NULL) {
return 0;
}
// 如果当前节点为叶节点,返回1
if (root->left == NULL && root->right == NULL) {
return 1;
}
// 递归计算左子树和右子树的叶节点个数
return countLeafNodes(root->left) + countLeafNodes(root->right);
}
int main() {
// 构造一颗二叉树
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->val = 2;
root->left->left = NULL;
root->left->right = NULL;
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->val = 3;
root->right->left = (TreeNode*)malloc(sizeof(TreeNode));
root->right->left->val = 4;
root->right->left->left = NULL;
root->right->left->right = NULL;
root->right->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->right->val = 5;
root->right->right->left = NULL;
root->right->right->right = NULL;
// 统计叶节点个数
int count = countLeafNodes(root);
printf("The number of leaf nodes is: %d\n", count);
return 0;
}
```
以上代码中,我们定义了一个二叉树结构体`TreeNode`,包含节点值`val`、左子树指针`left`和右子树指针`right`。我们通过构造一颗二叉树来演示如何统计叶节点个数。具体实现是通过递归的方式,如果当前节点为叶节点,则返回1,否则递归计算左子树和右子树的叶节点个数,并相加返回。最终输出叶节点个数。
阅读全文