假设二叉树中的每个结点值为单个字符,采用顺序存储结构存储。设计一个算法,求二叉树t中的叶子结点个数
时间: 2024-02-29 21:52:43 浏览: 71
西南交通大学-数据结构实验报告-求二叉树某结点在先序、中序、后序遍历中的访问次序
以下是求二叉树叶子结点个数的算法:
1. 定义一个计数器count,初始值为0。
2. 从根节点开始遍历二叉树,如果当前节点是叶子节点,即左右子树均为空,则count加1。
3. 如果当前节点不是叶子节点,则分别递归遍历左右子树,将左右子树的叶子节点个数相加,得到当前节点的叶子节点个数。
4. 最后返回count即可。
以下是该算法的C++代码实现:
```c++
int countLeafNodes(BiTree t) {
if (t == NULL) { // 如果当前节点为空,返回0
return 0;
}
if (t->lchild == NULL && t->rchild == NULL) { // 如果当前节点是叶子节点,返回1
return 1;
} else { // 如果当前节点不是叶子节点,递归遍历左右子树
int leftCount = countLeafNodes(t->lchild);
int rightCount = countLeafNodes(t->rchild);
return leftCount + rightCount; // 返回左右子树叶子节点个数之和
}
}
```
该算法的时间复杂度为O(n),其中n为二叉树中节点的个数。
阅读全文