.PAGE.中北大學數(shù)據(jù)結(jié)構(gòu)與算法課程設計說明書學院、系：軟件學院專業(yè)軟件工程班級1314010xxx學生姓名：學號：1314010xxx設計題目：樹的應用起迄日期:2015年1月12日-2015年1月29日指導教師:尹四清2015年1月29日一、需求分析1.設計內(nèi)容及設計要求A.設計內(nèi)容：〔1建立一棵樹；〔2將樹轉(zhuǎn)換成二叉樹；〔3實現(xiàn)二叉樹的前序、中序、后序的遞歸和非遞歸遍歷算法。B.設計要求：<1>符合課題要求,實現(xiàn)相應功能；<2>要求界面友好美觀,操作方便易行；<3>注意程序的實用性、安全性；2.本演示程序中,元素為單個字符,以空格表示空樹<即結(jié)點為空>,以回車符作為輸入結(jié)束標志,樹采用孩子兄弟表示法,二叉樹采用二叉鏈表表示法。在真實的運行過程中,由用戶手動輸入待創(chuàng)建樹的含有空格的先根次序序列,并按回車結(jié)束,程序會將其轉(zhuǎn)化為其對應的二叉樹,然后對二叉樹進行先序、中序、后序的遞歸及非遞歸遍歷以及層序遍歷,然后顯示轉(zhuǎn)化后二叉樹的高度和總結(jié)點數(shù),以驗證所創(chuàng)建的二叉樹是否正確,最后,銷毀創(chuàng)建的樹和二叉樹,程序結(jié)束。3.演示程序以用戶和計算機對話方式執(zhí)行,即在計算機終端〔屏幕上顯示"提示信息"之后,由用戶在鍵盤上輸入演示程序規(guī)定的運算命令,相應的輸入數(shù)據(jù)和運算結(jié)果顯示在其后。4.為了美觀,程序的輸出結(jié)果采用了分塊顯示的模式,由虛線及標題隔開,便于用戶檢查和驗證。5.測試數(shù)據(jù)如圖,給出一棵樹,若屏幕上顯示如下信息：->請按樹的先根次序輸入序列,如有空子樹,用空格填充,完成后輸入回車確認此時,你應當輸入：〔↙表示回車確認ABEFCDGHIJK↙提示：為方便確認輸入了幾個空格,用星號’*’表示輸入序列中的空格,則序列如下ABE*F**C*DGHI*J*K******↙〔不是真實的輸入序列,供計算需輸入空格個數(shù)時用這時,建好的樹的先根和后根次序序列如下：樹的先根序列ABEFCDGHIJK樹的后根序列EFBCIJKHGDA由樹和二叉樹的轉(zhuǎn)換關(guān)系知,二叉樹的先序和中序遍歷所得序列分別與樹的先根和后根遍歷所得序列相同,據(jù)此驗證轉(zhuǎn)化是否正確。二叉樹的先序和中序遍歷序列如下：二叉樹先序序列ABEFCDGHIJK二叉樹中序序列EFBCIJKHGDA概要設計為了實現(xiàn)上述程序功能,樹采用孩子兄弟表示法,二叉樹采用二叉鏈表表示法。為此,需要兩個抽象數(shù)據(jù)類型,樹和二叉樹的抽象數(shù)據(jù)類型。1.樹的抽象數(shù)據(jù)類型定義ADTTree{數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：若D為空集,則稱為空樹；若D僅含有一個數(shù)據(jù)元素,則R為空集,否則R={H},H是如下二元關(guān)系：<1>在D中存在唯一的稱為根的數(shù)據(jù)元素root,它在關(guān)系H下無前驅(qū)；<2>若D-{root}≠Φ,則存在D-{root}的一個劃分D1,D2,D3,

?,Dm<m>0>,對于任意j≠k<1≤j,k≤m>有Dj∩Dk=Φ,且對任意的i<1≤i≤m>,唯一存在數(shù)據(jù)元素xi∈Di有<root,xi>∈H;<3>對應于D-{root}的劃分,H-{<root,xi>,?,<root,xm>}有唯一的一個劃分H1,H2,?,Hm<m>0>,對任意j≠k<1≤j,k≤m>有Hj∩Hk=Φ,且對任意i<1≤i≤m>,Hi是Di上的二元關(guān)系,<Di,{Hi}>是一棵符合本定義的樹,稱為根root的子樹?；静僮鱌：InitTree<&T>;操作結(jié)果：構(gòu)造空樹T。DestroyTree<&T>;初始條件：樹T存在。操作結(jié)果：銷毀樹T。CreateTree<&T,definition>;初始條件：definition給出樹T的定義。操作結(jié)果：按definition構(gòu)造樹T。ClearTree<&T>;初始條件：樹T存在。操作結(jié)果：將樹T清為空樹。TreeEmpty<T>;初始條件：樹T存在。操作結(jié)果：若T為空樹,則返回TRUE,否則返回FALSE。TreeDepth<T>;初始條件：樹T存在。操作結(jié)果：返回Ｔ的深度。Root<T>;初始條件：樹T存在。操作結(jié)果：返回T的根。Value<T,cur_e>;初始條件：樹T存在,cur_e是T中某個結(jié)點。操作結(jié)果：返回cur_e的值。Assign<T,cur_e,value>;初始條件：樹T存在,cur_e是T中某個結(jié)點。操作結(jié)果：結(jié)點cur_e賦值為value。Parent<T,cur_e>;初始條件：樹T存在,cur_e是T中某個結(jié)點。操作結(jié)果：若cur_e是T的非根結(jié)點,則返回它的雙親,否則函數(shù)值為"空"。LeftChild<T,cur_e>;初始條件：樹T存在,cur_e是T中某個結(jié)點。操作結(jié)果：若cur_e是T的非葉子結(jié)點,則返回它的最左孩子,否則返回"空"。RightSibling<T,cur_e>;初始條件：樹T存在,cur_e是T中某個結(jié)點。操作結(jié)果：若cur_e有右兄弟,則返回它的右兄弟,否則返回"空"。InsertChild<&T,&p,I,c>;初始條件：樹Ｔ存在,ｐ指向Ｔ中某個結(jié)點,1≤i≤p指結(jié)點的度＋１,非空樹ｃ與Ｔ不相交。操作結(jié)果：插入c為Ｔ中ｐ指結(jié)點的第ｉ棵子樹。DeleteChild<&T,&p,i>;初始條件：樹T存在,p指向T中某個結(jié)點,1≤i≤p指結(jié)點的度。操作結(jié)果：刪除Ｔ中ｐ所指結(jié)點的第ｉ棵子樹。TraverseTree<T,visit<>>;初始條件：樹T存在,visit是對結(jié)點操作的應用函數(shù)。操作結(jié)果：按某種次序?qū)的每個結(jié)點調(diào)用函數(shù)visit<>一次且至多一次。一旦visit<>失敗,則操作失敗。}ADTTree2.二叉樹的抽象數(shù)據(jù)類型定義ADTBinaryTree{數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：若D=Φ,則R=Φ,稱BinaryTree為空二叉樹；若D≠Φ,則R={H},H是如下二元關(guān)系；〔1在D中存在惟一的稱為根的數(shù)據(jù)元素root,它在關(guān)系H下無前驅(qū)；〔2若D-{root}≠Φ,則存在D-{root}={D1,Dr},且D1∩Dr=Φ；〔3若D1≠Φ,則D1中存在惟一的元素x1,<root,x1>∈H,且存在D1上的關(guān)系H1?H；若Dr≠Φ,則Dr中存在惟一的元素xr,<root,xr>∈H,且存在上的關(guān)系Hr?H；H={<root,x1>,<root,xr>,H1,Hr}；〔4<D1,{H1}>是一棵符合本定義的二叉樹,稱為根的左子樹；<Dr,{Hr}>是一棵符合本定義的二叉樹,稱為根的右子樹?；静僮鳎篒nitBiTree<&T>操作結(jié)果：構(gòu)造空二叉樹T。DestroyBiTree<&T>初始條件：二叉樹T已存在。操作結(jié)果：銷毀二叉樹T。CreateBiTree<&T,definition>初始條件：definition給出二叉樹T的定義。操作結(jié)果：按definiton構(gòu)造二叉樹T。ClearBiTree<&T>初始條件：二叉樹T存在。操作結(jié)果：將二叉樹T清為空樹。BiTreeEmpty<T>初始條件：二叉樹T存在。操作結(jié)果：若T為空二叉樹,則返回TRUE,否則返回FALSE。BiTreeDepth<T>初始條件：二叉樹T存在。操作結(jié)果：返回T的深度。Root<T>初始條件：二叉樹T存在。操作結(jié)果：返回T的根。Value<T,e>初始條件：二叉樹T存在,e是T中某個結(jié)點。操作結(jié)果：返回e的值。Assign<T,&e,value>初始條件：二叉樹T存在,e是T中某個結(jié)點。操作結(jié)果：結(jié)點e賦值為value。Parent<T,e>初始條件：二叉樹T存在,e是T中某個結(jié)點。操作結(jié)果：若e是T的非根結(jié)點,則返回它的雙親,否則返回"空"。LeftChild<T,e>初始條件：二叉樹T存在,e是T中某個結(jié)點。操作結(jié)果：返回e的左孩子。若e無左孩子,則返回"空"。RightChild<T,e>初始條件：二叉樹T存在,e是T中某個結(jié)點。操作結(jié)果：返回e的右孩子。若e無右孩子,則返回"空"。LeftSibling<T,e>初始條件：二叉樹T存在,e是T中某個結(jié)點。操作結(jié)果：返回e的左兄弟。若e是T的左孩子或無左兄弟,則返回"空"。RightSibling<T,e>初始條件：二叉樹T存在,e是T中某個結(jié)點。操作結(jié)果：返回e的右兄弟。若e是T的右孩子或無右兄弟,則返回"空"。InsertChild<T,p,LR,c>初始條件：二叉樹T存在,p指向T中某個結(jié)點,LR為0或1,非空二叉樹c與T不相交且右子樹為空。操作結(jié)果：根據(jù)LR為0或1,插入c為T中p所指結(jié)點的左或右子樹。p所指結(jié)點的原有左或右子樹則成為c的右子樹。DeleteChild<T,p,LR>初始條件：二叉樹T存在,p指向T中某個結(jié)點,LR為0或1。操作結(jié)果：根據(jù)LR為0或1,刪除T中p所指結(jié)點的左或右子樹。PreOrderTraverse<T,visit<>>初始條件：二叉樹T存在,Visit是對結(jié)點操作的應用函數(shù)。操作結(jié)果：先序遍歷T,對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次。一旦visit<>失敗,則操作失敗。InOrderTraverse<T,visit<>>初始條件：二叉樹T存在,Visit是對結(jié)點操作的應用函數(shù)。操作結(jié)果：中序遍歷T,對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次。一旦visit<>失敗,則操作失敗。PostOrderTraverse<T,visit<>>初始條件：二叉樹T存在,Visit是對結(jié)點操作的應用函數(shù)。操作結(jié)果：后序遍歷T,對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次。一旦visit<>失敗,則操作失敗。LevelOrderTraverse<T,visit<>>初始條件：二叉樹T存在,Visit是對結(jié)點操作的應用函數(shù)。操作結(jié)果：層次遍歷T,對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次。一旦visit<>失敗,則操作失敗。}ADTBinaryTree本程序包括個模塊[1]主程序模塊先聲明一棵樹和一棵二叉樹,然后輸入樹的含空格先根次序序列,構(gòu)建一棵樹,然后將其轉(zhuǎn)化為二叉樹,并對二叉樹進行先序、中序、后序的遞歸和非遞歸遍歷以及層序遍歷,然后輸出二叉樹的高度和總結(jié)點數(shù),最后銷毀這兩棵樹。[2]建立樹模塊——按照樹的先根序列創(chuàng)建樹。[3]樹轉(zhuǎn)化二叉樹模塊——將樹轉(zhuǎn)化為二叉樹。[4]二叉樹的遍歷——二叉樹的先序、中序、后序的遞歸和非遞歸遍歷以及層序遍歷。[5]二叉樹的相關(guān)信息——二叉樹的高度和總結(jié)點數(shù)。[6]銷毀樹和二叉樹模塊——銷毀創(chuàng)建的樹和轉(zhuǎn)換出的二叉樹。[7]棧和隊列的模塊——供二叉樹先序、中序、后序的非遞歸算法調(diào)用各模塊之間關(guān)系：詳細設計元素類型、結(jié)點類型和指針類型樹的結(jié)點元素類型設置為字符型,這樣既可以接收字符也可以接受數(shù)字。typedefcharTElemType;//樹中結(jié)點元素類型//二叉樹的二叉鏈表存儲表示typedefstructBiNode{ TElemTypedata;//數(shù)據(jù)域,存儲結(jié)點名稱 structBiNode*lchild,*rchild;//孩子結(jié)點指針}BiNode,*BiTree;二叉樹的二叉鏈表表示法示意圖：//樹的孩子兄弟表示法typedefstructCSNode{TElemTypedata;//數(shù)據(jù)域,存儲結(jié)點名稱structCSNode*firstchild,*nextsibling;//孩子指針域和兄弟指針域}CSNode,*CSTree;樹的孩子兄弟表示法示意圖：構(gòu)造一般樹算法：按照樹的先根次序序列構(gòu)建一棵樹：對于這棵樹,按照需求分析第1頁的測試數(shù)據(jù),用戶應當輸入〔↙表示回車確認ABEFCDGHIJK↙正確輸入所需序列后,樹的建立完成。StatusCreateCSTree<CSTree&CT>{//按先根序列構(gòu)造樹 //按先根次序輸入樹中結(jié)點的值〔一個字符,空格字符表示空樹,構(gòu)造二叉鏈表表示樹T charch; ch=getchar<>; if<ch==''> CT=NULL; else{ if<!<CT=<CSNode*>malloc<sizeof<CSNode>>>>{ printf<"內(nèi)存分配失敗！\n">; exit<OVERFLOW>; }//if CT->data=ch;//生成根結(jié)點 CreateCSTree<CT->firstchild>;//構(gòu)建左子樹 CreateCSTree<CT->nextsibling>;//構(gòu)建右子樹 }//else returnOK;}//CreateCSTree轉(zhuǎn)換為二叉樹樹和二叉樹的轉(zhuǎn)換關(guān)鍵在于樹的二叉鏈表與其對應的二叉樹的二叉鏈表是相同的,只是對同一個二叉鏈表的解釋不同,二叉樹的數(shù)據(jù)域存放結(jié)點名稱,左指針域指向左孩子,右指針域指向右孩子；樹的數(shù)據(jù)域存放結(jié)點名稱,左指針域指向孩子結(jié)點,右指針域指向與該結(jié)點相鄰的一個兄弟結(jié)點。當兩者具有相同的存儲結(jié)構(gòu)時,便可以完成轉(zhuǎn)換,轉(zhuǎn)換過程的實質(zhì)是按照二叉樹的定義將二叉鏈表解釋為二叉樹的過程。StatusExchangeToBiTree<CSTree&CT,BiTree&T>{ //將一棵用二叉鏈表表示的樹遞歸地轉(zhuǎn)換為二叉樹 if<!CT>//樹CT為空時,二叉樹T為空 T=NULL; else{//若樹的對應結(jié)點不空,申請內(nèi)存空間 if<!<T=<BiNode*>malloc<sizeof<BiNode>>>>{ printf<"內(nèi)存分配失??！\n">; exit<OVERFLOW>; }//if//將樹的數(shù)據(jù)域復制到二叉樹對應的數(shù)據(jù)域 T->data=CT->data;//若樹的孩子域不為空,則用樹的孩子域創(chuàng)建二叉樹的左子樹 ExchangeToBiTree<CT->firstchild,T->lchild>;//若樹的兄弟域不為空,則用樹的兄弟域創(chuàng)建二叉樹的右子樹 ExchangeToBiTree<CT->nextsibling,T->rchild>; }//else}//ExchangeToBiTree二叉樹的遍歷二叉樹有先序、中序、后序、層序四種遍歷方式,而先序、中序、后序遍歷又有遞歸和非遞歸兩種算法,總共有7個遍歷算法。其中,先序、中序、后序非遞歸遍歷算法需要用到棧,層序遍歷需要使用隊列,隊列和棧的相關(guān)定義和算法請參考詳細設計P21。二叉樹先序、中序、后序遍歷的區(qū)別僅在于訪問根結(jié)點的時機不同,而層序遍歷則是逐層從左到右訪問每一個結(jié)點。先序遍歷二叉樹算法的框架是：若二叉樹為空,則空操作；否則訪問根結(jié)點<D>；先序遍歷左子樹<L>；先序遍歷右子樹<R>。中序遍歷二叉樹算法的框架是：若二叉樹為空,則空操作；否則中序遍歷左子樹<L>；訪問根結(jié)點<D>；中序遍歷右子樹<R>。后序遍歷二叉樹算法的框架是：若二叉樹為空,則空操作；否則后序遍歷左子樹<L>；后序遍歷右子樹<R>；訪問根結(jié)點<D>。雖然訪問根結(jié)點的時機不同,但是先左后右的規(guī)則并沒有改變。所有的遍歷函數(shù)都調(diào)用元素訪問函數(shù)Visit,他們的參數(shù)列表中均含有一個函數(shù)指針變量Status<*Visit><TElemType>,通過主函數(shù)向他們傳遞元素訪問函數(shù)Visit的函數(shù)名,就可以實現(xiàn)按元素訪問函數(shù)Visit設定格式輸出的目的。這樣的好處在于當輸出格式改變時,只需修改元素訪問函數(shù)Visit的輸出格式而無需更改7個遍歷函數(shù),做到一改全改。以下是所有遍歷算法的實現(xiàn)以及元素訪問函數(shù)Visit：//元素訪問函數(shù)VisitStatusPrintElement<TElemTypee>{//輸出元素e的值 printf<"%c",e>;//元素類型設定為字符型 returnOK;}//PrintElement//遞歸算法StatusPreOrderTraverse<BiTreeT,Status<*Visit><TElemType>>{//先序遍歷遞歸算法//采用二叉鏈表存儲結(jié)構(gòu),Visit是對數(shù)據(jù)元素操作的應用函數(shù) //先序遍歷二叉樹T的遞歸算法,對每個數(shù)據(jù)元素調(diào)用函數(shù)Visit if<T>{ if<Visit<T->data>>//訪問根結(jié)點 if<PreOrderTraverse<T->lchild,Visit>>//訪問左子樹 if<PreOrderTraverse<T->rchild,Visit>>//訪問右子樹returnOK; returnERROR; }//if elsereturnOK;}//PreOrderTraverseStatusInOrderTraverse<BiTreeT,Status<*Visit><TElemType>>{//中序遍歷遞歸算法//采用二叉鏈表存儲結(jié)構(gòu),Visit是對數(shù)據(jù)元素操作的應用函數(shù) //中序遍歷二叉樹T的遞歸算法,對每個數(shù)據(jù)元素調(diào)用函數(shù)Visit if<T>{ if<InOrderTraverse<T->lchild,Visit>>//訪問左子樹 if<Visit<T->data>>//訪問根結(jié)點 if<InOrderTraverse<T->rchild,Visit>>//訪問右子樹returnOK; returnERROR; }//if elsereturnOK;}//InOrderTraverseStatusPostOrderTraverse<BiTreeT,Status<*Visit><TElemType>>{//后序遍歷遞歸算法//采用二叉鏈表存儲結(jié)構(gòu),Visit是對數(shù)據(jù)元素操作的應用函數(shù) //后序遍歷二叉樹T的遞歸算法,對每個數(shù)據(jù)元素調(diào)用函數(shù)Visit if<T>{ if<PostOrderTraverse<T->lchild,Visit>>//訪問左子樹 if<PostOrderTraverse<T->rchild,Visit>>//訪問右子樹 if<Visit<T->data>>//訪問根結(jié)點returnOK; returnERROR; }//if elsereturnOK;}//PostOrderTraverse//非遞歸遍歷算法StatusPreOrderTraverse1<BiTreeT,Status<*Visit><TElemType>>{//先序遍歷非遞歸算法//采用二叉鏈表存儲結(jié)構(gòu),Visit是對數(shù)據(jù)元素操作的應用函數(shù) //先序遍歷二叉樹T的非遞歸算法,對每個數(shù)據(jù)元素調(diào)用函數(shù)Visit StackS; InitStack<S>;//初始化棧 BiTreep=T;//設置工作指針p并對其賦初值 while<p||!<StackEmpty<S>>>{ if<p>{ if<!Visit<p->data>>//訪問根結(jié)點 returnERROR; Push<S,p>;//根指針進棧 p=p->lchild;//遍歷左子樹 }//if else{ Pop<S,p>;//根指針退棧 p=p->rchild;//遍歷右子樹 }//else }//while returnOK;}//PreOrderTraverse1StatusInOrderTraverse1<BiTreeT,Status<*Visit><TElemType>>{//中序遍歷非遞歸算法//采用二叉鏈表存儲結(jié)構(gòu),Visit是對數(shù)據(jù)元素操作的應用函數(shù) //中序遍歷二叉樹T的非遞歸算法,對每個數(shù)據(jù)元素調(diào)用函數(shù)Visit StackS; InitStack<S>; BiTreep=T; while<p||!<StackEmpty<S>>>{ if<p>{ Push<S,p>;//根指針進棧 p=p->lchild;//遍歷左子樹 }//if else{ Pop<S,p>;//根指針退棧 if<!Visit<p->data>>//訪問根結(jié)點 returnERROR; p=p->rchild;//遍歷右子樹 }//else }//while returnOK;}//InOrderTraverse1StatusPostOrderTraverse1<BiTreeT,Status<*Visit><TElemType>>{//后序遍歷非遞歸算法//采用二叉鏈表存儲結(jié)構(gòu),Visit是對數(shù)據(jù)元素操作的應用函數(shù) //后序遍歷二叉樹T的非遞歸算法,對每個數(shù)據(jù)元素調(diào)用函數(shù)Visit BiTreep=T,q=NULL;//intn=0;Stacks;InitStack<s>;while<<p>||<!StackEmpty<s>>>{ while<p>{ Push<s,p>; p=p->lchild; }//while q=NULL; while<!StackEmpty<s>>{ GetTop<s,p>; if<<p->rchild==NULL>||<p->rchild==q>>{ if<!Visit<p->data>>//訪問根結(jié)點 returnERROR; if<p==T>returnERROR; q=p; Pop<s,p>; }//if else{ p=p->rchild; break; }//else }//while}//while returnOK;}//PostOrderTraverse1StatusLevelOrderTraverse1<BiTreeT,Status<*Visit><TElemType>>{//層序遍歷非遞歸算法//采用二叉鏈表存儲結(jié)構(gòu),Visit是對數(shù)據(jù)元素操作的應用函數(shù) //層序遍歷二叉樹T的算法,對每個數(shù)據(jù)元素調(diào)用函數(shù)Visit QueueQ; BiTreep=T; if<T>{//根結(jié)點入隊列 InitQueue<Q>;//初始化隊列 EnQueue<Q,T>; while<!QueueEmpty<Q>>{//隊列不空 DeQueue<Q,p>; if<!Visit<p->data>>//訪問根結(jié)點 returnERROR; if<p->lchild> EnQueue<Q,p->lchild>;//左孩子入隊列 if<p->rchild> EnQueue<Q,p->rchild>;//右孩子入隊列 }//while printf<"\n">;}//if returnOK;}//LevelOrderTraverse15.二叉樹的信息intBiTreeDepth<BiTreeT>{//遞歸求二叉樹高度 //若二叉樹T存在,返回T的深度〔高度,否則返回0 intThigh,leftThigh,rightThigh;//分別表示二叉樹高度,左子樹高度,右子樹高度 if<!T>return0;//樹高為0 else{ leftThigh=BiTreeDepth<T->lchild>;//求左子樹高度 rightThigh=BiTreeDepth<T->rchild>;//求右子樹高度 if<leftThigh>=rightThigh>//求二叉樹高度 Thigh=leftThigh+1; else Thigh=rightThigh+1; }//else returnThigh;}//BiTreeDepthintNodeSubNum<BiTreeT>{//統(tǒng)計二叉樹的結(jié)點個數(shù) if<!T>return0;//二叉樹為空樹,沒有結(jié)點 elsereturn<NodeSubNum<T->lchild>+NodeSubNum<T->rchild>+1>;}//NodeSubNum6.銷毀樹voidDestoryCSTree<CSTree&CT>{ //按照樹的定義遞歸地銷毀樹 if<CT>{//非空樹 if<CT->firstchild>//孩子子樹非空 DestoryCSTree<CT->firstchild>; if<CT->nextsibling>//兄弟子樹非空 DestoryCSTree<CT->nextsibling>; free<CT>;//釋放根結(jié)點 CT=NULL;//空指針賦0 }//if}//DestoryTreevoidDestoryBiTree<BiTree&T>{ //按照二叉樹定義遞歸地銷毀二叉樹 if<T>{//非空樹 if<T->lchild>//左子樹非空,銷毀左子樹 DestoryBiTree<T->lchild>; if<T->rchild>//右子樹非空,銷毀右子樹 DestoryBiTree<T->rchild>; free<T>;//釋放根結(jié)點 T=NULL;//空指針賦0 }//if}//DestoryTreevoidDestoryTree<CSTree&CT,BiTree&T>{ //銷毀樹和二叉樹 DestoryCSTree<CT>; DestoryBiTree<T>; printf<"->生成的樹和二叉樹已被銷毀！">;}//DestoryTree棧和隊列的定義及算法//棧的順序存儲表示typedefBiTreeSElemType;//棧的元素為二叉樹指針類型typedefstruct{//棧的順序存儲表示 SElemType*base;//棧底指針,在棧構(gòu)造之前和銷毀之后,base的值為NULL SElemType*top;//棧頂指針 intstacksize;//當前已分配的存儲空間,以元素為單位}Stack;//隊列的鏈式存儲表示typedefBiTreeQElemType;//隊列元素為二叉樹指針類型typedefstructQNode{//鏈隊列的C語言表示 QElemTypedata;//數(shù)據(jù)域 structQNode*next;//指針域}QNode,*QueuePtr;typedefstruct{ QueuePtrfront;//隊頭指針 QueuePtrrear;//隊尾指針}Queue;//棧的相關(guān)函數(shù)<供非遞歸后序遍歷使用>StatusInitStack<Stack&S>{//構(gòu)造一個空的順序棧 if<!<S.base=<SElemType*>malloc<STACK_INIT_SIZE*sizeof<SElemType>>>>{ printf<"內(nèi)存分配失??！\n">; exit<OVERFLOW>; } S.top=S.base; S.stacksize=STACK_INIT_SIZE; returnOK;}//InitStackStatusDestoryStack<Stack&S>{//釋放順序棧S所占內(nèi)存空間 free<S.base>; S.base=NULL; S.top=NULL; returnOK;}//DestoryStackStatusStackEmpty<StackS>{//判斷順序棧S是否為空棧,是返回1,否返回0 returnS.top==S.base;}//StackIsEmptyStatusPush<Stack&S,SElemTypee>{//入棧 if<S.top-S.base>=S.stacksize>{ if<!<S.base=<SElemType*>realloc<S.base,<STACK_INIT_SIZE+STACKINCREMENT>*sizeof<SElemType>>>>{ printf<"內(nèi)存分配失?。n">; exit<OVERFLOW>; } S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e;}//PushStatusPop<Stack&S,SElemType&e>{//出棧 if<StackEmpty<S>> returnERROR; e=*--S.top; returnOK;}//PopStatusGetTop<StackS,SElemType&e>{ //若棧不空,用e返回順序棧S棧頂元素的值,并返回OK,否則返回ERRROR if<StackEmpty<S>> returnERROR; e=*<S.top-1>; returnOK;}//GetTop//隊列的相關(guān)函數(shù)<供非遞歸層序遍歷使用>QueuePtrMallocQNode<>{//為鏈隊列結(jié)點申請內(nèi)存的函數(shù) QueuePtrp;//工作指針p if<!<p=<QueuePtr>malloc<sizeof<QNode>>>>{//申請結(jié)點的內(nèi)存空間,若失敗則提示并退出程序 printf<"內(nèi)存分配失敗,程序即將退出！\n">; exit<OVERFLOW>; } returnp;}//MallocQNodeStatusInitQueue<Queue&Q>//初始化鏈隊列{//構(gòu)建一個空隊列Q Q.front=Q.rear=MallocQNode<>;//申請頭結(jié)點的內(nèi)存空間,并使隊頭和隊尾指針同時指向它 Q.front->next=NULL; Q.front->data=0;//將隊長設為0 returnOK;}//InitQueueStatusDestoryQueue<Queue&Q>{//銷毀隊列Q while<Q.front>{//從頭結(jié)點開始向后逐個釋放結(jié)點內(nèi)存空間 Q.rear=Q.front->next; free<Q.front>; Q.front=Q.rear; }//while printf<"鏈隊列已成功銷毀！\n">; returnOK;}//DestoryQueueStatusQueueEmpty<QueueQ>{//若Q為空隊列,則返回OK;否則返回ERROR if<Q.rear==Q.front>//隊列為空的標志 returnOK; returnERROR;}//QueueEmptyStatusEnQueue<Queue&Q,QElemTypee>{//插入元素e為Q的新的隊尾元素 QueuePtrp=MallocQNode<>; p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; Q.front->data++;//隊長+1 returnOK;}//EnQueueStatusDeQueue<Queue&Q,QElemType&e>{//若隊列不空,則刪除Q的隊頭元素,用e返回其值,并返回OK,否則返回ERROR if<QueueEmpty<Q>> returnERROR; QueuePtrp=Q.front->next; e=p->data; Q.front->next=p->next; if<Q.rear==p> Q.rear=Q.front; free<p>; Q.front->data--;//隊長-1 returnOK;}//DeQueue主函數(shù)intmain<intargc,char*argv[]>{ printf<"樹的應用\n">; BiTreeT=NULL;//聲明一棵二叉樹 CSTreeCT=NULL;//聲明一棵普通樹 printf<"樹的建立\n">; printf<"->請按樹的先根次序輸入序列,如有空子樹,用空格填充,完成后輸入回車確認\n">; CreateCSTree<CT>; printf<"樹的轉(zhuǎn)換\n">; printf<"->正在將輸入的樹轉(zhuǎn)換為其對應的二叉樹...\n">; ExchangeToBiTree<CT,T>; printf<"->轉(zhuǎn)換操作執(zhí)行完畢！\n">; printf<"\n二叉樹的遍歷">; printf<"\n\n先序遍歷遞歸算法結(jié)果：">;PreOrderTraverse<T,PrintElement>; printf<"\n\n中序遍歷遞歸算法結(jié)果：">;InOrderTraverse<T,PrintElement>; printf<"\n\n后序遍歷遞歸算法結(jié)果：">;PostOrderTraverse<T,PrintElement>; printf<"\n\n先序遍歷非遞歸算法結(jié)果：">;PreOrderTraverse1<T,PrintElement>; printf<"\n\n中序遍歷非遞歸算法結(jié)果：">;InOrderTraverse1<T,PrintElement>; printf<"\n\n后序遍歷非遞歸算法結(jié)果：">;PostOrderTraverse1<T,PrintElement>; printf<"\n\n層序遍歷非遞歸算法結(jié)果：">;LevelOrderTraverse1<T,PrintElement>; printf<"\n二叉樹的信息">; printf<"\n該二叉樹的高度：%d",BiTreeDepth<T>>; printf<"\n二叉樹總結(jié)點數(shù)：%d",NodeSubNum<T>>; printf<"\n\n樹的銷毀">; DestoryTree<CT,T>; printf<"\n->算法演示結(jié)束！">; system<"pause">