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

1、實(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

2、操作系統(tǒng)或 Windows 操作系統(tǒng)Turbo C 程序集成環(huán)境或 Visual C+ 程序集成環(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ù)，所以必須將原始的中

3、綴表達(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 放入棧中，最后是操作符“-”，所以再?gòu)棾鰀和c 進(jìn)行d-c 運(yùn)算，并將其結(jié)果再次放入棧中，此時(shí)表達(dá)式結(jié)束，則棧中

4、的元素值就是該表達(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ì)尾其算法思想是

5、：從左往右按一個(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 完成。4、 轉(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è)stri

6、ng 變量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)取出stac

7、k_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ù)和

8、操作符，如下圖所示： 注意到最后返回的是stack_B 而不是stack_A，因?yàn)榭紤]到為了后面的計(jì)算方便，所以將其倒序保存在stack_B 中（最后一個(gè)while循環(huán)）。5、 后綴表達(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è)部分：1、 設(shè)計(jì)算

9、術(shù)表達(dá)式樹的存儲(chǔ)結(jié)構(gòu)；實(shí)驗(yàn)中采用的是二叉樹的的鏈接存儲(chǔ)。結(jié)點(diǎn)格式如下：其嚴(yán)格類的定義如下： template <typename T>class Binarynode /二叉樹的結(jié)點(diǎn)類public:Binarynode():left(NULL),right(NULL) /默認(rèn)構(gòu)造函數(shù)Binarynode(const T& item,Binarynode<T> *lptr=NULL,Binarynode<T> *rptr=NULL):data(item),left(lptr),right(rptr) /初始化T data; /結(jié)點(diǎn)數(shù)據(jù)Binarynod

