用二叉链表作为二叉树的数据表示,编写统计二叉树叶结点的算法
时间: 2023-11-14 11:10:33 浏览: 42
二叉链表的结构定义如下:
```c++
struct BiTNode{
char data;
BiTNode *lchild, *rchild;
};
typedef BiTNode *BiTree;
```
统计二叉树叶结点的算法可以采用递归的思想,对于每个节点,判断其左右子树是否为空,如果都为空,则该节点为叶节点,计数器加一,否则递归遍历其左右子树。
实现代码如下:
```c++
int countLeaves(BiTree root) {
if (root == nullptr) {
return 0;
}
if (root->lchild == nullptr && root->rchild == nullptr) {
return 1;
}
int leftCount = countLeaves(root->lchild);
int rightCount = countLeaves(root->rchild);
return leftCount + rightCount;
}
```
其中,`root`是指向二叉树根节点的指针。
相关问题
以二叉链表作为二叉树的存储结构,编写以下算法: 统计二叉树的叶结点个数的编码、
以下是统计二叉树叶结点个数的算法的Python代码实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def count_leaf_nodes(root):
if not root:
return 0
if not root.left and not root.right:
return 1
return count_leaf_nodes(root.left) + count_leaf_nodes(root.right)
# 测试代码
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
print(count_leaf_nodes(root)) # 输出 4
```
该算法的思路是,如果当前节点是空节点,那么返回0;如果当前节点是叶子节点(即左右子节点都为空),那么返回1;否则递归计算左右子树的叶子节点数量之和。时间复杂度为 $O(n)$,其中 $n$ 是二叉树的节点数。
以二叉链表作为二叉树的存储结构, 编写以下算法: (l) 统计二叉树的叶结点个数。用c语言写出完整的代码与注释
以下是统计二叉树叶节点个数的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) { // 如果当前节点为空,返回0
return 0;
} else if (!root->left && !root->right) { // 如果当前节点为叶节点,返回1
return 1;
} else { // 否则递归遍历左右子树,并将结果相加
return countLeaves(root->left) + countLeaves(root->right);
}
}
int main() {
// 构建以下二叉树
// 1
// / \
// 2 3
// / \
// 4 5
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->left->val = 2;
root->right->val = 3;
root->left->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->right = (TreeNode*)malloc(sizeof(TreeNode));
root->left->left->val = 4;
root->left->right->val = 5;
root->left->left->left = NULL;
root->left->left->right = NULL;
root->left->right->left = NULL;
root->left->right->right = NULL;
root->right->left = NULL;
root->right->right = NULL;
// 统计叶节点个数并输出
int count = countLeaves(root);
printf("The number of leaves in the binary tree is %d.\n", count);
return 0;
}
```
运行结果:
```
The number of leaves in the binary tree is 3.
```