设计一算法,计算二叉树叶子结点总数。提示: int LeafCount ( BiTree T ) 如果是空树,则叶子结点个数为0; 否则,为:左子树的叶子结点个数+右子树的叶子结点个数。
时间: 2023-06-26 09:05:42 浏览: 146
二叉树叶子结点个数计算.doc
5星 · 资源好评率100%
可以使用递归的方式实现计算二叉树叶子结点总数的算法,具体实现如下:
```c
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
int LeafCount(BiTree T) {
if (T == NULL) {
return 0;
}
if (T->lchild == NULL && T->rchild == NULL) {
// 当前节点是叶子节点
return 1;
}
// 左子树的叶子结点个数+右子树的叶子结点个数
return LeafCount(T->lchild) + LeafCount(T->rchild);
}
```
在主函数中,我们可以构造一个二叉树并计算其叶子结点总数:
```c
int main() {
BiTNode n1 = {1, NULL, NULL};
BiTNode n2 = {2, NULL, NULL};
BiTNode n3 = {3, &n1, NULL};
BiTNode n4 = {4, &n2, NULL};
BiTNode n5 = {5, &n3, &n4};
BiTNode n6 = {6, NULL, NULL};
BiTNode n7 = {7, &n6, &n5};
BiTree T = &n7;
printf("Leaf count: %d\n", LeafCount(T)); // 输出结果:Leaf count: 3
return 0;
}
```
上述代码中,我们构造了一个二叉树,根据计算叶子结点总数的算法,其叶子结点总数应为3。最终输出结果也是3,说明算法实现正确。
阅读全文