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

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