C语言用二叉链表作为二叉树的存储表示,编写统计二叉树中叶结点数的算法
时间: 2024-02-03 18:12:31 浏览: 24
二叉链表是一种常用的二叉树存储结构,可以使用递归实现统计二叉树中叶子节点数的算法。
具体实现思路如下:
1. 如果二叉树为空,则叶子节点数为0。
2. 如果二叉树只有根节点,则叶子节点数为1。
3. 递归计算左子树中叶子节点数和右子树中叶子节点数,然后将它们相加即可得到整棵二叉树中叶子节点数。
下面是使用C语言实现的代码:
```c
// 定义二叉树结点
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 统计二叉树中叶子节点数的函数
int count_leaf_nodes(TreeNode* root) {
if (root == NULL) { // 1. 如果二叉树为空,则叶子节点数为0。
return 0;
} else if (root->left == NULL && root->right == NULL) { // 2. 如果二叉树只有根节点,则叶子节点数为1。
return 1;
} else { // 3. 递归计算左子树和右子树中叶子节点数,然后将它们相加即可得到整棵二叉树中叶子节点数。
return count_leaf_nodes(root->left) + count_leaf_nodes(root->right);
}
}
```
需要注意的是,此代码中的二叉树是一棵普通的二叉树,并不是一个二叉搜索树。如果是二叉搜索树,可以对算法进行优化,具体实现就不赘述了。