设计一算法,计算二叉树叶子结点总数。提示: int LeafCount ( BiTree T ) 如果是空树,则叶子结点个数为0; 否则,为:左子树的叶子结点个数+右子树的叶子结点个数。
时间: 2024-05-13 19:16:41 浏览: 33
二叉树叶子结点个数计算.doc
5星 · 资源好评率100%
下面是算法的C++代码实现:
```cpp
// 定义二叉树结点
typedef struct BiTNode
{
int data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
// 计算叶子结点总数
int LeafCount(BiTree T)
{
if (T == NULL)
{
// 空树
return 0;
}
else if (T->lchild == NULL && T->rchild == NULL)
{
// 叶子结点
return 1;
}
else
{
// 非叶子结点,递归计算左右子树的叶子结点总数
return LeafCount(T->lchild) + LeafCount(T->rchild);
}
}
```
算法核心思想就是递归遍历二叉树,如果当前结点是叶子结点,则返回1,否则递归计算左右子树的叶子结点总数,最终得到整棵树的叶子结点总数。
阅读全文