求二叉树中叶结点个数的函数

求二叉树中叶结点个数的函数

//计算二叉树中叶子结点的个数
int LeafCount (BiTree T)
{ int m,n;
if ( !T ) return 0;
if (!T->lchild&& !T->rchild)
return 1;
else{
m=LeafCount( T->lchild);
n=LeafCount( T->rchild);
return (m+n);
} // if
return OK;
} //----------

template
int BiTree::CountLeaf(BiNode *root,int &count)
{
if(root!=NULL)
{
if(root->lchild==NULL&&root->rchild==NULL)
count++;
CountLeaf(root->lchild,count);
CountLeaf(root->rchild,count);
}
return count;
}

#include
#include
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
}
BiTNode,*BiTree;//树的数据结构
typedef struct SqStack
{
BiTNode *base;
BiTNode *top;
int stacksize;
}
SqStack;//栈的数据结构
void InitStack(SqStack *S)
{
S->base=(BiTNode*)malloc(STACK_INIT_SIZE*sizeof(BiTNode));
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
}//创建栈
void Push(SqStack *S,BiTNode e)
{
if(S->top-S->base>=S->stacksize)
{
S->base=(BiTNode*)realloc(S->base,
(S->stacksize+STACKINCREMENT)*sizeof(BiTNode));
S->top=S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
*(S->top)=e;
S->top++;
}//进栈操作
BiTNode Pop(SqStack *S)
{
S->top --;
return *S->top;
}//出栈操作
int StackEmpty(SqStack *S)
{
if(S->top == S->base )
return 1;
else
return 0;
}//判断栈是否为空
BiTree CreateBiTree()//创建树
{
char p;BiTree T;
scanf("%c",&p);
if(p==' ')
T=NULL;
else
{
T=(BiTNode *)malloc(sizeof(BiTNode));
T->data=p;
T->lchild=CreateBiTree();
T->rchild=CreateBiTree();
}
return (T);
}
int PreOrder(BiTree T)//先序求叶子节点
{
SqStack S;
int sum=0; //记录叶子结点个数
BiTree p=T;
InitStack(&S);
if(p)
Push(&S,*p);
while(!StackEmpty(&S))
{
p=(BiTNode *)malloc(sizeof(BiTNode));
*p=Pop(&S);
if(!(p->lchild) && !(p->rchild))
sum++;
if(p->rchild)
Push(&S,*p->rchild);
if(p->lchild)
Push(&S,*p->lchild);
}
return sum;
}
void main()
{
BiTree T;
printf("请创建树");
T=CreateBiTree();
printf("叶子节点数为：%d",PreOrder(T));

}

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息