數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)說明書樹的應(yīng)用樹和二叉樹的轉(zhuǎn)換

1、中北大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)說 明 書學(xué)院、系：軟件學(xué)院專業(yè)：軟件工程班級(jí)：1314010xxx學(xué)生姓名：學(xué) 號(hào)： 1314010xxx設(shè)計(jì)題目：樹的應(yīng)用起迄日期 :2015 年 1 月 12 日- 2015年1月29日指導(dǎo)教師 :尹四清.2015 年1月29 日一、需求分析1. 設(shè)計(jì)內(nèi)容及設(shè)計(jì)要求A. 設(shè)計(jì)內(nèi)容：（ 1）建立一棵樹；（ 2）將樹轉(zhuǎn)換成二叉樹；（ 3）實(shí)現(xiàn)二叉樹的前序、中序、后序的遞歸和非遞歸遍歷算法。B. 設(shè)計(jì)要求：(1) 符合課題要求，實(shí)現(xiàn)相應(yīng)功能；(2) 要求界面友好美觀，操作方便易行；(3) 注意程序的實(shí)用性、安全性；2. 本演示程序中，元素為單個(gè)字符，以空格表示空樹

2、 ( 即結(jié)點(diǎn)為空 ) ，以回車符作為輸入結(jié)束標(biāo)志，樹采用孩子兄弟表示法，二叉樹采用二叉鏈表表示法。在真實(shí)的運(yùn)行過程中，由用戶手動(dòng)輸入待創(chuàng)建樹的含有空格的先根次序序列， 并按回車結(jié)束， 程序會(huì)將其轉(zhuǎn)化為其對(duì)應(yīng)的二叉樹，然后對(duì)二叉樹進(jìn)行先序、中序、后序的遞歸及非遞歸遍歷以及層序遍歷，然后顯示轉(zhuǎn)化后二叉樹的高度和總結(jié)點(diǎn)數(shù)，以驗(yàn)證所創(chuàng)建的二叉樹是否正確，最后，銷毀創(chuàng)建的樹和二叉樹，程序結(jié)束。3. 演示程序以用戶和計(jì)算機(jī)對(duì)話方式執(zhí)行，即在計(jì)算機(jī)終端（屏幕）上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序規(guī)定的運(yùn)算命令，相應(yīng)的輸入數(shù)據(jù)和運(yùn)算結(jié)果顯示在其后。4. 為了美觀，程序的輸出結(jié)果采用了分塊顯示的模

3、式，由虛線及標(biāo)題隔開，便于用戶檢查和驗(yàn)證。5. 測(cè)試數(shù)據(jù)如圖，給出一棵樹，若屏幕上顯示如下信息：->請(qǐng)按樹的先根次序輸入序列，如有空子樹，用空格填充，完成后輸入回車確認(rèn)此時(shí)，你應(yīng)當(dāng)輸入：（表示回車確認(rèn)）ABEF CDGHIJK提示：為方便確認(rèn)輸入了幾個(gè)空格，用星號(hào)* 表示輸入序列中的空格，則序列如下ABE*F*C*DGHI*J*K*（不是真實(shí)的輸入序列，供計(jì)算需輸入空格個(gè)數(shù)時(shí)用）這時(shí)，建好的樹的先根和后根次序序列如下：.樹的先根序列ABEFCDGHIJK樹的后根序列EFBCIJKHGDA由樹和二叉樹的轉(zhuǎn)換關(guān)系知，二叉樹的先序和中序遍歷所得序列分別與樹的先根和后根遍歷所得序列相同，據(jù)此驗(yàn)證

4、轉(zhuǎn)化是否正確。二叉樹的先序和中序遍歷序列如下：二叉樹先序序列ABEFCDGHIJK二叉樹中序序列EFBCIJKHGDA二、概要設(shè)計(jì)為了實(shí)現(xiàn)上述程序功能，樹采用孩子兄弟表示法，二叉樹采用二叉鏈表表示法。為此，需要兩個(gè)抽象數(shù)據(jù)類型，樹和二叉樹的抽象數(shù)據(jù)類型。1. 樹的抽象數(shù)據(jù)類型定義ADT Tree數(shù)據(jù)對(duì)象D： D 是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：若 D為空集，則稱為空樹；若 D僅含有一個(gè)數(shù)據(jù)元素，則R為空集，否則R=H ， H是如下二元關(guān)系：(1)在 D 中存在唯一的稱為根的數(shù)據(jù)元素root ，它在關(guān)系 H 下無前驅(qū)；(2)若 D-root ，則存在 D-root 的一個(gè)劃分 D1,

