版权声明:本文为博主原创文章,转载请注明出处。 https://blog.csdn.net/twilight_karl/article/details/53468024
二叉树采用链式储存结构,设计算法计算一颗给定的二叉树中叶子节点的数目
使用递归创建并初始化二叉树。当输入的数据不为“#”时,将该元素视为一个有效的元素,否则置为null。每次递归返回当前位置的子树。
计算二叉树的所有叶子节点的数量。当一个节点的左孩子和右孩子都为空时。他是叶子节点。使用递归如果能找到就返回1,如果节点为NULL返回0,否则返回count(t->lchild)+ count(t->rchild)
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef struct node{
char data ;
struct node * lchild;
struct node * rchild;
}BiTree;
BiTree * CreatTree();
int Count(BiTree * );
void Preorder(BiTree *);
int main(){
BiTree * top = NULL;
top = CreatTree();
printf("遍历结果: ");
Preorder(top);
putchar('\n');
printf("叶子节点的个数: %d\n",Count(top));
system("pause");
return 0;
}
BiTree * CreatTree(){
BiTree *t;
char ch ;
ch = getchar();
if (ch != '#'){
t = (BiTree *)malloc(sizeof(BiTree));
t ->data = ch ;
t->lchild = CreatTree();
t->rchild = CreatTree();
}
else{
t=NULL;
}
return t;
}
int Count(BiTree * top){
if(top == NULL){
return 0;
}
else if ((top->lchild==NULL) && (top->rchild==NULL)){
return 1;
}
else{
return Count(top->lchild)+Count(top->rchild);
}
}
void Preorder(BiTree * top ){
if(top != NULL){
printf("%c ",top->data);
Preorder(top->lchild);
Preorder(top->rchild);
}
}