请问该如何去统计二叉树中叶子结点的个数？求解释~

Question

1. 在文件test.cpp中已经给出的创建一个二叉树的算法的基础上，分别设计递归和非递归的算法统计该二叉树中叶子结点的个数。test.cpp 的内容如下：#include <stdio.h>#include <malloc.h>typedef char datatype; /*结点属性值的类型*/typedef struct node{ /*二叉树结点的类型*/datatype data;struct node *leftchild, *rightchild;}BiTreeNode;#define Max 100typedef struct{BiTreeNode* data[Max];int top;}seqstack;FILE *rf ;void Initiate(BiTreeNode **root) //二叉树的初始化{*root=(BiTreeNode*)malloc(sizeof(BiTreeNode));(*root)->leftchild=NULL;(*root)->rightchild=NULL;}void Destroy(BiTreeNode **root) //释放二叉树{if((*root)!=NULL &&(*root)->leftchild!=NULL)Destroy(&(*root)->leftchild);if((*root)!=NULL &&(*root)->rightchild!=NULL)Destroy(&(*root)->rightchild);free(*root);}void createbintree(BiTreeNode **t) //创建二叉树{char ch;if ((ch=fgetc(rf))==' '){*t=NULL;}else{*t=(BiTreeNode *)malloc(sizeof(BiTreeNode ));/*生成二叉树的根结点*/(*t)->data=ch;createbintree(&(*t)->leftchild);/*递归实现左子树的建立*/createbintree(&(*t)->rightchild);/*递归实现右子树的建立*/}} void push(seqstack *s,BiTreeNode *t)/*进栈*/{s->data[++s->top]=t;}BiTreeNode* pop(seqstack *s)/*出栈*/{if (s->top!=-1){s->top--;return(s->data[s->top+1]);}elsereturn NULL;} void preorder(BiTreeNode *t)/*非递归实现二叉树的前序遍历*/{seqstack s;s.top=-1;while ((t) || (s.top!=-1))/*当前处理的子树不为空或栈不为空则循环*/{while (t){printf("%c ",t->data);s.top++;s.data[s.top]=t;t=t->leftchild;}if (s.top>-1){t=pop(&s);t=t->rightchild;}}}void main(){BiTreeNode *t;rf = fopen("input.txt", "r") ;createbintree(&t);printf("非递归前续遍历的例子:");preorder(t);printf("\n");}

Answer 1

既然都能写遍历的程序，你只要设置一个全局的变量count，在遍历的时候遇到叶子节点加1就成啊，至于怎么判断叶子结点就是判断他的左右子节点是否都为NULL就可以了

Answer 2

int LeafCountResc(BiTreeNode *tree)
{ //递归实现二叉树的遍历统计叶子数
BiTreeNode *t = tree;
int total = 0;

if(!t) return 0;

//如果已经是叶子，则返回1
//作为调试，打印叶子值
if(!t->leftchild && !t->rightchild )
{printf("%c ", t->data); return 1;}

//否则分别统计左子树和右子树的叶子数量

total += LeafCount(t->leftchild);
total += LeafCount(t->rightchild);
return total;
}

void LeafCountLoop(BiTreeNode *t)
/*非递归实现二叉树的前序遍历, 统计叶子数*/
{
int n = 0;
seqstack s;
s.top=-1;
while ((t) || (s.top!=-1))
/*当前处理的子树不为空或栈不为空则循环*/
{
while (t)
{
printf("%c",t->data);
if(t->rightchild)
{
s.top++;
s.data[s.top]=t;
}
//左右子树都为空则计数
else if(!t->leftchild){n++; printf("_");}

t=t->leftchild;
}
if (s.top>-1)
{
t=pop(&s);
t=t->rightchild;
}
}

printf("\nLeaf count=%d\n",n);
}