设计一算法,计算二叉树叶子结点总数。 提示:int LeafCount(BiTree T) 如果是空树,则叶子结点个数为0; 否则,为:左子树的叶子结点个数+右子树的叶子结点个数。
时间: 2023-06-18 17:07:27 浏览: 84
利用结点总数与分支总数求解问题-树和二叉树
下面是计算二叉树叶子结点总数的算法实现,使用递归的方式:
```
int LeafCount(BiTree T) {
if (T == NULL) { // 空树,叶子结点个数为0
return 0;
}
if (T->lchild == NULL && T->rchild == NULL) { // 叶子结点
return 1;
}
return LeafCount(T->lchild) + LeafCount(T->rchild); // 左子树叶子结点个数 + 右子树叶子结点个数
}
```
算法思路:
1. 若二叉树为空,则叶子结点个数为0;
2. 若当前结点是叶子结点,则叶子结点个数为1;
3. 否则,递归计算左子树的叶子结点个数和右子树的叶子结点个数,然后将它们相加。
注意:这里的二叉树是指二叉树的链式存储结构,结点结构体为:
```
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
```
阅读全文