1. 在文件test.cpp中已經(jīng)給出的創(chuàng)建一個(gè)二叉樹的算法的基礎(chǔ)上，分別設(shè)計(jì)遞歸和非遞歸的算法統(tǒng)計(jì)該二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)。test.cpp 的內(nèi)容如下：#include <stdio.h>#include <malloc.h>typedef char datatype; /*結(jié)點(diǎn)屬性值的類型*/typedef struct node{ /*二叉樹結(jié)點(diǎn)的類型*/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) //創(chuàng)建二叉樹{char ch;if ((ch=fgetc(rf))==' '){*t=NULL;}else{*t=(BiTreeNode *)malloc(sizeof(BiTreeNode ));/*生成二叉樹的根結(jié)點(diǎn)*/(*t)->data=ch;createbintree(&(*t)->leftchild);/*遞歸實(shí)現(xiàn)左子樹的建立*/createbintree(&(*t)->rightchild);/*遞歸實(shí)現(xiàn)右子樹的建立*/}} void push(seqstack *s,BiTreeNode *t)/*進(jìn)棧*/{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)/*非遞歸實(shí)現(xiàn)二叉樹的前序遍歷*/{seqstack s;s.top=-1;while ((t) || (s.top!=-1))/*當(dāng)前處理的子樹不為空或棧不為空則循環(huán)*/{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("非遞歸前續(xù)遍歷的例子:");preorder(t);printf("\n");}
2 回答
元芳怎么了
TA貢獻(xiàn)1798條經(jīng)驗(yàn) 獲得超7個(gè)贊
既然都能寫遍歷的程序，你只要設(shè)置一個(gè)全局的變量count，在遍歷的時(shí)候遇到葉子節(jié)點(diǎn)加1就成啊，至于怎么判斷葉子結(jié)點(diǎn)就是判斷他的左右子節(jié)點(diǎn)是否都為NULL就可以了
喵喔喔
TA貢獻(xiàn)1735條經(jīng)驗(yàn) 獲得超5個(gè)贊
int LeafCountResc(BiTreeNode *tree)
{ //遞歸實(shí)現(xiàn)二叉樹的遍歷統(tǒng)計(jì)葉子數(shù)
BiTreeNode *t = tree;
int total = 0;
if(!t) return 0;
//如果已經(jīng)是葉子，則返回1
//作為調(diào)試，打印葉子值
if(!t->leftchild && !t->rightchild )
{printf("%c ", t->data); return 1;}
//否則分別統(tǒng)計(jì)左子樹和右子樹的葉子數(shù)量
total += LeafCount(t->leftchild);
total += LeafCount(t->rightchild);
return total;
}
void LeafCountLoop(BiTreeNode *t)
/*非遞歸實(shí)現(xiàn)二叉樹的前序遍歷, 統(tǒng)計(jì)葉子數(shù)*/
{
int n = 0;
seqstack s;
s.top=-1;
while ((t) || (s.top!=-1))
/*當(dāng)前處理的子樹不為空或棧不為空則循環(huán)*/
{
while (t)
{
printf("%c",t->data);
if(t->rightchild)
{
s.top++;
s.data[s.top]=t;
}
//左右子樹都為空則計(jì)數(shù)
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);
}
添加回答
舉報(bào)
0/150
提交
取消