10、e<T> *&Left() return left; /取leftBinarynode<T> *&Right() return right; /取rightprotected:Binarynode<T> *left,*right;2、 給出二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)算法和樹的深度算法描述；葉子結(jié)點(diǎn)個(gè)數(shù)算法：template<typename T>void Leafcount(Binarynode<T>*t,int *c) /計(jì)算樹葉子的個(gè)數(shù) /t為構(gòu)建的樹，c用來返回葉子節(jié)點(diǎn)個(gè)數(shù)if (t) /樹不為空if (t->L

11、eft()=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)樹的深度算法： int Depth(Binarynode<T>*t) /計(jì)算樹的深度 int lh,rh; /定義左右子樹的深度 if (!t) return 0; /樹為空返回0 else lh=Depth(t->Left(); /遞歸調(diào)用，求左子樹深度rh=Depth(t->Right();

12、 /遞歸調(diào)用，求右子樹深度if (lh>rh) /判斷左右子樹哪個(gè)更大，更大的深度加1返回其值 return lh+1;elsereturn rh+1; return 1;3、 相應(yīng)的程序要給出足夠的注釋部分；參見九、附錄，由于在報(bào)告中分析的算法，在附錄源程序中省略部分注釋，以免繁雜。4、 給出程序的測(cè)試結(jié)果驗(yàn)證各項(xiàng)程序功能如下：（1） 進(jìn)入模塊選擇進(jìn)入模塊一：進(jìn)入模塊二：（2） 四種遍歷以先序序列為A B D E C F ,中序序列D B E A F C為例：（3） 求樹的葉子結(jié)點(diǎn)數(shù)和樹的深度（4） 求表達(dá)式的值1、輸入數(shù)據(jù)：2.2*（3.1+1.20）-7.5/3 正確結(jié)果：6.96

13、2、輸入數(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ǔ)，它要利用指針來

14、指向其左右孩子。如果要查找某一結(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)行語(yǔ)法判錯(cuò)的功能。 IsWellForm()函數(shù)。判斷原始中綴表達(dá)式的括號(hào)是否匹配，可以利用棧簡(jiǎn)單實(shí)現(xiàn)，即遇到“(”進(jìn)棧，遇到“)”就從棧中彈出一

15、個(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è)文件，頭文件bina

16、rynode.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è)文件。1、 binarynode.h/該頭文件主要給出二叉樹結(jié)點(diǎn)的定義和表達(dá)式二叉樹類及其相關(guān)的計(jì)算函數(shù)#ifdef WIN32#pragma warning(disable:4786)#endif#include <string>#

17、include <stack>#include <queue>using namespace std;template <typename T>class Binarynode /二叉樹的結(jié)點(diǎn)類public:Binarynode():left(NULL),right(NULL) /默認(rèn)構(gòu)造函數(shù)Binarynode(const T& item,Binarynode<T> *lptr=NULL,Binarynode<T> *rptr=NULL):data(item),left(lptr),right(rptr) /初始化二叉樹T

18、data; /結(jié)點(diǎn)數(shù)據(jù)Binarynode<T> *&Left() return left; /取leftBinarynode<T> *&Right() return right; /取rightprotected:Binarynode<T> *left,*right;class ExpressionType /表達(dá)式二叉樹類public:ExpressionType();ExpressionType(string m_string);void operator =(string m_string);/將一個(gè)字符串表達(dá)式賦予m_stringd

19、ouble Calculate();/計(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è)棧中bool IsWellForm(); /判斷原始表達(dá)式中的括號(hào)是否匹配，如果匹配返回true，否則返回false。int Size(); /返回原

20、始表達(dá)式所包含的字節(jié)數(shù)。private:string m_string; /存儲(chǔ)表示原始中綴表達(dá)式的字符串。;ExpressionType:ExpressionType() /構(gòu)造函數(shù)m_string = ""ExpressionType:ExpressionType(string m_string)this->m_string = m_string;void ExpressionType:operator =(string m_string)/賦值this->m_string = m_string;int ExpressionType:Size()/中綴表達(dá)式

21、包含字節(jié)數(shù)return m_string.size();bool ExpressionType:IsWellForm()/判斷表達(dá)式正確與否stack<char> stack;int size = Size();char ch;for(int i = 0; i < size; i+)ch = m_string.at(i);switch(ch)case '(':stack.push(ch);break;case ')':if(stack.empty()return false;elsestack.pop();break;default:break

22、;return stack.empty();queue<string> ExpressionType:DivideExpressionToItem()queue<string> que;if(!IsWellForm()/ 括號(hào)是否匹配cout<<"The original expression is not well-form. Please check it and try again!"<<endl;return que;string str = ""char ch;int size = Size();

23、bool bNumber = false;for(int i = 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 '

24、(':case ')':case '+':case '-':case '*':case '/':bNumber = false;break;default:continue;if(bNumber)str += ch;if(i=size-1)que.push(str);elseif(str.size() != 0)que.push(str);str = ch;que.push(str);str = ""return que;stack<string> ExpressionTyp

25、e:ChangeToSuffix()/轉(zhuǎn)化為后綴表達(dá)式queue<string> que;stack<string> stack_A;stack<string> stack_B;que = DivideExpressionToItem(); / 取得中綴表達(dá)式隊(duì)列if(que.empty()return stack_B;string str;while(!que.empty()str = que.front();que.pop();if(str = "(")stack_B.push(str);else if(str = ")&q

26、uot;)while(!stack_B.empty() && stack_B.top()!= "(")stack_A.push(stack_B.top();stack_B.pop();if(!stack_B.empty()stack_B.pop();else if(str = "+" | str = "-")if(stack_B.empty() | stack_B.top() = "(")stack_B.push(str);elsewhile(!stack_B.empty() &&

27、stack_B.top() != "(")stack_A.push(stack_B.top();stack_B.pop();stack_B.push(str);else if(str = "*" | str = "/")if(stack_B.empty() | stack_B.top() = "+" | stack_B.top() = "-" |stack_B.top() = "(")stack_B.push(str);elsestack_A.push(stack_B.top

28、();stack_B.pop();stack_B.push(str);elsestack_A.push(str);while(!stack_B.empty() / 如果stack_B中還有操作符則將其彈出并推入stack_Aif(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();return stack_B;double ExpressionType:Calculate()st

29、ack<string> stack_A = ChangeToSuffix();/ 取得后綴表達(dá)式if(stack_A.empty()return 0;stack<double> stack;string str;char ch;double dbl;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();stac

30、k.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 =

31、 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;return stack.top();2、 bt_algorithm.h/該頭文件主要完成二叉樹的定義和基本操作#include <iostream>#include <stack>#include <queue>#include <iomanip>#include

32、 "binarynode.h"using namespace std;struct Element /結(jié)點(diǎn)類型Element();Element(Binarynode<char>*t,int x,int lev):ptr(t),xOff(x),level(lev)Binarynode <char> *ptr;int xOff,level;Binarynode<char>*create(const string &Pres,const string& Ins) /構(gòu)造函數(shù)Binarynode<char> *roo

33、t;if(Pres.length()>0)root=new Binarynode<char>(Pres0);int index=Ins.find(Pres0);root->Left()=create(Pres.substr(1,index),Ins.substr(0,index);root->Right()=create(Pres.substr(index+1),Ins.substr(index+1);else root=NULL;return root;template<typename T>void PreOrder(Binarynode<T

34、>*t) /先序遍歷if (t)cout<<t->data<<" "PreOrder(t->Left();PreOrder(t->Right(); template<typename T>void InOrder(Binarynode<T>*t) /中序遍歷if (t)InOrder(t->Left();cout<<t->data<<" "InOrder(t->Right();template<typename T>void Po

35、stOrder(Binarynode<T>*t) /后序遍歷if (t)PostOrder(t->Left();PostOrder(t->Right();cout<<t->data<<" "template<typename T>void LevelOrder(Binarynode<T>*t)queue<Binarynode<T>*>Q;Binarynode<T> *p;if (t)Q.push(t);while(!Q.empty()p=Q.front();Q.

36、pop();cout<<p->data<<""if(p->Left()!=NULL)Q.push(p->Left();if(p->Right()!=NULL)Q.push(p->Right();template<typename T>void Leafcount(Binarynode<T>*t,int *c) /計(jì)算樹葉子的個(gè)數(shù)if (t)if (t->Left()=NULL&&t->Right()=NULL)*c=*c+1;Leafcount(t->Left()

37、,c);Leafcount(t->Right(),c);template<typename T>int Depth(Binarynode<T>*t) /計(jì)算樹的深度int lh,rh;if (!t) return 0;elselh=Depth(t->Left();rh=Depth(t->Right();if (lh>rh) return lh+1;elsereturn rh+1;return 1;3、 main/該文件為主程序,面向用戶#include <string>#include "bt_algorithm.h&quo

38、t;using namespace std;Binarynode<char> *create(const string &Pres,const string& Ins);void main()string pre,in;int q,m,n,number,c=0; /q為模塊選擇;m為子模塊一輸入功能序號(hào);n為子模塊而輸入功能序號(hào) /number用來標(biāo)記是否退出子模塊;c為樹葉子個(gè)數(shù) ExpressionType expr; string expression; /輸入的中綴表達(dá)式flag:cout<<" "<<endl;c

39、out<<" 二叉樹的操作與應(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)case 0:exit(0);break; case 1: /模塊一 cout<<" "<<endl;cout<<" 二叉樹基本操作 "<<endl;cout<<" 1.先序遍歷 5.葉子結(jié)點(diǎn)數(shù) "<<endl;cout<<" 2.中序遍歷 6.樹的深度 "<<endl;cout<<" 3.后序遍歷