二叉樹遞歸遍歷

1、 題目：假設(shè)二叉樹采用二叉鏈表結(jié)構(gòu)。設(shè)計(jì)并實(shí)現(xiàn)如下算法：先序遞歸建樹，中序非遞歸遍歷該樹，輸出各個(gè)結(jié)點(diǎn)的值，并求該樹中單分支結(jié)點(diǎn)的個(gè)數(shù)。一、需求分析用戶可以根據(jù)自己的需求分別輸入任意的一個(gè)二叉樹，并且能夠?qū)崿F(xiàn)中序非遞歸遍歷該樹輸出各個(gè)結(jié)點(diǎn)的數(shù)值。通過已有的二叉樹能夠求出該樹的單分支結(jié)點(diǎn)的個(gè)數(shù)。程序執(zhí)行的命令包括：(1)構(gòu)造二叉樹T(2)遍歷二叉樹(3)求二叉樹單分支結(jié)點(diǎn)的個(gè)數(shù)(4)求二叉樹的總結(jié)點(diǎn)數(shù)二、概要設(shè)計(jì)D為實(shí)現(xiàn)上述算法，需要鏈表的抽象數(shù)據(jù)類型：ADTBinarytree數(shù)據(jù)對象：D是具有相同特性的數(shù)據(jù)元素的集合數(shù)據(jù)關(guān)系R：若D為空集，則R為空集，稱binarytree為空二叉樹；若D不

