數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

圖4-1調(diào)用關(guān)系圖其他功能均為單個(gè)函數(shù)實(shí)現(xiàn)，不做流程描述4.詳細(xì)設(shè)計(jì)4.1數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)：BTNode*LchildNode(BTNode*p)〃返回*p結(jié)點(diǎn)的左孩子結(jié)點(diǎn)指針BTNode*RchildNode(BTNode*p)〃返回*p結(jié)點(diǎn)的右孩子結(jié)點(diǎn)指針voidCreateBTree(BTNode*&b,char*str//創(chuàng)建樹intFindNode(BTNode*b,ElemTypex)//查找結(jié)點(diǎn)是否存在voidInitQueue(SqQueue*&q) //創(chuàng)建隊(duì)列boolQueueEmpty(SqQueue*q) //判斷隊(duì)列是否為空boolenQueue(SqQueue*q,BTNode*e)//進(jìn)隊(duì)列booldeQueue(SqQueue*&q,BTNode*&e)//出隊(duì)列voidDestoryBTree(BTNode*&b) //銷毀釋放二叉樹voidDispBTree(BTNode*b)intBTHeight(BTNode*b)voidPreOrder(BTNode*b)voidInOrder(BTNode*b)voidPostOrder(BTNode*b)voidDispLeaf(BTNode*b)intlistleaf(BTNode*b)intlistnode(BTNode*b)intmaxnode(BTNode*b)intlistfloor(BTNode*b,voidInitStack(SqStack*&s)voidDestroyStack(SqStack*&s)//輸出二叉樹//計(jì)算二叉樹高度//先序遞歸遍歷算法//中序遞歸遍歷算法//后序遞歸遍歷算法//輸出葉子結(jié)點(diǎn)//輸出葉子結(jié)點(diǎn)個(gè)數(shù)voidDispBTree(BTNode*b)intBTHeight(BTNode*b)voidPreOrder(BTNode*b)voidInOrder(BTNode*b)voidPostOrder(BTNode*b)voidDispLeaf(BTNode*b)intlistleaf(BTNode*b)intlistnode(BTNode*b)intmaxnode(BTNode*b)intlistfloor(BTNode*b,voidInitStack(SqStack*&s)voidDestroyStack(SqStack*&s)//輸出二叉樹//計(jì)算二叉樹高度//先序遞歸遍歷算法//中序遞歸遍歷算法//后序遞歸遍歷算法//輸出葉子結(jié)點(diǎn)//輸出葉子結(jié)點(diǎn)個(gè)數(shù)//輸出結(jié)點(diǎn)個(gè)數(shù)//輸出結(jié)點(diǎn)的最大值charx)//輸出結(jié)點(diǎn)在第幾層//初始化棧//銷毀棧boolStackEmpty(SqStack*s)//判斷棧是否為空boolPush(SqStack*&s,BTNode*e)//進(jìn)棧boolPop(SqStack*&s,BTNode*&e)//出棧//先序非遞歸遍歷算法//中序非遞歸遍歷算法//后序非遞歸遍歷算法//層次遍歷算法boolGetTop(SqStack*s,BTNode*&e)//取棧頂元素//先序非遞歸遍歷算法//中序非遞歸遍歷算法//后序非遞歸遍歷算法//層次遍歷算法voidPreOrder1(BTNode*b)voidInOrder1(BTNode*b)voidPostOrder1(BTNode*b)voidLevelOrder(BTNode*b)4.2各模塊流程圖及算法：4.2.1主函數(shù)intmain(){system("cls");system("color00a");BTNode*b;inti,n;charx;cout<<"本程序?yàn)槎鏄涞牟僮?<<endl;charstr[20];cout<<"請輸入你的二叉樹"<<endl;cin.getline(str,20);CreateBTree(b,str);cout<<"創(chuàng)建成功！"<<endl;cout<<"是否繼續(xù)操作繼續(xù)操作請輸入1，否則輸入0"<<endl;cin>>i;while(i！=0){cout<<" "<<endlcout<<"輸入【0】結(jié)束程序"<<endlcout<<"輸入【1】輸出二叉樹"<<endlcout<<"輸入【2】計(jì)算二叉樹高度"<<endlcout<<"輸入【3】查找節(jié)點(diǎn)是否存在"<<endlcout<<"輸入【4】輸出所有葉子結(jié)點(diǎn)"<<endlcout<<"輸入【5】計(jì)算葉子節(jié)點(diǎn)個(gè)數(shù)"<<endlcout<<"輸入【6】前序遍歷輸出二叉樹"<<endlcout<<"輸入【7】中序遍歷輸出二叉樹"<<endlcout<<"輸入【8】后序遍歷輸出二叉樹"<<endlcout<<"輸入【9】計(jì)算結(jié)點(diǎn)個(gè)數(shù)"<<endlcout<<"輸入【10】輸出該樹中結(jié)點(diǎn)最大值"<<endlcout<<"輸入【11】輸出樹中結(jié)點(diǎn)值為x的層"<<endlcout<<"輸入【12】先序非遞歸算法"<<endlcout << " 輸入【13】中序非遞歸算法 " << endl;cout << " 輸入【14】后序非遞歸算法 " << endl;cout << " 輸入【15】層次遍歷(隊(duì)列)算法 " << endl;cout<<" "<<endl;cout<<" >>請輸入你的操作<< "<<endl;cin>>i;//以下為功能選擇相應(yīng)的函數(shù)，比較繁雜，在此不做展示}}4.2.2輸入二叉樹voidCreateBTree(BTNode*&b,char*str){//創(chuàng)建二叉鏈intMaxSize1=50;BTNode*St[MaxSize],*p=NULL;inttop=-1,k=0,j=0;charch=str[j];b=NULL;while(ch!='\0'){//str未掃描完時(shí)循環(huán)switch(ch){case'(':top++;St[top]=p;k=1;break;//可能有左孩子結(jié)點(diǎn)，進(jìn)棧case')':top--;break;case',':k=2;break;//后面為右孩子default:p=(BTNode*)malloc(sizeof(BTNode));p->data=ch;p->lchild=p->rchild=NULL;if(b==NULL)b=p;else{switch(k){St[top]->lchild=p;break;St[top]->rchild=p;break;}}}j++;ch=str[j];〃繼續(xù)掃描str}}4.2.3非遞歸遍歷voidPreOrder1(BTNode*b) //先序非遞歸遍歷算法{

BTNode*p;SqStack*st;InitStack(st);Push(st,b);while(!StackEmpty(st)){Pop(st,p);printf("%c",p->data);〃定義一個(gè)順序棧指針st〃初始化棧st//根節(jié)點(diǎn)進(jìn)棧//棧不為空時(shí)循環(huán)〃定義一個(gè)順序棧指針st〃初始化棧st//根節(jié)點(diǎn)進(jìn)棧//棧不為空時(shí)循環(huán)〃退棧節(jié)點(diǎn)p并訪問它〃訪問節(jié)點(diǎn)pPush(st,p->rchild);if(p->lchild!=NULL)//有左孩子時(shí)將其進(jìn)棧Push(st,p->lchild);}printf("\n");DestroyStack(st); //銷毀棧}voidInOrder1(BTNode*b){BTNode*p;SqStack*st;InitStack(st);if(b!=NULL){voidInOrder1(BTNode*b){BTNode*p;SqStack*st;InitStack(st);if(b!=NULL){p=b;while(!StackEmpty(st)||p{while(p!=NULL){Push(st,p);p=p->lchild;}if(!StackEmpty(st))//中序非遞歸遍歷算法〃定義一個(gè)順序棧指針st〃初始化棧stPop(st,p);printf("%c",p->data);p=p->rchild;!=NULL)〃掃描節(jié)點(diǎn)p的所有左下節(jié)點(diǎn)并進(jìn)?！ü?jié)點(diǎn)p進(jìn)棧//移動(dòng)到左孩子//若棧不空〃出棧節(jié)點(diǎn)p〃訪問節(jié)點(diǎn)p//轉(zhuǎn)向處理其右子樹}}printf("\n");}DestroyStack(st); //銷毀棧}//后序非遞歸遍歷算法//后序非遞歸遍歷算法〃定義一個(gè)順序棧指針st〃初始化棧st〃掃描節(jié)點(diǎn)p的所有左下節(jié)點(diǎn)并進(jìn)?！ü?jié)點(diǎn)p進(jìn)棧//移動(dòng)到左孩子//r指向剛剛訪問的節(jié)點(diǎn)，初始時(shí)為空〃flag為真表示正在處理?xiàng)ｍ敼?jié)點(diǎn)〃取出當(dāng)前的棧頂節(jié)點(diǎn)p〃若節(jié)點(diǎn)p的右孩子為空或者為剛剛訪問過的節(jié)點(diǎn)〃訪問節(jié)點(diǎn)p//r指向剛訪問過的節(jié)點(diǎn)//轉(zhuǎn)向處理其右子樹//表示當(dāng)前不是處理?xiàng)ｍ敼?jié)點(diǎn)//棧不空循環(huán)//銷毀棧voidPostOrder1(BTNode*b){BTNode*p,*r;boolflag;SqStack*st;InitStack(st);p=b;do{while(p!=NULL){Push(st,p);p=p->lchild;}r=NULL;flag=true;while(!StackEmpty(st)&&flag){GetTop(st,p);if(p->rchild==r){printf("%c",p->data);Pop(st,p);r=p;}else{p=p->rchild;flag=false;}}}while(!StackEmpty(st));printf("\n");DestroyStack(st);}4.2.4遞歸遍歷oidPreOrder(BTNode*b){//先序遍歷if(b!=NULL)cout<<(char)b->data;PreOrder(b->lchild);PreOrder(b->rchild);}}voidInOrder(BTNode*b){//中序遍歷if(b!=NULL){InOrder(b->lchild);cout<<(char)b->data;InOrder(b->rchild);}}voidPostOrder(BTNode*b){//后序遍歷if(b!=NULL){PostOrder(b->lchild);PostOrder(b->rchild);cout<<(char)b->data;}}4.3算法的效率分析：主函數(shù)：函數(shù)中并不包含for循環(huán)、遞歸等復(fù)雜的算法，時(shí)間復(fù)雜度為O(1);輸入二叉樹：函數(shù)需要掃描輸入的二叉樹，所以該算法的時(shí)間復(fù)雜度為O(n)；非遞歸類遍歷：由于不管是先序遍歷還是中序遍歷以及后序遍歷，我們都需要利用一個(gè)輔助棧來進(jìn)行每個(gè)節(jié)點(diǎn)的存儲(chǔ)打印，所以每個(gè)節(jié)點(diǎn)都要進(jìn)棧和出棧，不過是根據(jù)那種遍歷方式改變的是每個(gè)節(jié)點(diǎn)的進(jìn)棧順序，所以時(shí)間復(fù)雜度為O(n)，同樣空間復(fù)雜度也為O(n)，n為結(jié)點(diǎn)數(shù)；遞歸類遍歷：空間復(fù)雜度與系統(tǒng)堆棧有關(guān)，系統(tǒng)棧需要記住每個(gè)節(jié)點(diǎn)的值，所以空間復(fù)雜度為O(n)。時(shí)間復(fù)雜度應(yīng)該為O(nlogn)，每個(gè)節(jié)點(diǎn)都要遍歷到，需要n次，而且需要將二叉樹劃分logn次，所以遞歸版的遍歷的空間復(fù)雜度為O(nlogn)；層序遍歷：層序遍歷是通過隊(duì)列來進(jìn)行每個(gè)節(jié)點(diǎn)的存儲(chǔ)打印的，所以時(shí)間復(fù)雜度和空間復(fù)雜度都為O(n)，n為結(jié)點(diǎn)數(shù)。

5.測試即n'lHHiJUn'l川.會(huì)金公殳喪.<人天會(huì)33333-333JJ01234曰

010^345.H-78-ymlll

5.測試即n'lHHiJUn'l川.會(huì)金公殳喪.<人天會(huì)33333-333JJ01234曰

010^345.H-78-ymlll

EEmEEEmE2-二E'-一

^.胃睡*弓.史甥形5','.flrivln.Jv.1列圖5-1初始化菜單圖5-4輸出葉子結(jié)點(diǎn)8后序遞歸遍歷輸出為cbfegda圖5-5輸出后序遞歸遍歷?請輸入你的操作"11青輸入你的結(jié)點(diǎn)“在據(jù)圖5-6查找結(jié)點(diǎn)所在層?請輸入你的操作《?請輸入你的操作《14存序非遞歸遍歷輸出為cbfegda圖5-7輸出后續(xù)非遞歸遍歷?請輸入你的操作它15層次遍歷算法輸出：abdcegf圖5-8層次遍歷輸出結(jié)構(gòu)經(jīng)過多次測試與更改，但是無法打破原有的界面格式，使得界面輸出不夠美觀，程序的遞歸與非遞歸先序、中序、后序遍歷、層次遍歷、計(jì)算結(jié)點(diǎn)個(gè)數(shù)，計(jì)算結(jié)點(diǎn)所在層數(shù)等功能基本能夠流暢地實(shí)現(xiàn)，達(dá)到了應(yīng)有的要求；不過在輸出二叉樹的時(shí)候，不知道為什么后面會(huì)多出一個(gè)括號(hào)，經(jīng)過多次的更改與實(shí)驗(yàn)也沒有將其更改成功，通過查看相關(guān)書籍以及網(wǎng)上搜索算法原理，終于明白了錯(cuò)誤所在，并完成了排錯(cuò)。6．課程設(shè)計(jì)心得改進(jìn)方案對自己的設(shè)計(jì)進(jìn)行評價(jià)，指出合理和不足之處，提出改進(jìn)方案；1)菜單設(shè)置方面：運(yùn)用了if()語句，這樣看著沒有條理，不適合用在二叉樹的遍歷上，因?yàn)楸闅v結(jié)果顯而易見并不十分復(fù)雜，沒有必要使程序復(fù)雜化，故采用的是程序運(yùn)行輸出模式。2)二叉樹的創(chuàng)建：采用二叉鏈表存儲(chǔ)的方式，利用擴(kuò)展先序遍歷實(shí)現(xiàn)二叉樹的創(chuàng)建，這樣做相對簡單，但是對有些情況下不太實(shí)用，所以應(yīng)該增加一項(xiàng)根據(jù)后序中序?qū)崿F(xiàn)創(chuàng)建的算法，是程序更加完善。3)整體布局：由于存在某兩個(gè)函數(shù)的制約關(guān)系，要求必須先執(zhí)行A在執(zhí)行B,一旦執(zhí)行順序錯(cuò)誤就會(huì)導(dǎo)致輸出結(jié)果錯(cuò)誤。這樣降低了程序的冗錯(cuò)性，不利于用戶操作，可以通過添加函數(shù)間強(qiáng)制裝換關(guān)系，強(qiáng)制執(zhí)行，或者是在后者運(yùn)行的函數(shù)中添加必要語句，使其脫離制約函數(shù)的制約。設(shè)計(jì)心得其實(shí)在本程序的設(shè)計(jì)過程當(dāng)中，沒有很吸引人的關(guān)鍵技術(shù)，因?yàn)楸救说腃語言或C++語言都不是學(xué)的很好，所以當(dāng)初設(shè)計(jì)的時(shí)候就只是想把功能都實(shí)現(xiàn)就好了，盡可能的把所要求的功能都編進(jìn)程序，這樣就覺得很滿足了。所以都是設(shè)計(jì)的比較簡單易懂的語言，這樣自己能夠更明白一些，所以就沒有時(shí)間去細(xì)細(xì)地去設(shè)計(jì)自己的程序。本程序要說有什么值得說的，那就只有人性化這點(diǎn)了，在設(shè)計(jì)成學(xué)的時(shí)候，因?yàn)樽约号屡炝耍蕴砑恿撕茉敱M的提示，這樣在編程的過程中或調(diào)試的時(shí)候都能夠比較快的運(yùn)行。還有就是盡可能的應(yīng)用了do-while語句和switch-case語句，這兩個(gè)語句在之前不是很常用，所以在這個(gè)程序中試煉了一下，雖然在編寫的過程中總是出錯(cuò)，但還是成功的用好了，也是程序有條理一些。我也知道這些東西別人可能比我弄得還要好，但是我在我所學(xué)的知識(shí)中成功的應(yīng)用了這些，我覺得就是好事，就是進(jìn)步。唯一的亮點(diǎn)可能就是進(jìn)入系統(tǒng)是的密碼設(shè)計(jì)了，就這一點(diǎn)小小的設(shè)計(jì)就花了我好幾個(gè)小時(shí)去調(diào)試，因?yàn)榭偰茉诤竺娉绦虻募尤爰斑\(yùn)行時(shí)發(fā)現(xiàn)一些新的小問題。一周多的課程設(shè)計(jì)，終于成功的驗(yàn)收了，雖然有些疲憊，但還是有很多的收獲的，像計(jì)算機(jī)組成原理的課設(shè)一樣，我又一次鞏固了所學(xué)到的知識(shí)，之前的學(xué)習(xí)只是停留在理論基礎(chǔ)上，現(xiàn)在自己動(dòng)手操作試驗(yàn)后，才是真正的理解及體會(huì)。C也學(xué)了近一年，有很多知識(shí)都是似懂非懂，通過平時(shí)上機(jī)操作，自己也了解了一些，但讓我有了更深的理解和更好的認(rèn)識(shí)，則是在這次的課設(shè)上，之前的困惑也通過這次的課設(shè)解決了一些，雖然還是不能夠全面的理解，但是有進(jìn)步就很高興。在課程設(shè)計(jì)之前，因?yàn)橛辛司C合實(shí)驗(yàn)的經(jīng)驗(yàn)與教訓(xùn)，明白了寫代碼這一步是非常重要的，因?yàn)楫?dāng)你把代碼輸進(jìn)去之后，并編譯讓其運(yùn)行，發(fā)現(xiàn)通過不了，再來檢查出問題，是很費(fèi)費(fèi)力的事情，因此分析和規(guī)劃代碼是很重要的，最重要的是要把邏輯結(jié)構(gòu)寫好，這樣就不會(huì)出現(xiàn)大問題，寫代碼就要先找出核心的內(nèi)容，用多種方法來實(shí)現(xiàn)核心部分，這樣可以盡可能的避免發(fā)現(xiàn)邏輯或編譯不支持的錯(cuò)誤。通過本次論文設(shè)計(jì)，我初步學(xué)會(huì)了論文設(shè)計(jì)的基本方法，學(xué)會(huì)了怎樣去借鑒別人的方法和經(jīng)驗(yàn)，知道了如何整合資料和處理這些資料的能力，這為以后做畢設(shè)的論文打下了基礎(chǔ)，使我感覺比較好的是有一種成功的喜悅，雖然在編譯的時(shí)候會(huì)經(jīng)常因?yàn)橐恍┬〉腻e(cuò)誤而心煩意亂，但是也不失為一件好事，失敗的越多積累的經(jīng)驗(yàn)越豐富，對人的考驗(yàn)也比較多，那么在最后編譯成功時(shí)的喜悅就越濃烈，也是自己的能力有了進(jìn)一步的提高。由于知識(shí)和經(jīng)驗(yàn)的不足，這個(gè)程序編寫的不是很盡如人意，但是融合了自己的心血，就覺得是最好的，所以在以后還是需要較多的努力的，還是會(huì)在以后的學(xué)習(xí)過程中不斷地提高和改進(jìn)的。7．參考文獻(xiàn)[1]《算法導(dǎo)論》（英文名：IntroductiontoAlgorithm）主編：ThomasH.Cormen、CharlesE.Leiserson等譯者:潘金貴、顧鐵成出版社:機(jī)械工業(yè)出版社（第三版）[2]《數(shù)據(jù)結(jié)構(gòu)與算法》主編：王曙燕 2013年9月第1版人民郵電出版社[3]《C語言程序設(shè)計(jì)教程》主編：王曙燕2014年9月第1版人民郵電出版社[4]譚浩強(qiáng).C程序設(shè)計(jì)（第三版）[M].北京:清華大學(xué)出版社，2005.8．附錄#include<fstream>#include<iostream>#include<stdlib.h>#include<stdio.h>#include<string>#include"work.h"usingnamespacestd;#defineMaxSize100usingnamespacestd;typedefcharElemType;typedefstructb{ElemTypedata;structb*Ichild,*rchild;//二叉樹結(jié)構(gòu)聲明}BTNode;typedefstruct{BTNode*data[100];//存放棧中的數(shù)據(jù)元素inttop; //存放棧頂指針，即棧頂元素在data數(shù)組中的下標(biāo)}SqStack;typedefstruct{BTNode*data[MaxSize];//存放隊(duì)中元素intfront,rear;//隊(duì)頭隊(duì)尾指針}SqQueue;intwidth[10]={0};//存放各層寬度的數(shù)組BTNode*LchildNode(BTNode*p)/*返回*p結(jié)點(diǎn)的左孩子結(jié)點(diǎn)指針*/{returnp->lchild;}BTNode*RchildNode(BTNode*p)/*返回*p結(jié)點(diǎn)的右孩子結(jié)點(diǎn)指針*/{returnp->rchild;}voidCreateBTree(BTNode*&b,char*str){//創(chuàng)建二叉鏈intMaxSize1=50;BTNode*St[MaxSize],*p=NULL;inttop=-1,k=0,j=0;charch=str[j];b=NULL;while(ch!='\0'){ //str未掃描完時(shí)循環(huán)switch(ch){case'(':top++;St[top]=p;k=1;break;//可能有左孩子結(jié)點(diǎn)，進(jìn)棧case')':top--;break;case',':k=2;break; //后面為右孩子default:p=(BTNode*)malloc(sizeof(BTNode));p->data=ch;p->lchild=p->rchild=NULL;if(b==NULL)

b=p;else{switch(k){case1:St[top]->lchild=p;break;case2:St[top]->rchild=p;break;}}}j++;ch=str[j];〃繼續(xù)掃描str}}intFindNode(BTNode*b,ElemTypex){intp;if(b==NULL){returnNULL;}elseif(b->data==x){returnx;}elsep=FindNode(b->lchild,x);if(p!=NULL){returnp;}elsereturnFindNode(b->rchild,x);}}///隊(duì)列的有關(guān)操作voidInitQueue(SqQueue*&q){q=(SqQueue*)malloc(sizeof(SqQueue));q->front=q->rear=0;}//判斷隊(duì)列是否為空boolQueueEmpty(SqQueue*q){return(q->front==q->rear);}//進(jìn)隊(duì)列boolenQueue(SqQueue*q,BTNode*e){if((q->rear+1)%MaxSize==q->front)//隊(duì)滿溢出returnfalse;q->rear=(q->rear+1)%MaxSize;q->data[q->rear]=e;returntrue;}//出隊(duì)列booldeQueue(SqQueue*&q,BTNode*&e){if(q->front==q->rear)//^U斷是否隊(duì)空returnfalse;q->front=(q->front+1)%MaxSize;e=q->data[q->front];returnfalse;}voidDestoryBTree(BTNode*&b){if(b!=NULL)DestoryBTree(b->lchild);DestoryBTree(b->rchild);free(b);}}voidDispBTree(BTNode*b){//輸出單鏈表if(b!=NULL){cout<<(char)b->data<<"";if(b->lchild!=NULL||b->rchild!=NULL){cout<<"(";DispBTree(b->lchild);if(b->rchild!=NULL)cout<<",";DispBTree(b->rchild);cout<<")";}}}intBTHeight(BTNode*b){//樹的高度intlchildh,rchildh;if(b==NULL)return(0);lchildh=BTHeight(b->lchild);rchildh=BTHeight(b->rchild);return(lchildh>rchildh)?(lchildh+1):(rchildh+1);}voidPreOrder(BTNode*b){//先序遍歷if(b!=NULL){cout<<(char)b->data;PreOrder(b->lchild);returnreturn1;PreOrder(b->rchild);}voidInOrder(BTNode*b){//中序遍歷if(b!=NULL){InOrder(b->lchild);cout<<(char)b->data;InOrder(b->rchild);}}voidPostOrder(BTNode*b){//后序遍歷if(b!=NULL){PostOrder(b->lchild);PostOrder(b->rchild);cout<<(char)b->data;}}voidDispLeaf(BTNode*b){//遞歸輸出葉子節(jié)點(diǎn)if(b!=NULL){if(b->lchild==NULL&b->rchild==NULL)cout<<(char)b->data;DispLeaf(b->lchild);DispLeaf(b->rchild);}}intlistleaf(BTNode*b){//輸出葉子結(jié)點(diǎn)個(gè)數(shù)intnum1;if(b==NULL)return0;elseif(b->lchild==NULL&&b->rchild==NULL)num1=listleaf(b->rchild)+listleaf(b->lchild);returnnum1;}intlistnode(BTNode*b){intnum;if(b==NULL)return(0);else{num=listnode(b->lchild)+listnode(b->rchild)+1;}returnnum;}intmaxnode(BTNode*b){if(NULL==b)return0;intmaxLeft=maxnode(b->lchild);intmaxRight=maxnode(b->rchild);intmax=maxLeft>maxRight?maxLeft:maxRight;returnmax>b->data?max:b->data;}intlistfloor(BTNode*b,charx){intnum2,m,n;if(b==NULL)num2=0;elseif(b->data==x)num2=1;else{m=listfloor(b->lchild,x);n=listfloor(b->rchild,x);if(m==0&&n==0)num2=0;elsenum2=((m>n)?m:n)+1;}returnnum2;returnnum2;returnfalse;//棧頂e)//取棧//先序//定義//棧頂e)//取棧//先序//定義//根節(jié)intLevel(BTNode*b,ElemTypex,inth){intl;if(b==NULL)return(0);elseif((char)b->data==(char)x)return(h);else{l=Level(b->lchild,x,h+1);//左子樹中查找if(l!=0)return(l);//在左子樹中找到，返回lelsereturn(Level(b->rchild,x,h+1));//在左子樹中未找到再在右子樹中查找}}//棧的所有操作如下voidInitStack(SqStack*&s) //初始化棧{s=(SqStack*)malloc(sizeof(SqStack));//分配一個(gè)是順序棧空間，首地址存放在s中s->top=-1;//棧頂指針置為-1}voidDestroyStack(SqStack*&s)//銷毀棧{free(s);}boolStackEmpty(SqStack*s) //判斷棧是否為空{(diào)return(s->top==-1);}boolPush(SqStack*&s,BTNode*e)//進(jìn)棧{if(s->top==MaxSize-1)//棧滿的情況，即棧上溢出s->top++; //棧頂指針增1s->data[s->top]=e;〃元素e放在棧頂指針處returntrue;}boolPop(SqStack*&s,BTNode*&e)//出棧{if(s->top==-1)//棧為空的情況，即棧下溢出returnfalse;e=s->data[s->top];//取棧頂指針元素的元素s->top--;指針減1returntrue;}boolGetTop(SqStack*s,BTNode*&頂元素{if(s->top==-1)//棧為空的情況，即棧下溢出returnfalse;e=s->data[s->top];//取棧頂元素returntrue;}voidPreOrder1(BTNode*b)非遞歸遍歷算法{BTNode*p;SqStack*st;一個(gè)順序棧指缽tInitStack(st);〃初始化棧stPush(st,b);點(diǎn)進(jìn)棧while(!StackEmpty(st))//棧不為空時(shí)循環(huán){Pop(st,p); //退棧節(jié)點(diǎn)p并訪問它printf("%c",p->data);//訪問節(jié)點(diǎn)pif(p->rchild!=NULL)//有右孩子時(shí)將其進(jìn)棧Push(st,p->rchild);if(p->lchild!=NULL)//有左孩子時(shí)將其進(jìn)棧Push(st,p->lchild);}printf("\n");DestroyStack(st); //銷毀棧}//中序非遞歸遍歷voidInOrder1(BTNode*b)//中序非遞歸遍歷算法{BTNode*p;SqStack*st;〃定義一個(gè)順序棧指針stInitStack(st);〃初始化棧stif(b!=NULL){p=b;while(!StackEmpty(st)||p!=NULL){while(p!=NULL)〃掃描節(jié)點(diǎn)p的所有左下節(jié)點(diǎn)并進(jìn)棧{Push(st,p);〃節(jié)點(diǎn)p進(jìn)棧p=p->lchild;//移動(dòng)到左孩子}if(!StackEmpty(st))//若棧不空{(diào)Pop(st,p);〃出棧節(jié)點(diǎn)pprintf("%c",p->data);〃訪問節(jié)點(diǎn)pp=p->rchild;//轉(zhuǎn)向處理其右子樹}}printf("\n");}DestroyStack(st); //銷毀棧}voidPostOrder1(BTNode*b)//后序非遞歸遍歷算法{BTNode*p,*r;boolflag;SqStack*st;〃定義一個(gè)順序棧指針stInitStack(st);〃初始化棧stp=b;do{while(p!=NULL)〃掃描節(jié)點(diǎn)p的所有左下節(jié)點(diǎn)并進(jìn)棧{Push(st,p);〃節(jié)點(diǎn)p進(jìn)棧p=p->lchild;//移動(dòng)到左孩子}r=NULL;//r指向剛剛訪問的節(jié)點(diǎn)，初始時(shí)為空flag=true;//flag為真表示正在處理?xiàng)ｍ敼?jié)點(diǎn)while(!StackEmpty(st)&&flag){GetTop(st,p);〃取出當(dāng)前的棧頂節(jié)點(diǎn)pif(p->rchild==r)//若節(jié)點(diǎn)p的右孩子為空或者為剛剛訪問過的節(jié)點(diǎn){//訪問節(jié)點(diǎn)pprintf("%c",p->data);Pop(st,p);r=p;//r指向剛訪問過的節(jié)點(diǎn)}else{p=p->rchild;//轉(zhuǎn)向處理其右子樹flag=false;//表示當(dāng)前不是處理?xiàng)ｍ敼?jié)點(diǎn)}}}while(!StackEmpty(st));//棧不空循環(huán)printf("\n");DestroyStack(st); //銷毀棧}voidLevelOrder(BTNode*b){BTNode*p;SqQueue*qu;InitQueue(qu);//初始化隊(duì)列enQueue(qu,b);//根結(jié)點(diǎn)指針進(jìn)入隊(duì)列while(!QueueEmpty(qu))//隊(duì)不為空時(shí)循環(huán){deQueue(qu,p);//出隊(duì)結(jié)點(diǎn)pcout<<(char)p->data<<"";if(p->lchild!=NULL)//有{enQueue(qu,p->lchild);}if(p->rchild!=NULL)//有右孩子進(jìn)隊(duì){enQueue(qu,p->rchild);}}}intmain(){system("cls");system("color00a");BTNode*b;inti,n;charx;cout<<"本程序?yàn)槎鏄涞牟僮?<<endl;charstr[20];cout<<"請輸入你的二叉樹"<<endl;cin.getline(str,20);CreateBTree(b,str);cout<<”創(chuàng)建成功！"<<endl;cout<<"是否繼續(xù)操作繼續(xù)操作請輸入1，否則輸入0"<<endl;cin>>i;while(i!=0){cout <<〃-"<<endl;cout<<"--輸入【0】結(jié)束程序"<<endl;cout<<"輸入【1】輸出二叉樹"<<endl;cout<<"輸入【2】計(jì)算二叉樹高度"<<endl;cout<<"輸入【3】查找節(jié)點(diǎn)是否存在"<<endl;cout<<"輸入【4】輸出所有葉子結(jié)點(diǎn)"<<endl;cout<<"輸入【5】計(jì)算葉子節(jié)點(diǎn)個(gè)數(shù)"<<endl;cout<<"輸入【6】前序遍歷輸出二叉樹"<<endl;cout<<"輸入【7】中序遍歷輸出二叉樹"<<endl;cout<<"輸入【8】后序遍歷輸出二叉樹"<<endl;cout<<"輸入【9】計(jì)算結(jié)點(diǎn)個(gè)數(shù)"<<endl;cout<<"輸入【10】輸出該樹中結(jié)點(diǎn)最大值"<<endl;cout<<"輸入【