5、D2,D3, ,Dm(m>0)，對(duì)于任意 j k(1 j,k m)有 Dj Dk= , 且對(duì)任意的 i(1 i m)，唯一存在數(shù)據(jù)元素xi Di 有 <root,xi> H;(3)對(duì)應(yīng)于 D-root的劃分， H-<root,xi>, ,<root,xm> 有唯一的一個(gè)劃分H1， H2, , ,Hm(m>0)，對(duì)任意 j k(1 j,k m)有 Hj Hk=，且對(duì)任意 i(1 i m),Hi 是 Di 上的二元關(guān)系， (Di,Hi)是一棵符合本定義的樹，稱為根 root 的子樹。基本操作P：InitTree(&T);操作結(jié)果：構(gòu)造空樹T。

6、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);初始

7、條件：樹T 存在， cur_e 是 T 中某個(gè)結(jié)點(diǎn)。操作結(jié)果：返回cur_e 的值。Assign(T,cur_e,value);初始條件：樹T 存在， cur_e 是 T 中某個(gè)結(jié)點(diǎn)。操作結(jié)果：結(jié)點(diǎn)cur_e 賦值為 value 。Parent(T,cur_e);初始條件：樹T 存在， cur_e 是 T 中某個(gè)結(jié)點(diǎn)。操作結(jié)果：若cur_e 是 T 的非根結(jié)點(diǎn)，則返回它的雙親，否則函數(shù)值為“空”。LeftChild(T,cur_e);初始條件：樹T 存在， cur_e 是 T 中某個(gè)結(jié)點(diǎn)。操作結(jié)果：若cur_e 是 T 的非葉子結(jié)點(diǎn)，則返回它的最左孩子，否則返回“空”。RightSibling

8、(T,cur_e);初始條件：樹T 存在， cur_e 是 T 中某個(gè)結(jié)點(diǎn)。操作結(jié)果：若cur_e 有右兄弟，則返回它的右兄弟，否則返回“空”。InsertChild(&T,&p,I,c);初始條件：樹存在，指向中某個(gè)結(jié)點(diǎn)，1 i p 指結(jié)點(diǎn)的度，非空樹與.不相交。操作結(jié)果：插入c 為中指結(jié)點(diǎn)的第棵子樹。DeleteChild(&T,&p,i);初始條件：樹T 存在， p 指向 T 中某個(gè)結(jié)點(diǎn)， 1 i p 指結(jié)點(diǎn)的度。操作結(jié)果：刪除中所指結(jié)點(diǎn)的第棵子樹。TraverseTree(T,visit();初始條件：樹T 存在， visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。操作

9、結(jié)果：按某種次序?qū) 的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit() 一次且至多一次。 一旦 visit()失敗，則操作失敗。ADTTree2. 二叉樹的抽象數(shù)據(jù)類型定義ADT BinaryTree數(shù)據(jù)對(duì)象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，且 D1Dr = ；（ 3）若 D1，則 D1 中存在惟一的元素x1，<root,x1> H，且存在 D1

10、 上的關(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)是一棵符合本定義的二叉樹，稱為根的右子樹。基本操作：InitBiTree( &T )操作結(jié)果：構(gòu)造空二叉樹T。DestroyBiTree( &T )初始條件：二叉樹T 已存在。操作結(jié)果：銷毀二叉樹T。CreateBiTree( &T, definition ).初始條件： definit

11、ion給出二叉樹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 中某個(gè)結(jié)點(diǎn)。操作結(jié)果：返回e 的值。Assign( T, &e, value )

12、初始條件：二叉樹T 存在， e 是 T 中某個(gè)結(jié)點(diǎn)。操作結(jié)果：結(jié)點(diǎn)e 賦值為 value 。Parent( T, e )初始條件：二叉樹T 存在， e 是 T 中某個(gè)結(jié)點(diǎn)。操作結(jié)果：若e 是 T 的非根結(jié)點(diǎn)，則返回它的雙親，否則返回“空”。LeftChild( T, e )初始條件：二叉樹T 存在， e 是 T 中某個(gè)結(jié)點(diǎn)。操作結(jié)果：返回e 的左孩子。若e 無左孩子，則返回“空”。RightChild( T, e )初始條件：二叉樹T 存在， e 是 T 中某個(gè)結(jié)點(diǎn)。操作結(jié)果：返回e 的右孩子。若e 無右孩子，則返回“空”。LeftSibling( T, e ).初始條件：二叉樹T 存在， e

