假设在二叉树中每个节点的值为单个字符,用顺序存储结构存储,设计一个算法,求二叉树b中第k层叶子节点个数的C语言代码
时间: 2024-03-23 15:38:38 浏览: 22
以下是求二叉树第k层叶子节点个数的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_TREE_SIZE 100 //定义二叉树的最大节点数
typedef char ElemType; //定义节点值的数据类型
typedef struct BiTNode //定义二叉树节点结构体
{
ElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
//按先序遍历顺序构建二叉树
void CreateBiTree(BiTree *T)
{
ElemType ch;
scanf("%c", &ch);
if (ch == '#')
{
*T = NULL;
}
else
{
*T = (BiTree)malloc(sizeof(BiTNode));
(*T)->data = ch;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}
//求二叉树第k层叶子节点个数
int CountLeaf(BiTree T, int k)
{
if (T == NULL || k < 1)
{
return 0;
}
if (k == 1) //找到第k层
{
if (T->lchild == NULL && T->rchild == NULL) //是叶子节点
{
return 1;
}
else
{
return 0;
}
}
else //递归遍历左右子树
{
return CountLeaf(T->lchild, k-1) + CountLeaf(T->rchild, k-1);
}
}
int main()
{
BiTree T;
printf("请按先序遍历顺序输入二叉树节点的值:\n");
CreateBiTree(&T);
int k;
printf("请输入要求的层数k:");
scanf("%d", &k);
int count = CountLeaf(T, k);
printf("第%d层叶子节点个数为:%d\n", k, count);
return 0;
}
```
注意:本代码中#表示空节点,构建二叉树时输入时可用。