數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)二叉樹

..實(shí)驗(yàn)六：二叉樹及其應(yīng)用一、實(shí)驗(yàn)?zāi)康?樹是數(shù)據(jù)結(jié)構(gòu)中應(yīng)用極為廣泛的非線性結(jié)構(gòu),本單元的實(shí)驗(yàn)達(dá)到熟悉二叉樹的存儲(chǔ)結(jié)構(gòu)的特性,以及如何應(yīng)用樹結(jié)構(gòu)解決具體問題。二、問題描述首先,掌握二叉樹的各種存儲(chǔ)結(jié)構(gòu)和熟悉對(duì)二叉樹的基本操作。其次,以二叉樹表示算術(shù)表達(dá)式的基礎(chǔ)上,設(shè)計(jì)一個(gè)十進(jìn)制的四則運(yùn)算的計(jì)算器。如算術(shù)表達(dá)式：a+b*<c-d>-e/f三、實(shí)驗(yàn)要求如果利用完全二叉樹的性質(zhì)和二叉鏈表結(jié)構(gòu)建立一棵二叉樹,分別計(jì)算統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(shù)。求二叉樹的深度。十進(jìn)制的四則運(yùn)算的計(jì)算器可以接收用戶來自鍵盤的輸入。由輸入的表達(dá)式字符串動(dòng)態(tài)生成算術(shù)表達(dá)式所對(duì)應(yīng)的二叉樹。自動(dòng)完成求值運(yùn)算和輸出結(jié)果。四、實(shí)驗(yàn)環(huán)境 PC微機(jī) DOS操作系統(tǒng)或Windows操作系統(tǒng) TurboC程序集成環(huán)境或VisualC++程序集成環(huán)境五、實(shí)驗(yàn)步驟1、根據(jù)二叉樹的各種存儲(chǔ)結(jié)構(gòu)建立二叉樹；2、設(shè)計(jì)求葉子結(jié)點(diǎn)個(gè)數(shù)算法和樹的深度算法；3、根據(jù)表達(dá)式建立相應(yīng)的二叉樹,生成表達(dá)式樹的模塊；4、根據(jù)表達(dá)式樹,求出表達(dá)式值,生成求值模塊；5、程序運(yùn)行效果,測(cè)試數(shù)據(jù)分析算法。六、測(cè)試數(shù)據(jù)1、輸入數(shù)據(jù)：2.2*〔3.1+1.20-7.5/3 正確結(jié)果：6.962、輸入數(shù)據(jù)：<1+2>*3+<5+6*7>;正確輸出：56七、表達(dá)式求值由于表達(dá)式求值算法較為復(fù)雜,所以單獨(dú)列出來加以分析：1、主要思路：由于操作數(shù)是任意的實(shí)數(shù),所以必須將原始的中綴表達(dá)式中的操作數(shù)、操作符以及括號(hào)分解出來,并以字符串的形式保存；然后再將其轉(zhuǎn)換為后綴表達(dá)式的順序,后綴表達(dá)式可以很容易地利用堆棧計(jì)算出表達(dá)式的值。例如有如下的中綴表達(dá)式：a+b-c轉(zhuǎn)換成后綴表達(dá)式為：ab+c-然后分別按從左到右放入棧中,如果碰到操作符就從棧中彈出兩個(gè)操作數(shù)進(jìn)行運(yùn)算,最后再將運(yùn)算結(jié)果放入棧中,依次進(jìn)行直到表達(dá)式結(jié)束。如上述的后綴表達(dá)式先將a和b放入棧中,然后碰到操作符"+",則從棧中彈出a和b進(jìn)行a+b的運(yùn)算,并將其結(jié)果d〔假設(shè)為d放入棧中,然后再將c放入棧中,最后是操作符"-",所以再彈出d和c進(jìn)行d-c運(yùn)算,并將其結(jié)果再次放入棧中,此時(shí)表達(dá)式結(jié)束,則棧中的元素值就是該表達(dá)式最后的運(yùn)算結(jié)果。當(dāng)然將原始的中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式比較關(guān)鍵,要同時(shí)考慮操作符的優(yōu)先級(jí)以及對(duì)有括號(hào)的情況下的處理,相關(guān)內(nèi)容會(huì)在算法具體實(shí)現(xiàn)中詳細(xì)討論。2、求值過程一、將原始的中綴表達(dá)式中的操作數(shù)、操作符以及括號(hào)按順序分解出來,并以字符串的形式保存。二、將分解的中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的形式,即調(diào)整各項(xiàng)字符串的順序,并將括號(hào)處理掉。三、計(jì)算后綴表達(dá)式的值。3、中綴表達(dá)式分解DivideExpressionToItem<>函數(shù)。分解出原始中綴表達(dá)式中的操作數(shù)、操作符以及括號(hào),保存在隊(duì)列中,以本實(shí)驗(yàn)中的數(shù)據(jù)為例,分解完成后隊(duì)列中的保存順序如下圖所示：隊(duì)首隊(duì)尾其算法思想是：從左往右按一個(gè)字節(jié)依次掃描原始中綴表達(dá)式m_string,碰到連續(xù)的數(shù)字或小數(shù)點(diǎn)就加到string變量str中；如果碰到括號(hào)或操作符就將原先的str推入隊(duì)列,然后將括號(hào)或操作符賦予str,再將str推入隊(duì)列,并將str賦予空值,依次循環(huán)進(jìn)行直到掃描m_string完成。轉(zhuǎn)化為后綴表達(dá)式ChangeToSuffix<>函數(shù)。將保存在隊(duì)列中的中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式,并保存在棧中。這個(gè)函數(shù)也是整個(gè)表達(dá)式算法的關(guān)鍵,這里需要兩個(gè)棧stack_A和stack_B,分別在轉(zhuǎn)換過程中臨時(shí)存放后綴表達(dá)式的操作數(shù)與操作符。依次從中綴表達(dá)式隊(duì)列que中出列一個(gè)元素,并保存在一個(gè)string變量str中,然后按以下幾方面進(jìn)行處理：①如果str是"<",則將str推入棧stack_B。②如果str是">",則要考慮stack_B的棧頂是不是"<",是的話就將"<"出棧stack_B；如果不是,則將stack_B出棧一個(gè)元素〔操作符,然后將其推入棧stack_A。③如果str是"+"或"-",則要考慮有括號(hào)和優(yōu)先級(jí)的情況,如果棧stack_B為空或者棧頂為"<",則將str推入棧stack_B；因?yàn)椴僮鞣?+"和"-"優(yōu)先級(jí)相同〔誰先出現(xiàn)就先處理誰進(jìn)棧stack_A,并且低于"*"和"/",所以當(dāng)棧stack_B不為空并且棧頂不為"<",則依次循環(huán)取出stack_B的棧頂元素并依次推入棧stack_A,循環(huán)結(jié)束后再將str推入棧stack_B。④如果str是"*"或"/",因?yàn)樗鼈兊膬?yōu)先級(jí)相同并且高于"+"和"-",所以如果棧stack_B為空或者棧頂為"+"、"-"或"<"就直接將str推入棧stack_B；否則就將stack_B彈出一個(gè)元素并將其推入棧stack_A中,然后再將str推入棧stack_B中。⑤除了上述情況外就只剩下操作數(shù)了,操作數(shù)就可以直接推入棧stack_A中。注意整個(gè)過程中棧stack_B中的元素只能是如下幾種："<"、"+"、"-"、"*"、"/",而最終棧stack_A保存的是后綴表達(dá)式。只有操作數(shù)和操作符,如下圖所示：注意到最后返回的是stack_B而不是stack_A,因?yàn)榭紤]到為了后面的計(jì)算方便,所以將其倒序保存在stack_B中〔最后一個(gè)while循環(huán)。后綴表達(dá)式求值Calculate<>函數(shù)。剩下的計(jì)算后綴表達(dá)式就顯得非常簡(jiǎn)單了,依次將倒序的后綴表達(dá)式stack_B彈出一個(gè)元素推入保存結(jié)果的double類型的棧stack中,如果遇到操作符就從棧stack中彈出兩元素進(jìn)行該操作符的運(yùn)算并將其結(jié)果推入到棧stack中,依次循環(huán)進(jìn)行直到棧stack_B為空,最后棧stack只有一個(gè)元素即為表達(dá)式的結(jié)果。八、實(shí)驗(yàn)報(bào)告要求實(shí)驗(yàn)報(bào)告應(yīng)包括以下幾個(gè)部分：設(shè)計(jì)算術(shù)表達(dá)式樹的存儲(chǔ)結(jié)構(gòu)；實(shí)驗(yàn)中采用的是二叉樹的的鏈接存儲(chǔ)。結(jié)點(diǎn)格式如下：其嚴(yán)格類的定義如下：template<typenameT>classBinarynode//二叉樹的結(jié)點(diǎn)類{ public: Binarynode<>:left<NULL>,right<NULL>{}//默認(rèn)構(gòu)造函數(shù) Binarynode<constT&item,Binarynode<T>*lptr=NULL, Binarynode<T>*rptr=NULL>:data<item>,left<lptr>,right<rptr>{}//初始化 Tdata;//結(jié)點(diǎn)數(shù)據(jù) Binarynode<T>*&Left<>{returnleft;}//取left Binarynode<T>*&Right<>{returnright;}//取right protected: Binarynode<T>*left,*right;};給出二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)算法和樹的深度算法描述；葉子結(jié)點(diǎn)個(gè)數(shù)算法：template<typenameT>voidLeafcount<Binarynode<T>*t,int*c>//計(jì)算樹葉子的個(gè)數(shù){//t為構(gòu)建的樹,c用來返回葉子節(jié)點(diǎn)個(gè)數(shù) if<t>//樹不為空 { if<t->Left<>==NULL&&t->Right<>==NULL>//若該結(jié)點(diǎn)左右均為空,為葉子結(jié)點(diǎn) { *c=*c+1; } Leafcount<t->Left<>,c>;//左子樹遞歸求葉子結(jié)點(diǎn) Leafcount<t->Right<>,c>;//右子樹遞歸求葉子結(jié)點(diǎn) }}樹的深度算法：intDepth<Binarynode<T>*t>//計(jì)算樹的深度{intlh,rh;//定義左右子樹的深度if<!t>return0;//樹為空返回0else{ lh=Depth<t->Left<>>;//遞歸調(diào)用,求左子樹深度 rh=Depth<t->Right<>>;//遞歸調(diào)用,求右子樹深度 if<lh>rh>//判斷左右子樹哪個(gè)更大,更大的深度加1返回其值 returnlh+1; else returnrh+1;}return1;}相應(yīng)的程序要給出足夠的注釋部分；參見九、附錄,由于在報(bào)告中分析的算法,在附錄源程序中省略部分注釋,以免繁雜。給出程序的測(cè)試結(jié)果驗(yàn)證各項(xiàng)程序功能如下：進(jìn)入模塊選擇進(jìn)入模塊一：進(jìn)入模塊二：四種遍歷以先序序列為ABDECF,中序序列DBEAFC為例：求樹的葉子結(jié)點(diǎn)數(shù)和樹的深度求表達(dá)式的值1、輸入數(shù)據(jù)：2.2*〔3.1+1.20-7.5/3 正確結(jié)果：6.962、輸入數(shù)據(jù)：<1+2>*3+<5+6*7>; 正確輸出：56九、思考題與實(shí)驗(yàn)總結(jié)1、分析利用完全二叉樹的性質(zhì)和二叉鏈表存儲(chǔ)有什么不同？分析其優(yōu)缺點(diǎn)。其實(shí)利用完全二叉樹的性質(zhì)的存儲(chǔ)本質(zhì)上是順序存儲(chǔ),但是又區(qū)別于一般的順序存儲(chǔ),由于樹無法在順序表直接進(jìn)行存儲(chǔ),所以在描述二叉樹的時(shí)候規(guī)定樹從左到右,從上到下依次存儲(chǔ)樹結(jié)點(diǎn),不存在的結(jié)點(diǎn)也要存儲(chǔ),其以0表示,對(duì)于完全二叉樹來講,只要知道結(jié)點(diǎn)在樹中的編號(hào),就能迅速定位該結(jié)點(diǎn),但是由于要存儲(chǔ)0來表示空結(jié)點(diǎn),在結(jié)點(diǎn)數(shù)龐大的時(shí)候會(huì)有可能浪費(fèi)空間。最后,它若要增加結(jié)點(diǎn),若新增結(jié)點(diǎn)已超出范圍,則必須要重新申請(qǐng)空間。而二叉鏈表存儲(chǔ)則是典型鏈表存儲(chǔ),它要利用指針來指向其左右孩子。如果要查找某一結(jié)點(diǎn),必須從根出發(fā),但是不會(huì)像利用完全二叉樹的性質(zhì)存儲(chǔ)那樣浪費(fèi)不必要的空間。在增加結(jié)點(diǎn)時(shí)更容易。綜上分析,其優(yōu)缺點(diǎn)：完全二叉樹性質(zhì)存儲(chǔ)：優(yōu)點(diǎn),查找結(jié)點(diǎn)速度快,易于理解,在結(jié)點(diǎn)數(shù)少的情況下,存儲(chǔ)方便。缺點(diǎn),存儲(chǔ)大量結(jié)點(diǎn)可能會(huì)浪費(fèi)大量空間,增加結(jié)點(diǎn)復(fù)雜。二叉鏈表存儲(chǔ)：優(yōu)點(diǎn),增加結(jié)點(diǎn)容易,易于存儲(chǔ)結(jié)點(diǎn)數(shù)比較大的樹。而且指針靈活的應(yīng)用,更易與在樹上進(jìn)行復(fù)雜的操作。缺點(diǎn),查找結(jié)點(diǎn)必須從根出發(fā),依次遍歷。2、增加輸入表達(dá)式進(jìn)行語法判錯(cuò)的功能。IsWellForm<>函數(shù)。判斷原始中綴表達(dá)式的括號(hào)是否匹配,可以利用棧簡(jiǎn)單實(shí)現(xiàn),即遇到"<"進(jìn)棧,遇到">"就從棧中彈出一個(gè)元素,直到表達(dá)式結(jié)束。如果棧為空則表示括號(hào)匹配,否則不匹配。其具體實(shí)現(xiàn)見附錄。下面是程序的試驗(yàn)：3．實(shí)驗(yàn)總結(jié)實(shí)驗(yàn)終于完成了,相對(duì)來說難度很大,不過由于這個(gè)是數(shù)據(jù)結(jié)構(gòu)的重中之重,所以花了蠻多的心思的,樹的確有很多優(yōu)點(diǎn),使得它如此舉足輕重,它可以勾勒生活中的方方面面的關(guān)系,特別在當(dāng)今社會(huì)數(shù)據(jù)關(guān)系如此復(fù)雜的情況下,它獨(dú)享風(fēng)光是可以理解的。不過由于它結(jié)構(gòu)復(fù)雜多變,所以存儲(chǔ)起來就頗為費(fèi)勁了,這造成了我在實(shí)驗(yàn)中吃苦頭的主要因素。實(shí)驗(yàn)中第一次嘗試用VISIO畫圖表,發(fā)現(xiàn)它的確是個(gè)畫圖表的好工具。最后對(duì)于實(shí)驗(yàn)本身不多說了,比較滿意,但是需要進(jìn)一步了解樹,了解編程。十、附錄源程序包含三個(gè)文件,頭文件binarynode.h主要給出了二叉樹結(jié)點(diǎn)類的定義和表達(dá)式二叉樹類的定義及其相關(guān)函數(shù)。頭文件bt_algorithm.h主要給出了二叉樹的相關(guān)基本操作。主程序則包含兩個(gè)模塊,子模塊一是基于用戶自己構(gòu)建的二叉樹的相關(guān)基本操作,包括各種遍歷,求二叉樹的葉子數(shù)和求樹的深度。子模塊二主要是表達(dá)式求值的運(yùn)算,由用戶輸入中綴表達(dá)式,經(jīng)過運(yùn)算直接輸出結(jié)果。下面給出以上三個(gè)文件。binarynode.h//該頭文件主要給出二叉樹結(jié)點(diǎn)的定義和表達(dá)式二叉樹類及其相關(guān)的計(jì)算函數(shù)#ifdefWIN32#pragmawarning<disable:4786>#endif#include<string>#include<stack>#include<queue>usingnamespacestd;template<typenameT>classBinarynode//二叉樹的結(jié)點(diǎn)類{ public: Binarynode<>:left<NULL>,right<NULL>{}//默認(rèn)構(gòu)造函數(shù) Binarynode<constT&item,Binarynode<T>*lptr=NULL, Binarynode<T>*rptr=NULL>:data<item>,left<lptr>,right<rptr>{}//初始化二叉樹 Tdata;//結(jié)點(diǎn)數(shù)據(jù) Binarynode<T>*&Left<>{returnleft;}//取left Binarynode<T>*&Right<>{returnright;}//取right protected: Binarynode<T>*left,*right;};classExpressionType//表達(dá)式二叉樹類{public: ExpressionType<>; ExpressionType<stringm_string>; voidoperator=<stringm_string>;//將一個(gè)字符串表達(dá)式賦予m_string doubleCalculate<>;//計(jì)算轉(zhuǎn)換后的后綴表達(dá)式的值private: queue<string>DivideExpressionToItem<>;//將原始的中綴表達(dá)式中的操作數(shù)、操作符以及括號(hào)按順序以//字符串的形式分解出來,然后保存在一個(gè)隊(duì)列中 stack<string>ChangeToSuffix<>;//將隊(duì)列中表示原始表達(dá)式各項(xiàng)的字符串調(diào)整順序,轉(zhuǎn)換成后綴表達(dá)式的//順序,并處理掉括號(hào),然后保存在一個(gè)棧中 boolIsWellForm<>;//判斷原始表達(dá)式中的括號(hào)是否匹配,如果匹配返回true,否則返回false。 intSize<>;//返回原始表達(dá)式所包含的字節(jié)數(shù)。private: stringm_string;//存儲(chǔ)表示原始中綴表達(dá)式的字符串。};ExpressionType::ExpressionType<>//構(gòu)造函數(shù){ m_string="";}ExpressionType::ExpressionType<stringm_string>{ this->m_string=m_string;}voidExpressionType::operator=<stringm_string>//賦值{ this->m_string=m_string;}intExpressionType::Size<>//中綴表達(dá)式包含字節(jié)數(shù){ returnm_string.size<>;}boolExpressionType::IsWellForm<>//判斷表達(dá)式正確與否{ stack<char>stack; intsize=Size<>; charch; for<inti=0;i<size;i++> { ch=m_string.at<i>; switch<ch> { case'<': stack.push<ch>; break; case'>': if<stack.empty<>> returnfalse; else stack.pop<>; break; default:break; } } returnstack.empty<>;}queue<string>ExpressionType::DivideExpressionToItem<>{ queue<string>que; if<!IsWellForm<>>//括號(hào)是否匹配 { cout<<"Theoriginalexpressionisnotwell-form.Pleasecheckitandtryagain!"<<endl; returnque; }stringstr="";charch;intsize=Size<>;boolbNumber=false;for<inti=0;i<size;i++>{ ch=m_string.at<i>; switch<ch> { case'0': case'1': case'2': case'3': case'4': case'5': case'6': case'7': case'8': case'9': case'.': bNumber=true; break; case'<': case'>': case'+': case'-': case'*': case'/': bNumber=false; break; default:continue; }if<bNumber>{ str+=ch; if<i==size-1> que.push<str>;}else{ if<str.size<>!=0> que.push<str>; str=ch; que.push<str>; str="";}}returnque;}stack<string>ExpressionType::ChangeToSuffix<>//轉(zhuǎn)化為后綴表達(dá)式{ queue<string>que; stack<string>stack_A; stack<string>stack_B; que=DivideExpressionToItem<>;//取得中綴表達(dá)式隊(duì)列 if<que.empty<>> returnstack_B; stringstr; while<!que.empty<>> { str=que.front<>; que.pop<>; if<str=="<"> {stack_B.push<str>; } elseif<str==">"> { while<!stack_B.empty<>&&stack_B.top<>!="<"> { stack_A.push<stack_B.top<>>; stack_B.pop<>; } if<!stack_B.empty<>> stack_B.pop<>; } elseif<str=="+"||str=="-"> { if<stack_B.empty<>||stack_B.top<>=="<"> { stack_B.push<str>; } else { while<!stack_B.empty<>&&stack_B.top<>!="<"> { stack_A.push<stack_B.top<>>; stack_B.pop<>; } stack_B.push<str>; }} elseif<str=="*"||str=="/"> { if<stack_B.empty<>||stack_B.top<>=="+"||stack_B.top<>=="-"|| stack_B.top<>=="<"> { stack_B.push<str>; } else { stack_A.push<stack_B.top<>>; stack_B.pop<>; stack_B.push<str>; } } else stack_A.push<str>;} while<!stack_B.empty<>>//如果stack_B中還有操作符則將其彈出并推入stack_A { if<stack_B.top<>!="<"> stack_A.push<stack_B.top<>>; stack_B.pop<>; } while<!stack_A.empty<>> { stack_B.push<stack_A.top<>>; stack_A.pop<>; } returnstack_B;}doubleExpressionType::Calculate<>{ stack<string>stack_A=ChangeToSuffix<>;//取得后綴表達(dá)式 if<stack_A.empty<>> return0; stack<double>stack; stringstr; charch;doubledbl;while<!stack_A.empty<>>{ str=stack_A.top<>; stack_A.pop<>; ch=str.at<0>; switch<ch> { case'+': dbl=stack.top<>; stack.pop<>; dbl+=stack.top<>; stack.pop<>; stack.push<dbl>; break; case'-': dbl=stack.top<>; stack.pop<>; dbl=stack.top<>-dbl; stack.pop<>; stack.push<dbl>; break; case'*': dbl=stack.top<>; stack.pop<>; dbl*=stack.top<>; stack.pop<>; stack.push<dbl>; break; case'/': dbl=stack.top<>; stack.pop<>;if<dbl!=0.000>//除數(shù)不為0?。 dbl=stack.top<>/dbl; stack.pop<>; stack.push<dbl>;}break; default: //將字符串所代表的操作數(shù)轉(zhuǎn)換成雙精度浮點(diǎn)數(shù) //并壓入棧 char*p=<char*>str.begin<>; stack.push<atof<p>>; break; }}returnstack.top<>;}bt_algorithm.h//該頭文件主要完成二叉樹的定義和基本操作#include<iostream>#include<stack>#include<queue>#include<iomanip>#include"binarynode.h"usingnamespacestd;structElement//結(jié)點(diǎn)類型{ Element<>{}; Element<Binarynode<char>*t,intx,intlev>:ptr<t>,xOff<x>,level<lev>{} Binarynode<char>*ptr; intxOff,level;};Binarynode<char>*create<conststring&Pres,conststring&Ins>//構(gòu)造函數(shù){ Binarynode<char>*root; if<Pres.length<>>0> { root=newBinarynode<char><Pres[0]>; intindex=Ins.find<Pres[0]>; root->Left<>=create<Pres.substr<1,index>,Ins.substr<0,index>>; root->Right<>=create<Pres.substr<index+1>,Ins.substr<index+1>>; } elseroot=NULL; returnroot;}template<typenameT>voidPreOrder<Binarynode<T>*t>//先序遍歷{ if<t> { cout<<t->data<<""; PreOrder<t->Left<>>; PreOrder<t->Right<>>; }}template<typenameT>voidInOrder<Binarynode<T>*t>//中序遍歷{ if<t> { InOrder<t->Left<>>; cout<<t->data<<""; InOrder<t->Right<>>; }}template<typenameT>voidPostOrder<Binarynode<T>*t>//后序遍歷{ if<t> { PostOrder<t->Left<>>; PostOrder<t->Right<>>; cout<<t->data<<""; }}template<typenameT>voidLevelOrder<Binarynode<T>*t>{ queue<Binarynode<T>*>Q; Binarynode<T>*p; if<t> { Q.push<t>; while<!Q.empty<>> { p=Q.front<>; Q.pop<>; cout<<p->data<<""; if<p->Left<>!=NULL> Q.push<p->Left<>>; if<p->Right<>!=NULL> Q.push<p->Right<>>; } }}template<typenameT>voidLeafcount<Binarynode<T>*t,int*c>//計(jì)算樹葉子的個(gè)數(shù){ if<t> { if<t->Left<>==NULL&&t->Right<>==NULL> { *c=*c+1; } Leafcount<t->Left<>,c>; Leafcount<t->Right<>,c>; }}template<typenameT>intDepth<Binarynode<T>*t>//計(jì)算樹的深度{ intlh,rh; if<!t>return0; else { lh=Depth<t->Left<>>; rh=Depth<t->Right<>>; if<lh>rh> returnlh+1; else returnrh+1; } return1;}main//該文件為主程序,面向用戶#include<string>#include"bt_algorithm.h"usingnamespacestd;Binarynode<char>*create<conststring&Pres,conststring&Ins>;voidmain<>{ stringpre,in; intq,m,n,number,c=0;//q為模塊選擇;m為子模塊一輸入功能序號(hào);n為子模塊而輸入功能序號(hào) //number用來標(biāo)記是否退出子模塊;c為樹葉子個(gè)數(shù) ExpressionTypeexpr;stringexpression;//輸入的中綴表達(dá)式flag:cout<<"┌────────────────────────────────┐"<<endl;cout<<"│二叉樹的操作與應(yīng)用│"<<endl;cout<<"│姓名:翁恒叢學(xué)號(hào):6100410184班級(jí):計(jì)算機(jī)卓越│"<<endl;cout<<"││"<<endl;cout<<"│1.二叉樹基本操作2.表達(dá)式求值0.退出程序│"<<endl;cout<<"└────────────────────────────────┘"<<endl;cout<<"選擇主模塊:";cin>>q;switch<q> { case0: exit<0>; break;case1://模塊一 {cout<<"┏━━━━━━━━━━━━━━━━━━━━━━━━━┓"<<endl;cout<<"┃二叉樹基本操作┃"<<endl;cout<<"┃1.先序遍歷5.葉子結(jié)點(diǎn)數(shù)┃"<<endl;cout<<"┃2.中序遍歷6.樹的深度┃"<<endl;cout<<"┃3.后序遍歷0.退出子模塊一┃"<<endl; cout<<"┃4.層序遍歷┃"<<endl;cout<<"┗━━━━━━━━━━━━━━━━━━━━━━━━━┛"<<endl; co