13、 是 T 中某個(gè)結(jié)點(diǎn)。操作結(jié)果：返回e 的左兄弟。若e 是 T 的左孩子或無左兄弟，則返回“空”。RightSibling( T, e )初始條件：二叉樹T 存在， e 是 T 中某個(gè)結(jié)點(diǎn)。操作結(jié)果：返回e 的右兄弟。若e 是 T 的右孩子或無右兄弟，則返回“空”。InsertChild( T, p, LR, c )初始條件：二叉樹T 存在， p 指向 T 中某個(gè)結(jié)點(diǎn)，LR 為 0 或 1，非空二叉樹c 與 T不相交且右子樹為空。操作結(jié)果：根據(jù)LR 為 0 或 1，插入 c 為 T 中 p 所指結(jié)點(diǎn)的左或右子樹。p 所指結(jié)點(diǎn)的原有左或右子樹則成為c 的右子樹。DeleteChild( T, p

14、, LR )初始條件：二叉樹T 存在， p 指向 T 中某個(gè)結(jié)點(diǎn)， LR 為 0 或 1。操作結(jié)果：根據(jù)LR 為 0 或 1，刪除 T 中 p 所指結(jié)點(diǎn)的左或右子樹。PreOrderTraverse( T, visit() )初始條件：二叉樹T 存在， Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。操作結(jié)果：先序遍歷T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗，則操作失敗。InOrderTraverse( T, visit() )初始條件：二叉樹T 存在， Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。操作結(jié)果：中序遍歷T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗，則操

15、作失敗。PostOrderTraverse( T, visit() )初始條件：二叉樹T 存在， Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。操作結(jié)果：后序遍歷T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗，則操作失敗。LevelOrderTraverse( T, visit() )初始條件：二叉樹T 存在， Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。操作結(jié)果：層次遍歷T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗，則操作失敗。ADT BinaryTree.3. 本程序包括個(gè)模塊【1】主程序模塊先聲明一棵樹和一棵二叉樹，然后輸入樹的含空格先根次序序列，構(gòu)建一棵樹，然后

16、將其轉(zhuǎn)化為二叉樹，并對(duì)二叉樹進(jìn)行先序、中序、后序的遞歸和非遞歸遍歷以及層序遍歷，然后輸出二叉樹的高度和總結(jié)點(diǎn)數(shù)，最后銷毀這兩棵樹?！?】建立樹模塊按照樹的先根序列創(chuàng)建樹?！?】樹轉(zhuǎn)化二叉樹模塊將樹轉(zhuǎn)化為二叉樹?！?】二叉樹的遍歷二叉樹的先序、中序、后序的遞歸和非遞歸遍歷以及層序遍歷。【5】二叉樹的相關(guān)信息二叉樹的高度和總結(jié)點(diǎn)數(shù)?！?】銷毀樹和二叉樹模塊銷毀創(chuàng)建的樹和轉(zhuǎn)換出的二叉樹?！?】棧和隊(duì)列的模塊供二叉樹先序、中序、后序的非遞歸算法調(diào)用各模塊之間關(guān)系：三、詳細(xì)設(shè)計(jì)1. 元素類型、結(jié)點(diǎn)類型和指針類型.樹的結(jié)點(diǎn)元素類型設(shè)置為字符型，這樣既可以接收字符也可以接受數(shù)字。typedef char T

17、ElemType;/樹中結(jié)點(diǎn)元素類型/-二叉樹的二叉鏈表存儲(chǔ)表示-typedef struct BiNodeTElemType data; /數(shù)據(jù)域 , 存儲(chǔ)結(jié)點(diǎn)名稱struct BiNode *lchild,*rchild;/孩子結(jié)點(diǎn)指針BiNode,*BiTree;二叉樹的二叉鏈表表示法示意圖：/-樹的孩子兄弟表示法-typedef struct CSNodeTElemType data; /數(shù)據(jù)域 , 存儲(chǔ)結(jié)點(diǎn)名稱struct CSNode *firstchild, *nextsibling; /孩子指針域和兄弟指針域 CSNode, *CSTree;樹的孩子兄弟表示法示意圖：.2. 構(gòu)

