假设二又树中的每个结点值为单个字符,采用顺序存储结构存储。设计一个算法,求二叉树t中的叶子结点个个数。完整C语言代码
时间: 2024-02-29 14:51:32 浏览: 22
下面是完整的 C 语言代码实现:
```c
#include <stdio.h>
#define MAX_TREE_SIZE 100 // 二叉树的最大结点数
typedef char ElementType; // 假设结点值为字符类型
ElementType tree[MAX_TREE_SIZE]; // 用一维数组存储二叉树结点
int CountLeaf(const ElementType* tree, int n, int root)
{
if (root >= n || tree[root] == '#') {
return 0; // 空树或空结点,返回0
}
if (root * 2 >= n || tree[root * 2] == '#') {
return 1; // 左右子树都为空,说明是叶子结点,返回1
}
return CountLeaf(tree, n, root * 2) + CountLeaf(tree, n, root * 2 + 1);
}
int main()
{
// 构造一个二叉树,用 # 表示空结点
tree[1] = 'A';
tree[2] = 'B';
tree[3] = 'C';
tree[4] = 'D';
tree[5] = '#';
tree[6] = 'E';
tree[7] = '#';
tree[8] = '#';
tree[9] = 'F';
tree[10] = '#';
tree[11] = 'G';
tree[12] = '#';
tree[13] = '#';
tree[14] = '#';
tree[15] = 'H';
int count = CountLeaf(tree, 16, 1);
printf("叶子结点个数为:%d\n", count);
return 0;
}
```
这里构造了一个二叉树,用 `#` 来表示空结点,然后调用 `CountLeaf` 函数计算二叉树中的叶子结点个数。输出结果为:
```
叶子结点个数为:5
```