2、為空集，則RDH,H是如下二元關(guān)系；(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root,它在關(guān)系H下無前驅(qū)；(2)若DDroot不為空，則存在DDrootUD1,Dr,且DIDDrDOO；(3)若D1不為空，則D1中存在唯一的元素x1,DH,且存在D1上的關(guān)系H1是H的子集；若Dr不為空集，則Dr00000000Xr,root,XrUH,且存在Dr上的關(guān)系Xr,H1,Hr;(4)(D1,H1)是一顆符合本定義的二叉樹，HrDH的子集；H=base=(structnode*)malloc(MAX*sizeof(node);if(!s-base)exit(0);s-top=s-base;s-size=

3、MAX;returns;/*判斷棧是否為空棧*/intstackempty(stack*s)if(s-top=s-base)return1;elsereturn0;/*入棧*/stack*push(stack*s,structbitnode*t)if(s-top-s-base=s-size)s-base=(structnode*)realloc(s-base,(s-size+10)*sizeof(node);if(!s-base)exit(0);s-top=s-base+s-size;s-size+=10;(*s-top).p=t;s-top+;returns;/*出棧*/structbitn

4、ode*pop(stack*s)if(s-top=s-base)printf(這是一個(gè)空棧n);return0;elses-top-;return(*s-top).p);/*取棧頂?shù)脑?/structbitnode*getpop(stack*s)if(s-top=s-base)printf(這是一個(gè)的空棧！n)；returnNULL;elsereturn(*(s-top-1).p;/*先序遞歸構(gòu)建二叉樹*/structbitnode*creatbitree(structbitnode*r)chara;scanf(%c,&a);if(a=)returnr=NULL;elser=(structb

5、itnode*)malloc(sizeof(bitnode);r-data=a;r-lchild=creatbitree(r-lchild);r-rchild=creatbitree(r-rchild);returnr;/*中序非遞歸遍歷二叉樹*/voidinorder(structbitnode*T)structbitnode*p,*q;p=T;s=initstack();if(p)while(p)push(s,p);p=p-lchild;while(!stackempty(s)p=pop(s);visit(p-data);if(p-rchild!=NULL)q=p-rchild;while

6、(q)push(s,q);q=q-lchild;/*求二叉樹的結(jié)點(diǎn)總數(shù)*/intcounter(structbitnode*T)intnum1,num2,num;if(T=NULL)return0;elsenum1=counter(T-lchild);num2=counter(T-rchild);num=num1+num2+1;returnnum;/*求二叉樹的單分支的結(jié)點(diǎn)數(shù)*/intonecount(structbitnode*T)ints1,s2;if(T=NULL)return(0);elses1=onecount(T-lchild);s2=onecount(T-rchild);if(T

7、-lchild!=NULL&T-rchild=NULL)|(T-rchild!=NULL&T-lchild=NULL)return(s1+s2+1);elsereturn(s1+s2);主函數(shù)和其他函數(shù)的偽碼算法main()intsum;printf(xianxushurubitree:n);TOC o 1-5 h zT=creatbitree(T);/*創(chuàng)建二叉樹*/a=counter(T);/*求結(jié)點(diǎn)總數(shù)*/printf(na=%dn,a);printf(nxianxubianlibitree:n);inorder(T);/*中序遍歷二叉樹*/sum=onecount(T);/*求單分支的

8、結(jié)點(diǎn)數(shù)*/printf(nnthebitreedanfenzhijiedianshu:nSUM=%dn,sum);getch();/*訪問元素*/voidvisit(charch)if(i!=(a-1)printf(%c-,ch);i+;elseprintf(%c,ch);printf(n);4函數(shù)調(diào)用關(guān)系maincreatbitreecounterinorderonecount四、調(diào)試分析叮步完成編程的工作時(shí)，*initstackpushpopvisit在輸入二叉樹的發(fā)現(xiàn)只能輸入一個(gè)字符，而且程序不再進(jìn)行，最后是自己的不小心將語句chara;scanf(c,&a);中的c寫為dU致的。ret

9、urnD在編寫元素入棧和出棧的時(shí)候，程序報(bào)如下的錯(cuò)誤：語法有錯(cuò)誤。提示語句(*s-top).p);有錯(cuò)，經(jīng)過檢查原來是定義的時(shí)候的類型使用錯(cuò)了。3.在編譯的時(shí)候還有警告的提示：exp6.c50：指針轉(zhuǎn)換后指向其它類型在push函數(shù)中”,在檢查該語句的發(fā)現(xiàn)是s-base=(structnode*)realloc(s-base,(s-size+10)*sizeof(node);中的node寫成了二叉樹的類型bitnode了，因此出現(xiàn)上述的提示。算法的時(shí)空分析各操作的算法時(shí)間復(fù)雜度比較合理initstack,stackempty,push,pop,getpop,visit為0(1)；creatbit

10、ree,inorder,counter,onecount為O(n),注：n為二叉樹的總結(jié)點(diǎn)數(shù)。本次實(shí)驗(yàn)采用數(shù)據(jù)抽象的程序設(shè)計(jì)方法,將程序化為三層次結(jié)構(gòu),設(shè)計(jì)時(shí)思路清晰,使調(diào)試也較順利,各模塊有較好的可重用性。五、用戶手冊D本程序的運(yùn)行環(huán)境為windowsxp操作系統(tǒng)，并且在TC2.0中運(yùn)行，執(zhí)行文件為Exp6.c；D.在輸入二叉樹的時(shí)候空格表示為空,輸入注意空格的個(gè)數(shù)；3.進(jìn)入演示程序后,完成編譯,再點(diǎn)擊超級(jí)工具集里的中文D0S環(huán)境運(yùn)行選項(xiàng),進(jìn)入D0S環(huán)境中,用戶根據(jù)需求鍵入相應(yīng)的數(shù)據(jù),可以看到相應(yīng)的結(jié)果。六、測試結(jié)果所以在wintc中運(yùn)行得到的結(jié)果如下圖所示：匚:DOCUME1.ADMINE

11、11桌面mimi.EHexianxushutrubitree=ABDGJEHHCFIa=11ahonsixubian11bitree=thebitreedanfenzhijiediansliu:SUM=&我輸入的二叉樹是ABDGJEHKCFIA運(yùn)行的結(jié)果是：結(jié)點(diǎn)的總數(shù)是11遍歷的結(jié)果GJDBEKHAFICBC單分支的結(jié)點(diǎn)數(shù)是6DEF七、附錄：源程序GHI#includeJK#include#defineNULL0#defineMAX100/*定義二叉樹*/typedefstructbitnodechardata;structbitnode*lchild,*rchild;bitnode;/*定義

12、棧元素的類型*/typedefstructnodestructbitnode*p;node;/*定義棧*/typedefstructstacknode*base;node*top;intsize;stack;TOC o 1-5 h z/*全局變量*/structbitnode*T;stack*s;inti=0,a;/*a為二叉樹的結(jié)點(diǎn)總數(shù)；i為訪問結(jié)點(diǎn)時(shí)的計(jì)數(shù)*/*構(gòu)建空棧*/stack*initstack()s-base=(structnode*)malloc(MAX*sizeof(node);if(!s-base)exit(0);s-top=s-base;s-size=MAX;return

13、s;/*判斷棧是否為空棧*/intstackempty(stack*s)if(s-top=s-base)return1;elsereturn0;/*入棧*/stack*push(stack*s,structbitnode*t)if(s-top-s-base=s-size)s-base=(structnode*)realloc(s-base,(s-size+10)*sizeof(node);if(!s-base)exit(0);s-top=s-base+s-size;s-size+=10;(*s-top).p=t;s-top+;returns;/*出棧*/structbitnode*pop(st

14、ack*s)if(s-top=s-base)printf(這是一個(gè)空棧n);return0;elses-top-;return(*s-top).p);/*取棧頂?shù)脑?/structbitnode*getpop(stack*s)if(s-top=s-base)printf(這是一個(gè)的空棧！n)；returnNULL;elsereturn(*(s-top-1).p;/*先序遞歸構(gòu)建二叉樹*/structbitnode*creatbitree(structbitnode*r)chara;scanf(%c,&a);if(a=)returnr=NULL;elser=(structbitnode*)ma

15、lloc(sizeof(bitnode);r-data=a;r-lchild=creatbitree(r-lchild);r-rchild=creatbitree(r-rchild);returnr;/*訪問元素*/voidvisit(charch)if(i!=(a-1)printf(%c-,ch);i+;elseprintf(%c,ch);printf(n);/*中序非遞歸遍歷二叉樹*/voidinorder(structbitnode*T)structbitnode*p,*q;p=T;s=initstack();if(p)while(p)push(s,p);p=p-lchild;while

16、(!stackempty(s)p=pop(s);visit(p-data);if(p-rchild!=NULL)q=p-rchild;while(q)push(s,q);q=q-lchild;/*求二叉樹的結(jié)點(diǎn)總數(shù)*/intcounter(structbitnode*T)intnum1,num2,num;if(T=NULL)return0;elsenum1=counter(T-lchild);num2=counter(T-rchild);num=num1+num2+1;returnnum;/*求二叉樹的單分支的結(jié)點(diǎn)數(shù)*/intonecount(structbitnode*T)ints1,s2;if(T=NULL)return(0);elses1=onecount(T-lchild);s2=onecount(T-rchild);if(T-lchild!=NULL&T-rchild=NULL)|(T-rchild!=NULL&T-lchild=NULL)return(s1+s2+1);elsereturn(s1+s2);/*主函數(shù)*