18、造一般樹算法：按照樹的先根次序序列構(gòu)建一棵樹：對(duì)于這棵樹，按照需求分析第1 頁的測(cè)試數(shù)據(jù)，用戶應(yīng)當(dāng)輸入（表示回車確認(rèn)）ABEF CDGHIJK正確輸入所需序列后，樹的建立完成。Status CreateCSTree(CSTree &CT) /按先根序列構(gòu)造樹/ 按先根次序輸入樹中結(jié)點(diǎn)的值（一個(gè)字符），空格字符表示空樹，構(gòu)造二叉鏈表表示樹Tchar ch;ch=getchar();if(ch=' ')CT=NULL;elseif(!(CT=(CSNode *)malloc(sizeof(CSNode)printf("內(nèi)存分配失敗！n");exit(OV

19、ERFLOW);/ifCT->data=ch;/生成根結(jié)點(diǎn)CreateCSTree(CT->firstchild);/構(gòu)建左子樹CreateCSTree(CT->nextsibling);/構(gòu)建右子樹/else.return OK;/CreateCSTree3. 轉(zhuǎn)換為二叉樹樹和二叉樹的轉(zhuǎn)換關(guān)鍵在于樹的二叉鏈表與其對(duì)應(yīng)的二叉樹的二叉鏈表是相同的，只是對(duì)同一個(gè)二叉鏈表的解釋不同，二叉樹的數(shù)據(jù)域存放結(jié)點(diǎn)名稱，左指針域指向左孩子，右指針域指向右孩子；樹的數(shù)據(jù)域存放結(jié)點(diǎn)名稱，左指針域指向孩子結(jié)點(diǎn)，右指針域指向與該結(jié)點(diǎn)相鄰的一個(gè)兄弟結(jié)點(diǎn)。當(dāng)兩者具有相同的存儲(chǔ)結(jié)構(gòu)時(shí)， 便可以完成轉(zhuǎn)換，轉(zhuǎn)

20、換過程的實(shí)質(zhì)是按照二叉樹的定義將二叉鏈表解釋為二叉樹的過程。Status ExchangeToBiTree(CSTree &CT,BiTree &T)/ 將一棵用二叉鏈表表示的樹遞歸地轉(zhuǎn)換為二叉樹if(!CT) /樹 CT 為空時(shí)，二叉樹T 為空T=NULL;else/ 若樹的對(duì)應(yīng)結(jié)點(diǎn)不空，申請(qǐng)內(nèi)存空間if(!(T=(BiNode *)malloc(sizeof(BiNode)printf("內(nèi)存分配失??！n");exit(OVERFLOW);/if/ 將樹的數(shù)據(jù)域復(fù)制到二叉樹對(duì)應(yīng)的數(shù)據(jù)域T->data=CT->data;/ 若樹的孩子域不為空，

21、則用樹的孩子域創(chuàng)建二叉樹的左子樹ExchangeToBiTree(CT->firstchild,T->lchild);/ 若樹的兄弟域不為空，則用樹的兄弟域創(chuàng)建二叉樹的右子樹ExchangeToBiTree(CT->nextsibling,T->rchild);/else./ExchangeToBiTree4. 二叉樹的遍歷二叉樹有先序、中序、后序、層序四種遍歷方式，而先序、中序、后序遍歷又有遞歸和非遞歸兩種算法，總共有7 個(gè)遍歷算法。其中，先序、中序、后序非遞歸遍歷算法需要用到棧，層序遍歷需要使用隊(duì)列，隊(duì)列和棧的相關(guān)定義和算法請(qǐng)參考詳細(xì)設(shè)計(jì)P21。二叉樹先序、中序、后

22、序遍歷的區(qū)別僅在于訪問根結(jié)點(diǎn)的時(shí)機(jī)不同，而層序遍歷則是逐層從左到右訪問每一個(gè)結(jié)點(diǎn)。先序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則訪問根結(jié)點(diǎn)(D) ；先序遍歷左子樹(L)；先序遍歷右子樹(R) 。中序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則中序遍歷左子樹(L)； 訪問根結(jié)點(diǎn)(D) ；中序遍歷右子樹(R) 。后序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則后序遍歷左子樹(L)； 后序遍歷右子樹(R) ；訪問根結(jié)點(diǎn)(D) 。雖然訪問根結(jié)點(diǎn)的時(shí)機(jī)不同，但是先左后右的規(guī)則并沒有改變。所有的遍歷函數(shù)都調(diào)用元素訪問函數(shù)Visit，他們的參數(shù)列表中均含有一個(gè)函數(shù)指針變量Statu

23、s(* Visit)(TElemType)，通過主函數(shù)向他們傳遞元素訪問函數(shù)Visit的函數(shù)名，就可以實(shí)現(xiàn)按元素訪問函數(shù)Visit設(shè)定格式輸出的目的。這樣的好處在于當(dāng)輸出格式改變時(shí)，只需修改元素訪問函數(shù)Visit的輸出格式而無需更改7 個(gè)遍歷函數(shù)，做到一改全改。以下是所有遍歷算法的實(shí)現(xiàn)以及元素訪問函數(shù)Visit：/-元素訪問函數(shù)Visit-Status PrintElement(TElemType e) /輸出元素e 的值printf(" %c ",e); /元素類型設(shè)定為字符型return OK;/PrintElement/-遞歸算法 -Status PreOrderTr

24、averse(BiTree T,Status(* Visit)(TElemType) /先序遍歷遞歸算法./ 采用二叉鏈表存儲(chǔ)結(jié)構(gòu)， Visit 是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)/ 先序遍歷二叉樹T 的遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visitif(T)if(Visit(T->data) /訪問根結(jié)點(diǎn)if(PreOrderTraverse(T->lchild,Visit) /訪問左子樹if(PreOrderTraverse(T->rchild,Visit) /訪問右子樹return OK;return ERROR; /ifelse return OK;/PreOrderTraver

25、seStatus InOrderTraverse(BiTree T,Status(* Visit)(TElemType) /中序遍歷遞歸算法/ 采用二叉鏈表存儲(chǔ)結(jié)構(gòu)， Visit 是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)/ 中序遍歷二叉樹T 的遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visitif(T)if(InOrderTraverse(T->lchild,Visit) /訪問左子樹if(Visit(T->data) /訪問根結(jié)點(diǎn)if(InOrderTraverse(T->rchild,Visit) /訪問右子樹return OK;return ERROR; /ifelse return OK;

26、/InOrderTraverseStatus PostOrderTraverse(BiTree T,Status(* Visit)(TElemType) /后序遍歷遞歸算法/ 采用二叉鏈表存儲(chǔ)結(jié)構(gòu)， Visit 是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)/ 后序遍歷二叉樹T 的遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visitif(T)if(PostOrderTraverse(T->lchild,Visit) /訪問左子樹if(PostOrderTraverse(T->rchild,Visit) /訪問右子樹if(Visit(T->data) /訪問根結(jié)點(diǎn).return OK;return ERRO

27、R;/ifelse return OK;/PostOrderTraverse/-非遞歸遍歷算法-Status PreOrderTraverse1(BiTree T,Status(* Visit)(TElemType) /先序遍歷非遞歸算法/ 采用二叉鏈表存儲(chǔ)結(jié)構(gòu)， Visit 是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)/ 先序遍歷二叉樹T 的非遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)VisitStack S;InitStack(S); /初始化棧BiTree p=T;/設(shè)置工作指針p 并對(duì)其賦初值while(p|!(StackEmpty(S)if(p)if(!Visit(p->data)/訪問根結(jié)點(diǎn)return

28、 ERROR;Push(S,p);/根指針進(jìn)棧p=p->lchild;/遍歷左子樹/ifelsePop(S,p);/根指針退棧p=p->rchild;/遍歷右子樹/else/whilereturn OK; /PreOrderTraverse1Status InOrderTraverse1(BiTree T,Status(* Visit)(TElemType) /中序遍歷非遞歸算法/ 采用二叉鏈表存儲(chǔ)結(jié)構(gòu)， Visit 是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)/ 中序遍歷二叉樹T 的非遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)VisitStack S;.InitStack(S);BiTree p=T;whi

29、le(p|!(StackEmpty(S)if(p)Push(S,p);/根指針進(jìn)棧p=p->lchild;/遍歷左子樹/ifelsePop(S,p);/根指針退棧if(!Visit(p->data)/訪問根結(jié)點(diǎn)return ERROR;p=p->rchild;/遍歷右子樹/else/whilereturn OK; /InOrderTraverse1Status PostOrderTraverse1(BiTree T,Status(* Visit)(TElemType) /后序遍歷非遞歸算法/ 采用二叉鏈表存儲(chǔ)結(jié)構(gòu)， Visit 是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)/ 后序遍歷二叉樹T

30、的非遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)VisitBiTree p=T, q=NULL; / int n=0;Stack s;InitStack(s);while(p)|(!StackEmpty(s) while(p)Push(s,p);p=p->lchild;/whileq=NULL;while(!StackEmpty(s)GetTop(s, p);.if(p->rchild=NULL)|(p->rchild=q)if(!Visit(p->data)/訪問根結(jié)點(diǎn)return ERROR;if(p=T) return ERROR;q=p;Pop(s,p);/ifelsep=

31、p->rchild;break;/else/while/whilereturn OK; /PostOrderTraverse1Status LevelOrderTraverse1(BiTree T,Status(* Visit)(TElemType) /層序遍歷非遞歸算法/ 采用二叉鏈表存儲(chǔ)結(jié)構(gòu)， Visit 是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)/ 層序遍歷二叉樹T 的算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)VisitQueue Q;BiTree p=T;if(T)/根結(jié)點(diǎn)入隊(duì)列InitQueue(Q);/初始化隊(duì)列EnQueue(Q,T);while(!QueueEmpty(Q)/隊(duì)列不空DeQueue(Q

32、,p);if(!Visit(p->data)/訪問根結(jié)點(diǎn)return ERROR;if(p->lchild)EnQueue(Q,p->lchild);/左孩子入隊(duì)列if(p->rchild).EnQueue(Q,p->rchild);/右孩子入隊(duì)列/whileprintf("n");/ifreturn OK; /LevelOrderTraverse15. 二叉樹的信息int BiTreeDepth(BiTree T) /遞歸求二叉樹高度/ 若二叉樹T 存在，返回T 的深度（高度），否則返回0int Thigh,leftThigh,rightTh

33、igh; /分別表示二叉樹高度，左子樹高度，右子樹高度if(!T) return 0; /樹高為 0elseleftThigh=BiTreeDepth(T->lchild);/求左子樹高度rightThigh=BiTreeDepth(T->rchild);/求右子樹高度if(leftThigh>=rightThigh)/求二叉樹高度Thigh=leftThigh+1;elseThigh=rightThigh+1;/elsereturn Thigh;/BiTreeDepthint NodeSubNum(BiTree T) /統(tǒng)計(jì)二叉樹的結(jié)點(diǎn)個(gè)數(shù)if(!T) return 0;

34、/二叉樹為空樹，沒有結(jié)點(diǎn)else return(NodeSubNum(T->lchild)+NodeSubNum(T->rchild)+1); /NodeSubNum6. 銷毀樹void DestoryCSTree(CSTree &CT)/ 按照樹的定義遞歸地銷毀樹if(CT) /非空樹if(CT->firstchild)/孩子子樹非空.DestoryCSTree(CT->firstchild);if(CT->nextsibling) /兄弟子樹非空DestoryCSTree(CT->nextsibling);free(CT); /釋放根結(jié)點(diǎn)CT=N

35、ULL;/空指針賦0/if/DestoryTreevoid DestoryBiTree(BiTree &T)/ 按照二叉樹定義遞歸地銷毀二叉樹if(T) /非空樹if(T->lchild) /左子樹非空 , 銷毀左子樹DestoryBiTree(T->lchild);if(T->rchild) /右子樹非空 , 銷毀右子樹DestoryBiTree(T->rchild);free(T); /釋放根結(jié)點(diǎn)T=NULL;/空指針賦0/if/DestoryTreevoid DestoryTree(CSTree &CT,BiTree &T)/ 銷毀樹和二叉

36、樹DestoryCSTree(CT);DestoryBiTree(T);printf("->生成的樹和二叉樹已被銷毀！");/DestoryTree7. 棧和隊(duì)列的定義及算法/-棧的順序存儲(chǔ)表示-typedef BiTree SElemType;/棧的元素為二叉樹指針類型typedef struct /棧的順序存儲(chǔ)表示SElemType *base;/棧底指針，在棧構(gòu)造之前和銷毀之后，base 的值為 NULLSElemType *top;/棧頂指針.int stacksize;/當(dāng)前已分配的存儲(chǔ)空間，以元素為單位Stack;/-隊(duì)列的鏈?zhǔn)酱鎯?chǔ)表示-typedef B

37、iTree QElemType;/隊(duì)列元素為二叉樹指針類型typedef struct QNode /鏈隊(duì)列的C 語言表示QElemType data;/數(shù)據(jù)域struct QNode * next;/指針域QNode,* QueuePtr;typedef structQueuePtr front; /隊(duì)頭指針QueuePtr rear;/隊(duì)尾指針Queue;/-棧的相關(guān)函數(shù) ( 供非遞歸后序遍歷使用)-Status InitStack(Stack &S)/構(gòu)造一個(gè)空的順序棧if(!(S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(S

38、ElemType)printf("內(nèi)存分配失?。");exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/InitStackStatus DestoryStack(Stack &S)/釋放順序棧S 所占內(nèi)存空間free(S.base);S.base=NULL;S.top=NULL;return OK;/DestoryStackStatus StackEmpty(Stack S)/判斷順序棧S 是否為空棧 , 是返回 1，否返回0.return S.top=S.base;/StackI

39、sEmptyStatus Push(Stack &S,SElemType e) /入棧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;/PushStatus Pop(St

40、ack &S,SElemType &e) /出棧if(StackEmpty(S)return ERROR;e=*-S.top;return OK;/PopStatus GetTop(Stack S,SElemType &e)/ 若棧不空，用 e 返回順序棧 S 棧頂元素的值，并返回 OK，否則返回 ERRROR if(StackEmpty(S)return ERROR;e = *(S.top-1);return OK;/GetTop/-隊(duì)列的相關(guān)函數(shù)( 供非遞歸層序遍歷使用)-QueuePtr MallocQNode()/為鏈隊(duì)列結(jié)點(diǎn)申請(qǐng)內(nèi)存的函數(shù)QueuePtr p;

41、 /工作指針p.if(!(p=(QueuePtr)malloc(sizeof(QNode) /申請(qǐng)結(jié)點(diǎn)的內(nèi)存空間， 若失敗則提示并退出程序printf("內(nèi)存分配失敗，程序即將退出！n");exit(OVERFLOW);return p; /MallocQNodeStatus InitQueue(Queue &Q) /初始化鏈隊(duì)列 / 構(gòu)建一個(gè)空隊(duì)列 QQ.front=Q.rear=MallocQNode();/申請(qǐng)頭結(jié)點(diǎn)的內(nèi)存空間，并使隊(duì)頭和隊(duì)尾指針同時(shí)指向它Q.front->next=NULL;Q.front->data=0;/將隊(duì)長設(shè)為0retur

42、n OK;/InitQueueStatus DestoryQueue(Queue &Q)/銷毀隊(duì)列Qwhile(Q.front) / 從頭結(jié)點(diǎn)開始向后逐個(gè)釋放結(jié)點(diǎn)內(nèi)存空間 Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;/whileprintf("鏈隊(duì)列已成功銷毀！n");return OK;/DestoryQueueStatus QueueEmpty(Queue Q)/若 Q為空隊(duì)列，則返回OK;否則返回ERRORif(Q.rear=Q.front) /隊(duì)列為空的標(biāo)志return OK;return ERR

43、OR;/QueueEmptyStatus EnQueue(Queue &Q,QElemType e)./ 插入元素 e 為 Q的新的隊(duì)尾元素QueuePtr p=MallocQNode();p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;Q.front->data+; /隊(duì)長 +1return OK;/EnQueueStatus DeQueue(Queue &Q,QElemType &e) / 若隊(duì)列不空 , 則刪除 Q的隊(duì)頭元素 , 用 e 返回其值 , 并返回 OK,否則返回 ERROR if(Q

44、ueueEmpty(Q)return ERROR; QueuePtr p= Q.front->next;e = p->data;Q.front->next = p->next;if(Q.rear=p)Q.rear=Q.front;free(p);Q.front->data-; /隊(duì)長 -1return OK;/DeQueue8. 主函數(shù)int main(int argc,char *argv)printf("-樹的應(yīng)用-n");BiTree T=NULL;/聲明一棵二叉樹CSTree CT=NULL;/聲明一棵普通樹printf("-樹的建立-n");printf("->請(qǐng)按樹的先根次序輸入序列，如有空子樹， 用空格填充， 完成后輸入回車確認(rèn) n");CreateCSTree(CT);.printf("-樹的轉(zhuǎn)換 -n");printf("->正在將輸入的樹轉(zhuǎn)換為其對(duì)應(yīng)的二叉樹.n");ExchangeToBiTree(CT,T);printf("->