叉樹(shù)的基本操作完整版,包含叉樹(shù)的所有操作,凡是你想要的都在里面數(shù)據(jù)結(jié)構(gòu)版

1、#include"stdio.h"#include"stdlib.h"#include"string.h"#include"math.h"typedefcharTElemType;定義結(jié)點(diǎn)數(shù)據(jù)為字符型typedefintStatus;定義函數(shù)類(lèi)型為int型#defineERROR0#defineOK1data;結(jié)點(diǎn)數(shù)值*lchild;/左孩子指針*rchild;II右孩子指針*next;下一結(jié)點(diǎn)指針typedefstructBiTNode/te義結(jié)構(gòu)體TElemTypestructBiTNodestructBiTN

2、odestructBiTNodeBiTNode,*BiTree;StatusNumJudge(charch20)II限制輸入數(shù)據(jù)必須為大于零的整形charch120;intnum;while(1)scanf("%s",ch);num=atoi(ch);將字符串轉(zhuǎn)換為整型itoa(num,ch1,10);將整型轉(zhuǎn)換為字符串型if(strcmp(ch,ch1)=0&&num>0)break;elseprintf("請(qǐng)輸入一個(gè)大于零的整數(shù)：");returnnum;IINumJudgeStatusInitBiTree(BiTree&

3、;T)若申請(qǐng)空間失敗則退出II構(gòu)造空二叉樹(shù)Tif(!(T=(BiTree)malloc(sizeof(BiTNode)exit(ERROR);IIT->next=NULL;printf("nt空二叉樹(shù)構(gòu)建成功!nn");returnOK;IIInitBiTreeStatusDestroyTree(BiTree&T,BiTreet)II銷(xiāo)毀二叉樹(shù)if(T)free(T);T=NULL;printf("t二叉樹(shù)銷(xiāo)毀成功!n");if(t)(DestroyTree(T,t->lchild);DestroyTree(T,t->rchil

4、d);free(t);returnOK;/DestroyTreeStatusClearBiTree(BiTree&T,intsum,int&i)(/清空二叉樹(shù)if(T)(ClearBiTree(T->lchild,sum,i);ClearBiTree(T->rchild,sum,i);free(T);i+;if(i=sum)printf("t二叉樹(shù)清空成功！n");T=NULL;returnOK;/ClearBiTreeStatusCreateBiTree(BiTree&T,inti,intj,TElemTypech)/按先序次序輸入二叉

5、樹(shù)中結(jié)點(diǎn)的值(一個(gè)字符)，空格字符表示該結(jié)點(diǎn)為空/構(gòu)造二叉鏈表示的二叉樹(shù)TTElemTypechi;intk;charstr20;if(i=0)printf("n按先序順序建立二叉樹(shù)：請(qǐng)按提示輸入相應(yīng)的數(shù)據(jù)(一個(gè)字符)，若提示結(jié)點(diǎn)數(shù)值為空，n請(qǐng)輸入空格nn");printf("%5s請(qǐng)輸入樹(shù)根：","");if(i!=0&&i>=j)printf("%5s請(qǐng)輸入%c的左孩子：","",ch);if(j!=0&&j>i)printf("%5s請(qǐng)

6、輸入%c的右孩子：","",ch);while(1)/限制輸入數(shù)據(jù)必須為字符型，否則重新輸入fflush(stdin);for(k=0;k<20;k+)strk=getchar();if(strk='n')break;if(k=0)printf("%5s請(qǐng)輸入一個(gè)字符后再按Enter鍵：","");if(k=1)break;if(k>1)printf("%5s您只能輸入一個(gè)字符：","");ch1=str0;/獲取輸入的準(zhǔn)確字符型數(shù)據(jù)if(ch1='

7、')T=NULL;returnERROR;/輸入空格則為根結(jié)點(diǎn)為空if(ch1!='')if(!(T=(BiTree)malloc(sizeof(BiTNode)exit(ERROR);T->data=ch1;生成根結(jié)點(diǎn)ch=T->data;i+;CreateBiTree(T->lchild,i,j,ch);構(gòu)造左子樹(shù)j=i;j+;CreateBiTree(T->rchild,i,j,ch);構(gòu)造右子樹(shù)i=0;j=0;returnOK;/CreateBitreeStatusTreeDepth(BiTreeT,intl,int&h)若二叉樹(shù)

8、存在，返回其深度if(T)l=l+1;if(l>h)h=l;TreeDepth(T->lchild,l,h);TreeDepth(T->rchild,l,h);returnh;/TreeDepthStatusGetRootElem(BiTreeT)/獲取根結(jié)點(diǎn)值printf("該二叉樹(shù)的根結(jié)點(diǎn)值為：%cnn",T->data);returnOK;/GetRootElemStatusSaveElem(BiTreeT,BiTree*Q,inti)根據(jù)完全二叉樹(shù)中，若本節(jié)點(diǎn)位置序號(hào)為i,則其左孩子結(jié)點(diǎn)為2i,右孩子為2i+1的方法保存二叉樹(shù)的有效結(jié)點(diǎn)至指針

9、數(shù)組Q特定的位置if(T)Qi=T;SaveElem(T->lchild,Q,2*i);SaveElem(T->rchild,Q,2*i+1);returnOK;/SaveElemStatusLev_Traverse(BiTreeT,inth)按層次從上到下，每層從左到右的順序顯示樹(shù)狀二叉樹(shù)if(T=NULL)printf("ntt二叉樹(shù)目前為空樹(shù)nn");returnERROR;BiTree*Q;if(!(Q=(BiTree*)malloc(int(pow(2,h)+1)*sizeof(BiTNode)exit(ERROR);inti,j,n=1,k=h;fo

10、r(i=1;i<=int(pow(2,h)+1);i+)Qi=NULL;，從左到右的順序SaveElem(T,Q,n);將目前有效結(jié)點(diǎn)按照滿(mǎn)二叉樹(shù)的序號(hào)存儲(chǔ)printf("提示:規(guī)定下圖中的有效結(jié)點(diǎn)的位置序號(hào)從1開(kāi)始按從上到下依次遞增n");for(i=1;i<=(pow(2,h)+1);i+)/樹(shù)形顯示二叉樹(shù)if(int(pow(2,h)%i=0)printf("n");printf("tt");for(j=0;j<pow(2,k-1)-1;j+)printf("");k-;if(Qi)prin

11、tf("%c”,Qi->data);if(!Qi)printf("");for(j=0;j<pow(2,k+1)-1;j+)printf("");printf("nn");i=0;j=0;returnOK;/Lev_TraverseStatusFirstPrint(BiTreeT,inti)按先序次序(遞歸)訪問(wèn)二叉樹(shù)if(i=0)printf("n先序(遞歸)遍歷結(jié)果如下:n");if(T)i+;printf("%-5c”,T->data);/訪問(wèn)TFirstPrint(T-

12、>lchild,i);遞歸遍歷左子樹(shù)FirstPrint(T->rchild,i);遞歸遍歷右子樹(shù)i=0;returnOK;/FirstPrintBiTreeStatusMiddlePrint(BiTreeT,inti)按中序次序(遞歸)訪問(wèn)二叉樹(shù)if(i=0)printf("n中序(遞歸)遍歷結(jié)果如下:n");if(T)i+;MiddlePrint(T->lchild,i);遞歸遍歷左子樹(shù)printf("%-5c”,T->data);/訪問(wèn)TMiddlePrint(T->rchild,i);遞歸遍歷右子樹(shù)i=0;returnOK;/

13、MiddlePrintStatusLastPrint(BiTreeT,inti)/按后序次序(遞歸)訪問(wèn)二叉樹(shù)if(i=0)printf("n后序(遞歸)遍歷結(jié)果如下：n");if(T)i+;LastPrint(T->lchild,i);遞歸遍歷左子樹(shù)LastPrint(T->rchild,i);遞歸遍歷右子樹(shù)printf("%-5c",T->data);/訪問(wèn)Ti=0;returnOK;/LastPrintStatusPreOrderTraverse(BiTreeT)/按先序(非遞歸)遍歷二叉樹(shù)TBiTreep,S,q;intflag

14、=0;if(!(S=(BiTree)malloc(sizeof(BiTNode)exit(ERROR);S->next=NULL;建立空棧Sp=T;printf("n先序(非遞歸)遍歷結(jié)果如下:n");while(1)while(1)遍歷存儲(chǔ)并訪問(wèn)左子樹(shù)直到根結(jié)點(diǎn)左孩子不存在printf("%-5c",p->data);q=S->next;S->next=p;p->next=q;當(dāng)前結(jié)點(diǎn)進(jìn)棧if(p->lchild)p=p->lchild;elsebreak;while(1)棧頂指針出棧，如果當(dāng)前棧頂指針的右孩子

15、存在則跳出循環(huán)p=S->next;S->next=p->next;if(!S->next&&!p->rchild)flag=1;break;/如果?？詹⑶耶?dāng)前結(jié)點(diǎn)右孩子不存在則遍歷結(jié)束if(p->rchild)p=p->rchild;break;if(flag=1)break;printf("nn");returnOK;/PreOrderTraverseStatusInOrderTraverse(BiTreeT)/中序遍歷(非遞歸)二叉樹(shù)TBiTreep,S,q;if(!(S=(BiTree)malloc(sizeo

16、f(BiTNode)exit(ERROR);S->next=NULL;建立空棧Sp=T;printf("n中序(非遞歸)遍歷結(jié)果如下：n");while(p|S->next)if(p)q=S->next;S->next=p;p->next=q;p=p->lchild;左孩子進(jìn)棧elsep=S->next;S->next=p->next;if(p)printf("%-5c”,p->data);/輸出棧中元素elsereturnERROR;p=p->rchild;printf("nn"

17、;);returnOK;/InOrderTraverseStatusPostOrderTraverse(BiTreeT)后序遍歷(非遞歸)二叉樹(shù)TBiTreep,S,q;if(!(S=(BiTree)malloc(sizeof(BiTNode)exit(ERROR);S->next=NULL;建立空棧Sp=T;printf("n后序(非遞歸)遍歷結(jié)果如下:n");while(1)while(1)/遍歷左子樹(shù)，若當(dāng)前結(jié)點(diǎn)左右孩子都不存在則跳出q=S->next;S->next=p;p->next=q;/當(dāng)前結(jié)點(diǎn)進(jìn)棧if(p->lchild)p=p

18、->lchild;elseif(p->rchild)p=p->rchild;elsebreak;while(S->next)p=S->next;S->next=p->next;/棧頂指針出棧并訪問(wèn)printf("%-5c",p->data);if(!S->next)break;若棧空則跳出if(p=S->next->rchild)p=S->next;/若當(dāng)前結(jié)點(diǎn)為棧頂指針的右孩子，則繼續(xù)出棧else(if(S->next->rchild)(/棧頂指針右孩存在，指針移至棧頂指針的右孩子后跳出循

19、環(huán)p=S->next->rchild;break;if(!S->next)break;/若?？談t跳出循環(huán)printf("nn");returnOK;/PostOrderTraverseStatusGetElemSum(BiTreeT)(/計(jì)算二叉樹(shù)中總結(jié)點(diǎn)的個(gè)數(shù)BiTreep,*q;intl=0,h=0;if(!(q=(BiTree*)malloc(int(pow(2,TreeDepth(T,l,h)+1)*sizeof(BiTNode)exit(ERROR);inthead=1,tail=2;q1=T;while(head<tail)(p=qhea

20、d+;if(p->lchild)qtail+=p->lchild;if(p->rchild)qtail+=p->rchild;returnhead-1;/GetElemSumStatusLevelOrderPrint(BiTreeT)(/二叉樹(shù)T存在,層序遍歷二叉樹(shù)將二叉樹(shù)中的結(jié)點(diǎn)按從上到下，從左到右的順序存至指針數(shù)組q,然后按次序輸出BiTreep,*q;if(!(q=(BiTree*)malloc(GetElemSum(T)*sizeof(BiTNode)exit(ERROR);inthead=1,tail=2;q1=T;printf("n層序(非遞歸)遍

21、歷結(jié)果如下：n");while(head<tail)(p=qhead+;printf("%-5c",p->data);if(p->lchild)qtail+=p->lchild;if(p->rchild)qtail+=p->rchild;printf("nn");returnOK;/LevelOrderPrintStatusGetElemNum(BiTreeT,TElemTypee)(查找元素e在二叉樹(shù)T中的個(gè)數(shù)及位置intj,i=0,num=0,*a;BiTreep,*q;if(!(q=(BiTree*)m

22、alloc(GetElemSum(T)*sizeof(BiTNode)exit(ERROR);if(!(a=(int*)malloc(GetElemSum(T)*sizeof(int)exit(ERROR);inthead=1,tail=2;q1=T;while(head<tail)(p=qhead+;if(p->data=e)num+;ai=head-1;i+;if(p->lchild)qtail+=p->lchild;if(p->rchild)qtail+=p->rchild;printf("n元素%c在二叉樹(shù)中的個(gè)數(shù)為：%dn",e

23、,num);printf("元素%c在二叉樹(shù)中的位置序號(hào)為:",e);for(j=0;j<i;j+)printf("%-4d”,aj);printf("n");returnnum;/GetElemNumStatusGetLeafNum(BiTreeT)/計(jì)算二叉樹(shù)T中葉子個(gè)數(shù)BiTreep,*q;if(!(q=(BiTree*)malloc(GetElemSum(T)*sizeof(BiTNode)exit(ERROR);intnum=0,head=1,tail=2;q1=T;while(head<tail)p=qhead+;if(

24、!p->lchild&&!p->rchild)num+;if(p->lchild)qtail+=p->lchild;if(p->rchild)qtail+=p->rchild;returnnum;/GetLeafNumStatusLBrother(BiTreeT,intsum)(/求第num個(gè)結(jié)點(diǎn)的左兄弟BiTreep,*q;if(!(q=(BiTree*)malloc(GetElemSum(T)*sizeof(BiTNode)exit(ERROR);inti,num,head=1,tail=2;charstr20;q1=T;printf(&

25、quot;請(qǐng)輸入要查找的位置序號(hào)：");num=NumJudge(str);if(num>sum)printf("您輸入的位置序號(hào)大于有效結(jié)點(diǎn)個(gè)數(shù)n");returnERROR;while(head<tail)(p=qhead+;if(num=tail-2)break;if(p->lchild)qtail+=p->lchild;if(p->rchild)qtail+=p->rchild;if(num=1)printf("位置%d的c沒(méi)有左兄弟n”,num,qnum->data);elsefor(i=1;i<

26、num;i+)if(qi->lchild=qnum|qi->rchild=qnum)break;if(qi->lchild=qnum)printf("位置%d的c沒(méi)有左兄弟n”,num,qnum->data);if(qi->rchild=qnum)printf("位置%d的%c的左兄弟為:%cn”,num,qnum->data,qi->lchild->data);returnOK;/LBrotherStatusRBrother(BiTreeT,intsum)/求第num個(gè)結(jié)點(diǎn)的右兄弟BiTreep,*q;if(!(q=(BiT

27、ree*)malloc(GetElemSum(T)*sizeof(BiTNode)exit(ERROR);inti,num,head=1,tail=2;charstr20;q1=T;printf("請(qǐng)輸入要查找的位置序號(hào)：");num=NumJudge(str);if(num>sum)printf("您輸入的位置序號(hào)大于有效結(jié)點(diǎn)個(gè)數(shù)n");returnERROR;while(head<tail)p=qhead+;if(num=tail-2)break;if(p->lchild)qtail+=p->lchild;if(p->r

28、child)qtail+=p->rchild;if(num=1)printf("位置%d的c沒(méi)有右兄弟n”,num,qnum->data);else(for(i=1;i<num;i+)(if(qi->lchild=qnum|qi->rchild=qnum)break;if(!qi->rchild|qi->rchild=qnum)printf("位置%d的%c沒(méi)有右兄弟n",num,qnum->data);if(qi->rchild&&qi->lchild=qnum)printf("

29、;位置%d的%c的右兄弟為：%cn",num,qnum->data,qi->rchild->data);returnOK;/RBrotherStatusLchild(BiTreeT,intsum)(/求第num個(gè)結(jié)點(diǎn)的左孩子BiTreep,*q;if(!(q=(BiTree*)malloc(GetElemSum(T)*sizeof(BiTNode)exit(ERROR);intnum,head=1,tail=2;charstr20;q1=T;printf(-請(qǐng)輸入要查找的位置序號(hào)：");num=NumJudge(str);if(num>sum)(pr

30、intf("您輸入的位置序號(hào)大于有效結(jié)點(diǎn)個(gè)數(shù)n");returnERROR;while(head<tail)(p=qhead+;if(num=tail-2)break;if(p->lchild)qtail+=p->lchild;if(p->rchild)qtail+=p->rchild;if(qnum->lchild)printf("位置%d的%c的左孩子為:%cn",num,qnum->data,qnum->lchild->data);else(printf("位置%d的%c的左孩子不存在

31、n",num,qnum->data);returnOK;/LchildStatusRchild(BiTreeT,intsum)(/求第num個(gè)結(jié)點(diǎn)的右孩子BiTreep,*q;if(!(q=(BiTree*)malloc(GetElemSum(T)*sizeof(BiTNode)exit(ERROR);intnum,head=1,tail=2;charstr20;q1=T;printf(-請(qǐng)輸入要查找的位置序號(hào)：");num=NumJudge(str);if(num>sum)(printf("您輸入的位置序號(hào)大于有效結(jié)點(diǎn)個(gè)數(shù)n");retur

32、nERROR;while(head<tail)(p=qhead+;if(num=tail-2)break;if(p->lchild)qtail+=p->lchild;if(p->rchild)qtail+=p->rchild;if(qnum->rchild)printf("位置%d的%c的右孩子為:%cn”,num,qnum->data,qnum->rchild->data);else(printf("位置%d的%c的右孩子不存在n”,num,qnum->data);returnOK;/RchildStatusPa

33、rtents(BiTreeT,intsum)(/求第num個(gè)結(jié)點(diǎn)的雙親BiTreep,*q;if(!(q=(BiTree*)malloc(GetElemSum(T)*sizeof(BiTNode)exit(ERROR);inti,num,head=1,tail=2;charstr20;q1=T;printf(-請(qǐng)輸入要查找的位置序號(hào)：");num=NumJudge(str);if(num>sum)(printf("您輸入的位置序號(hào)大于有效結(jié)點(diǎn)個(gè)數(shù)n");returnERROR;while(head<tail)(p=qhead+;if(num=tail-

34、2)break;if(p->lchild)qtail+=p->lchild;if(p->rchild)qtail+=p->rchild;if(num=1)printf("位置%d的c沒(méi)有雙親n”,num,qnum->data);else(for(i=1;i<num;i+)(if(qi->lchild=qnum|qi->rchild=qnum)break;printf("位置%d的%c的雙親為：%cn",num,qnum->data,qi->data);returnOK;/PartentsStatusTre

35、eDelete(BiTree&T,intsum)(刪除第num個(gè)結(jié)點(diǎn)BiTreep,p1,*q;if(!(q=(BiTree*)malloc(GetElemSum(T)*sizeof(BiTNode)exit(ERROR);inti,num,head=1,tail=2,a=0,b=0;charstr20;q1=T;printf("請(qǐng)輸入要?jiǎng)h除結(jié)點(diǎn)的位置序號(hào)：");num=NumJudge(str);if(num>sum)printf("n您輸入的位置序號(hào)大于有效結(jié)點(diǎn)個(gè)數(shù)nn");returnERROR;if(num=1)printf(&qu

36、ot;t對(duì)不起，您不能刪除根結(jié)點(diǎn)，若想刪除根結(jié)點(diǎn)，請(qǐng)選擇銷(xiāo)毀樹(shù)nn");returnERROR;while(head<tail)p=qhead+;if(num=tail-2)break;if(p->lchild)qtail+=p->lchild;if(p->rchild)qtail+=p->rchild;for(i=1;i<num;i+)if(qi->lchild=qnum|qi->rchild=qnum)break;printf("n您刪除了如下子樹(shù):nn");Lev_Traverse(qnum,TreeDepth

37、(qnum,a,b);if(qi->lchild=qnum)qi->lchild=NULL;if(qi->rchild=qnum)qi->rchild=NULL;p1=NULL;DestroyTree(p1,qnum);printf("n刪除結(jié)點(diǎn)成功n");returnOK;/TreeDeleteStatusTreeInsert(BiTree&T,intsum)/在第num個(gè)生成子樹(shù)BiTreep,p1,*q;if(!(q=(BiTree*)malloc(GetElemSum(T)*sizeof(BiTNode)exit(ERROR);int

38、num,head=1,tail=2,a=0,b=0;charch='',str20;q1=T;printf("請(qǐng)輸入要插入結(jié)點(diǎn)的位置序號(hào)：");num=NumJudge(str);if(num>sum)printf("n您輸入的位置序號(hào)大于有效結(jié)點(diǎn)個(gè)數(shù)nn");returnERROR;while(head<tail)p=qhead+;if(num=tail-2)break;if(p->lchild)qtail+=p->lchild;if(p->rchild)qtail+=p->rchild;if(qnu

39、m->lchild&&qnum->rchild)printf("您輸入的位置序號(hào)已有左子樹(shù)和右子樹(shù)，無(wú)法再此位置插入nn");returnERROR;if(qnum->lchild&&!qnum->rchild)printf("位置%d的c處只能生成右子樹(shù)，確定插入/退出(y/n):",num,qnum->data);while(1)scanf("%s",str);if(strcmp(str,"y")=0|strcmp(str,"n"

40、)=0)break;elseprintf("選擇錯(cuò)誤，請(qǐng)重新輸入：");if(strcmp(str,"y")=0)printf("請(qǐng)輸入插入子樹(shù)的彳息：n");CreateBiTree(p1,a,b,ch);if(p1)qnum->rchild=p1;if(strcmp(str,"n")=0)returnERROR;if(!qnum->lchild&&qnum->rchild)printf("位置%d的c處只能生成左子樹(shù)，確定插入/退出(y/n):",num,q

41、num->data);while(1)scanf("%s",str);if(strcmp(str,"y")=0|strcmp(str,"n")=0)break;elseprintf("選擇錯(cuò)誤，請(qǐng)重新輸入:");if(strcmp(str,"y")=0)printf("請(qǐng)輸入插入子樹(shù)的彳息：n");CreateBiTree(p1,a,b,ch);if(p1)qnum->lchild=p1;if(strcmp(str,"n")=0)returnE

42、RROR;if(!qnum->lchild&&!qnum->rchild)printf("請(qǐng)輸入插入子樹(shù)的彳息：n");CreateBiTree(p1,a,b,ch);printf("tt你想把新建的樹(shù)作為位置%d的c處的：n”,num,qnum->data);printf("tt1左子樹(shù)2右子樹(shù)n”);printf("ntt請(qǐng)輸入你的選擇：");while(1)scanf("%s",str);if(strcmp(str,"1")=0|strcmp(str,&q

43、uot;2")=0)break;elseprintf("選擇錯(cuò)誤，請(qǐng)重新輸入:");if(strcmp(str,"1")=0)if(p1)qnum->lchild=p1;if(strcmp(str,"2”)=0)if(p1)qnum->rchild=p1;printf("插入子樹(shù)成功n”);returnOK;/TreeInsertStatusModify(BiTreeT,intsum,int&n)修改二叉樹(shù)第num個(gè)結(jié)點(diǎn)的值BiTreep,*q;if(!(q=(BiTree*)malloc(GetElem

44、Sum(T)*sizeof(BiTNode)exit(ERROR);intk,num,head=1,tail=2;charstr20;q1=T;n=0;printf("請(qǐng)輸入要修改結(jié)點(diǎn)的位置序號(hào)：");num=NumJudge(str);if(num>sum)printf("n您輸入的位置序號(hào)大于有效結(jié)點(diǎn)個(gè)數(shù)nn");returnERROR;while(head<tail)p=qhead+;if(num=tail-2)break;if(p->lchild)qtail+=p->lchild;if(p->rchild)qtail

45、+=p->rchild;printf("%5s請(qǐng)輸入新的結(jié)點(diǎn)值：","");while(1)fflush(stdin);for(k=0;k<20;k+)strk=getchar();if(strk='n')break;if(k=0)printf("%5s請(qǐng)輸入一個(gè)字符后再按Enter鍵：","");if(k=1)break;if(k>1)printf("%5s您只能輸入一個(gè)字符：","");qnum->data=str0;printf(

46、"n修改成功n");n=1;returnOK;/ModifyintMainMenu()主菜單函數(shù)system("cls");intchoose;charstr20;printf("nttt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*“).printf("nttt計(jì)本102盧榮盼1018014052”);printf("nttt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*“).1 建立空樹(shù)n"）;2 構(gòu)造二叉樹(shù)n"）;3 顯示樹(shù)狀二叉樹(shù)n&

47、quot;）;4 遍歷二叉樹(shù)->>進(jìn)入子菜單n"）;5 查看二叉樹(shù)信息->>進(jìn)入子菜單n"）;6 對(duì)二叉樹(shù)進(jìn)行操作->>進(jìn)入子菜單n"）;0退出程序"）;*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*“）.printf("ntttprintf("ntttprintf("ntttprintf("ntttprintf("ntttprintf("ntttprintf("ntttprintf("nttt*=*;printf(

48、"nttt請(qǐng)輸入你的選擇：");while(1)scanf("%s",str);if(strcmp(str,"0")=0|strcmp(str,"1")=0|strcmp(str,"2")=0|strcmp(str,"3")=0|strcmp(str,"4")=0|strcmp(str,"5")=0|strcmp(str,"6")=0)choose=atoi(str);break;elseprintf("t

49、tt選擇錯(cuò)誤請(qǐng)重新輸入：");)if(choose=0)(printf("nnt謝謝使用本程序nn");returnchoose;/MainMenu()intMenu()/主菜單函數(shù)system("cls");intchoose;charstr20;printf("nttt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*“).printf("nttt請(qǐng)選擇對(duì)應(yīng)的選項(xiàng)按對(duì)應(yīng)的方式遍歷二叉樹(shù)");按先序（遞歸）遍歷二叉樹(shù)n"）;按中序（遞歸）遍歷二叉樹(shù)n"）;按后序（遞

50、歸）遍歷二叉樹(shù)n"）;按先序（非遞歸）遍歷二叉樹(shù)按中序（非遞歸）遍歷二叉樹(shù)按后序（非遞歸）遍歷二叉樹(shù)按層次（非遞歸）遍歷二叉樹(shù)返回主菜單"）;printf("nttt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*“).printf("ntttt1printf("ntttt2printf("ntttt3n");n");n");n");printf("ntttt4printf("ntttt5printf("ntttt6printf(&qu

51、ot;ntttt7printf("nttttOprintf("nttt*=*=printf("ttt請(qǐng)輸入你的選擇:");while(1)scanf("%s",str);if(strcmp(str,"0”)=0|strcmp(str,"1”)=0|strcmp(str,"2”)=0|strcmp(str,"3”)=0|strcmp(str,"4”)=0|strcmp(str,"5”)=0|strcmp(str,"6”)=0|strcmp(str,"7”)=

52、0)(choose=atoi(str);break;else(printf("ttt選擇錯(cuò)誤請(qǐng)重新輸入：");returnchoose;/Menu()intMenu1()(查看二叉樹(shù)信息菜單system("cls");intchoose;charstr20,str120;printf("nt*一*一*一*一*一*一*一*一*一*一*一*一*一*一*一*一*一*一*一*一*一*一*一*一*一*一*"-I;printf("nt請(qǐng)選擇對(duì)應(yīng)的選項(xiàng)查看當(dāng)前二叉樹(shù)的信息");printf("nt*一*一*一*一*一*

53、一*一*一*一*一*一*一*一*一*一*一*一*一*一*一*一*一*一*一*一*一*"-I;printf(-nt1返回根結(jié)點(diǎn)值printf("nt3二叉樹(shù)的總結(jié)點(diǎn)個(gè)數(shù)printf("nt5二叉樹(shù)中度為1的結(jié)點(diǎn)個(gè)數(shù)printf("nt7某一值的結(jié)點(diǎn)個(gè)數(shù)及位置printf("nt9二叉樹(shù)中某結(jié)點(diǎn)的右孩子printf("nt11二叉樹(shù)中某結(jié)點(diǎn)的右兄弟printf("nt0返回主菜單n");2二叉樹(shù)的深度n");4二叉樹(shù)中度為2的結(jié)點(diǎn)個(gè)數(shù)n");6二叉樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)n");8二叉樹(shù)中某結(jié)點(diǎn)的

54、左孩子n");10二叉樹(shù)中某結(jié)點(diǎn)的左兄弟n");12二叉樹(shù)中某結(jié)點(diǎn)的雙親n");printf("t*=*=一*一*一*一*n");printf("tt請(qǐng)輸入你的選擇:");while(1)(scanf("%s”,str);choose=atoi(str);itoa(choose,str1,10);if(choose>0&&choose<=12&&strcmp(str,str1)=0|strcmp(str,"0”)=0)break;else(printf(&quo

55、t;tt選擇錯(cuò)誤請(qǐng)重新輸入:");returnchoose;/Menu1()intMenu2()(主菜單函數(shù)system("cls");intchoose;charstr20;printf("nttt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*");");printf("nttt請(qǐng)選擇對(duì)應(yīng)的選項(xiàng)對(duì)二叉樹(shù)進(jìn)行操作printf("nttt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*");刪除某一結(jié)點(diǎn)n");對(duì)某一結(jié)點(diǎn)生成子樹(shù)n");修改某一結(jié)點(diǎn)值

56、n");清空二叉樹(shù)n");銷(xiāo)毀二叉樹(shù)n");返回主菜單");：*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*，printf("ntttt1printf("ntttt2printf("ntttt3printf("ntttt4printf("ntttt5printf("ntttt0printf("ntttprintf("nttt請(qǐng)輸入你的選擇：");while(1)(scanf("%s”,str);if(strcmp(str,"0

57、”)=0|strcmp(str,"1”)=0|strcmp(str,"2”)=0|strcmp(str,"3”)=0|strcmp(str,"4”)=0|strcmp(str,"5”)=0)choose=atoi(str);break;elseprintf("ttt選擇錯(cuò)誤請(qǐng)重新輸入:");returnchoose;/Menu2()voidmain()system("colore0");BiTreeT=NULL;intnum,l,h,choose,flag=0,i=0,j=0,n;TElemTypech;

58、while(choose=MainMenu()!=0)switch(choose)case1:if(flag=2)printf("您已清空了之前的二叉樹(shù)，目前為空樹(shù)，無(wú)須再建立空樹(shù)！nn");elseif(flag=0)InitBiTree(T);flag=1;elseprintf("您之前已經(jīng)建過(guò)空樹(shù)，若想重建，請(qǐng)先銷(xiāo)毀當(dāng)前的樹(shù)！nn");system("pause");break;case2:if(!T)printf("您還沒(méi)有建樹(shù)，請(qǐng)先建樹(shù)！nn");elseif(T->next)printf(&quo

59、t;二叉樹(shù)已存在，若想重建，請(qǐng)先清空當(dāng)前的二叉樹(shù)！nn");elsesystem("cls");CreateBiTree(T->next,i,j,ch);printf("nn二叉樹(shù)創(chuàng)建完成！nn");system("pause");break;case3:if(!T)printf("您還沒(méi)有建樹(shù)，請(qǐng)先建樹(shù)！nn");elsel=0;h=0;if(T->next)printf("n當(dāng)前二叉樹(shù)的樹(shù)狀圖如下：nn");Lev_Traverse(T->next,TreeDep

60、th(T->next,l,h);system("pause");break;case4:if(!T)printf("您還沒(méi)有建樹(shù)，請(qǐng)先建樹(shù)！nn");system("pause");elseif(!T->next)printf("二叉樹(shù)目前為空樹(shù)，請(qǐng)創(chuàng)建非空樹(shù)后再遍歷!nn");system("pause");elsewhile(choose=Menu()!=0)l=0;h=0;printf("n當(dāng)前二叉樹(shù)的樹(shù)狀圖如下:nn");Lev_Traverse(T-&g

61、t;next,TreeDepth(T->next,l,h);switch(choose)case1:FirstPrint(T->next,i);printf("nn");system("pause");break;case2:MiddlePrint(T->next,i);printf("nn");system("pause");break;case3:LastPrint(T->next,i);printf("nn");system("pause");b

62、reak;case4:PreOrderTraverse(T->next);system("pause");break;case5:InOrderTraverse(T->next);system("pause");break;case6:PostOrderTraverse(T->next);system("pause");break;case7:LevelOrderPrint(T->next);printf("nn");system("pause");break;defau

63、lt:exit(ERROR);break;case5:if(!T)printf("您還沒(méi)有建樹(shù)，請(qǐng)先建樹(shù)！nn");system("pause");elseif(!T->next)printf("二叉樹(shù)目前為空樹(shù)，請(qǐng)創(chuàng)建非空樹(shù)后再查看信息!nn");system("pause");elsewhile(choose=Menu1()!=0)l=0;h=0;printf("n當(dāng)前二叉樹(shù)的樹(shù)狀圖如下:nn");Lev_Traverse(T->next,TreeDepth(T->next,l,h);switch(choose)case1:GetRootElem(T->next);system("pause");break;case2:printf("當(dāng)前二叉樹(shù)的深度為：dnn”,TreeDepth(T->next,l,h);system("pause");break;case3: