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

1、<p>　　數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)</p><p><b>　　說(shuō) 明 書</b></p><p>　　2015 年1月 29 日</p><p><b>　　一、需求分析</b></p><p>　　1.設(shè)計(jì)內(nèi)容及設(shè)計(jì)要求</p><p><b>　　A

2、.設(shè)計(jì)內(nèi)容：</b></p><p><b>　　（1）建立一棵樹(shù)；</b></p><p>　　（2）將樹(shù)轉(zhuǎn)換成二叉樹(shù)；</p><p>　　（3）實(shí)現(xiàn)二叉樹(shù)的前序、中序、后序的遞歸和非遞歸遍歷算法。</p><p><b>　　B.設(shè)計(jì)要求：</b></p><p

3、>　　(1) 符合課題要求，實(shí)現(xiàn)相應(yīng)功能；</p><p>　　(2) 要求界面友好美觀，操作方便易行；</p><p>　　(3) 注意程序的實(shí)用性、安全性；</p><p>　　2.本演示程序中，元素為單個(gè)字符，以空格表示空樹(shù)(即結(jié)點(diǎn)為空)，以回車符作為輸入結(jié)束標(biāo)志，樹(shù)采用孩子兄弟表示法，二叉樹(shù)采用二叉鏈表表示法。在真實(shí)的運(yùn)行過(guò)程中，由用戶手動(dòng)輸入待創(chuàng)建樹(shù)

4、的含有空格的先根次序序列，并按回車結(jié)束，程序會(huì)將其轉(zhuǎn)化為其對(duì)應(yīng)的二叉樹(shù)，然后對(duì)二叉樹(shù)進(jìn)行先序、中序、后序的遞歸及非遞歸遍歷以及層序遍歷，然后顯示轉(zhuǎn)化后二叉樹(shù)的高度和總結(jié)點(diǎn)數(shù)，以驗(yàn)證所創(chuàng)建的二叉樹(shù)是否正確，最后，銷毀創(chuàng)建的樹(shù)和二叉樹(shù)，程序結(jié)束。</p><p>　　3.演示程序以用戶和計(jì)算機(jī)對(duì)話方式執(zhí)行，即在計(jì)算機(jī)終端（屏幕）上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序規(guī)定的運(yùn)算命令，相應(yīng)的輸入數(shù)據(jù)和運(yùn)算結(jié)果

5、顯示在其后。</p><p>　　4.為了美觀，程序的輸出結(jié)果采用了分塊顯示的模式，由虛線及標(biāo)題隔開(kāi)，便于用戶檢查和驗(yàn)證。</p><p><b>　　5.測(cè)試數(shù)據(jù)</b></p><p>　　如圖，給出一棵樹(shù)，若屏幕上顯示如下信息：</p><p>　　->請(qǐng)按樹(shù)的先根次序輸入序列，如有空子樹(shù)，用空格填充，完成后

6、輸入回車確認(rèn)</p><p>　　此時(shí)，你應(yīng)當(dāng)輸入：（↙表示回車確認(rèn)）</p><p>　　ABE F C DGHI J K ↙</p><p>　　提示：為方便確認(rèn)輸入了幾個(gè)空格，用星號(hào)’*’表示輸入序列中的空格，則序列如下</p><p>　　ABE*F**C*DGHI*J*K******↙（不是真實(shí)的輸入序列，供計(jì)算需輸入空

7、格個(gè)數(shù)時(shí)用）</p><p>　　這時(shí)，建好的樹(shù)的先根和后根次序序列如下：</p><p>　　樹(shù)的先根序列 A B E F C D G H I J K</p><p>　　樹(shù)的后根序列 E F B C I J K H G D A</p><p>　　由樹(shù)和二叉樹(shù)的轉(zhuǎn)換關(guān)系知，二叉樹(shù)的先序和

8、中序遍歷所得序列分別與樹(shù)的先根和后根遍歷所得序列相同，據(jù)此驗(yàn)證轉(zhuǎn)化是否正確。二叉樹(shù)的先序和中序遍歷序列如下：</p><p>　　二叉樹(shù)先序序列 A B E F C D G H I J K</p><p>　　二叉樹(shù)中序序列 E F B C I J K H G D A</p><p><b>　　概要設(shè)計(jì)&l

9、t;/b></p><p>　　為了實(shí)現(xiàn)上述程序功能，樹(shù)采用孩子兄弟表示法，二叉樹(shù)采用二叉鏈表表示法。為此，需要兩個(gè)抽象數(shù)據(jù)類型，樹(shù)和二叉樹(shù)的抽象數(shù)據(jù)類型。</p><p>　　1.樹(shù)的抽象數(shù)據(jù)類型定義</p><p>　　ADT Tree{ </p><p>　　數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。 &#

10、160;</p><p>　　數(shù)據(jù)關(guān)系R：若D為空集，則稱為空樹(shù)； </p><p>　　若D僅含有一個(gè)數(shù)據(jù)元素，則R為空集，否則R={H}，H是如下二元關(guān)系： </p><p>　　(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無(wú)前驅(qū)；  </p><p>　　(2)若D-{root}≠

11、Φ，則存在D-{root}的一個(gè)劃分D1,D2,D3, ?,Dm(m>0)，</p><p>　　對(duì)于任意j≠k(1≤j,k≤m)有Dj∩Dk=Φ,且對(duì)任意的i(1≤i≤m)，</p><p>　　唯一存在數(shù)據(jù)元素xi∈Di有<root,xi>∈H;</p><p>　　(3)對(duì)應(yīng)于D-{root}的劃分，H-{<root,xi&g

12、t;,?,<root,xm>}有唯一的一個(gè)劃分</p><p>　　H1，H2,?,Hm(m>0)，對(duì)任意j≠k(1≤j,k≤m)有Hj∩Hk=Φ，且對(duì)任意i</p><p>　　(1≤i≤m),Hi是Di上的二元關(guān)系，(Di,{Hi})是一棵符合本定義的樹(shù)，</p><p>　　稱為根root的子樹(shù)。 </p><p

13、><b>　　基本操作P： </b></p><p>　　InitTree(&T); </p><p>　　操作結(jié)果：構(gòu)造空樹(shù)T。 </p><p>　　DestroyTree(&T); </p><p>　　初始條件：樹(shù)T存在。 </p>

14、;<p>　　操作結(jié)果：銷毀樹(shù)T。 </p><p>　　CreateTree(&T,definition); </p><p>　　初始條件：definition給出樹(shù)T的定義。 </p><p>　　操作結(jié)果：按definition構(gòu)造樹(shù)T。 </p><p>　　ClearT

15、ree(&T); </p><p>　　初始條件：樹(shù)T存在。 </p><p>　　操作結(jié)果：將樹(shù)T清為空樹(shù)。 </p><p>　　TreeEmpty(T); </p><p>　　初始條件：樹(shù)T存在。 </p><p>　　操作結(jié)果：若T為空樹(shù)，則返回TRU

16、E，否則返回FALSE。 </p><p>　　TreeDepth(T); </p><p>　　初始條件：樹(shù)T存在。 </p><p>　　操作結(jié)果：返回Ｔ的深度。 </p><p><b>　　Root(T); </b></p><p>　　初

17、始條件：樹(shù)T存在。 </p><p>　　操作結(jié)果：返回T的根。 </p><p>　　Value(T,cur_e); </p><p>　　初始條件：樹(shù)T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。 </p><p>　　操作結(jié)果：返回cur_e的值。 </p><p>　　As

18、sign(T,cur_e,value); </p><p>　　初始條件：樹(shù)T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。 </p><p>　　操作結(jié)果：結(jié)點(diǎn)cur_e賦值為value。 </p><p>　　Parent(T,cur_e); </p><p>　　初始條件：樹(shù)T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。&

19、#160;</p><p>　　操作結(jié)果：若cur_e是T的非根結(jié)點(diǎn)，則返回它的雙親，否則函數(shù)值為“空”。 </p><p>　　LeftChild(T,cur_e); </p><p>　　初始條件：樹(shù)T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。 </p><p>　　操作結(jié)果：若cur_e是T的非葉子結(jié)點(diǎn)，則返回它的最

20、左孩子，否則返回“空”。 </p><p>　　RightSibling(T,cur_e); </p><p>　　初始條件：樹(shù)T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。 </p><p>　　操作結(jié)果：若cur_e有右兄弟，則返回它的右兄弟，否則返回“空”。 </p><p>　　InsertChild(&a

21、mp;T,&p,I,c); </p><p>　　初始條件：樹(shù)Ｔ存在，ｐ指向Ｔ中某個(gè)結(jié)點(diǎn)，1≤i≤p指結(jié)點(diǎn)的度＋１，非空樹(shù)ｃ與Ｔ不相交。 </p><p>　　操作結(jié)果：插入c為Ｔ中ｐ指結(jié)點(diǎn)的第ｉ棵子樹(shù)。 </p><p>　　DeleteChild(&T,&p,i); </p><

22、p>　　初始條件：樹(shù)T存在，p指向T中某個(gè)結(jié)點(diǎn)，1≤i≤p指結(jié)點(diǎn)的度。 </p><p>　　操作結(jié)果：刪除Ｔ中ｐ所指結(jié)點(diǎn)的第ｉ棵子樹(shù)。 </p><p>　　TraverseTree(T,visit()); </p><p>　　初始條件：樹(shù)T存在，visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。 </p><p

23、>　　操作結(jié)果：按某種次序?qū)的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit( )一次且至多一次。一旦visit( )失敗，則操作失敗。 </p><p><b>　　}ADT Tree</b></p><p>　　2.二叉樹(shù)的抽象數(shù)據(jù)類型定義</p><p>　　ADT BinaryTree{ </p><p>

24、;　　數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。 </p><p><b>　　數(shù)據(jù)關(guān)系R： </b></p><p>　　若D=Φ，則R=Φ，稱BinaryTree為空二叉樹(shù)； </p><p>　　若D≠Φ，則R={H}，H是如下二元關(guān)系； </p><p>　　（1）在D中存在惟一的稱為根的數(shù)據(jù)元素ro

25、ot，它在關(guān)系H下無(wú)前驅(qū)； </p><p>　　（2）若D-{root}≠Φ，則存在D-{root}={D1,Dr}，且D1∩Dr =Φ； </p><p>　?。?）若D1≠Φ，則D1中存在惟一的元素x1，<root,x1>∈H，且存在D1上的關(guān)系H1 ?H；若Dr≠Φ，則Dr中存在惟一的元素xr，<root,xr>∈H，且存在上的關(guān)系Hr ?H；H={&l

26、t;root,x1>,<root,xr>,H1,Hr}； </p><p>　?。?）(D1,{H1})是一棵符合本定義的二叉樹(shù)，稱為根的左子樹(shù)；(Dr,{Hr})是一棵符合本定義的二叉樹(shù)，稱為根的右子樹(shù)。 </p><p><b>　　基本操作： </b></p><p>　　InitBiTree( &T )

27、</p><p>　　操作結(jié)果：構(gòu)造空二叉樹(shù)T。</p><p>　　DestroyBiTree( &T ) </p><p>　　初始條件：二叉樹(shù)T已存在。 </p><p>　　操作結(jié)果：銷毀二叉樹(shù)T。 </p><p>　　CreateBiTree( &T, definition ) <

28、;/p><p>　　初始條件：definition給出二叉樹(shù)T的定義。 </p><p>　　操作結(jié)果：按definiton構(gòu)造二叉樹(shù)T。 </p><p>　　ClearBiTree( &T ) </p><p>　　初始條件：二叉樹(shù)T存在。 </p><p>　　操作結(jié)果：將二叉樹(shù)T清為空樹(shù)。 </

29、p><p>　　BiTreeEmpty( T ) </p><p>　　初始條件：二叉樹(shù)T存在。 </p><p>　　操作結(jié)果：若T為空二叉樹(shù)，則返回TRUE，否則返回FALSE。 </p><p>　　BiTreeDepth( T ) </p><p>　　初始條件：二叉樹(shù)T存在。 </p>&l

30、t;p>　　操作結(jié)果：返回T的深度。 </p><p>　　Root( T ) </p><p>　　初始條件：二叉樹(shù)T存在。 </p><p>　　操作結(jié)果：返回T的根。 </p><p>　　Value( T, e ) </p><p>　　初始條件：二叉樹(shù)T存在，e是T中某個(gè)結(jié)點(diǎn)。 </p&g

31、t;<p>　　操作結(jié)果：返回e的值。 </p><p>　　Assign( T, &e, value ) </p><p>　　初始條件：二叉樹(shù)T存在，e是T中某個(gè)結(jié)點(diǎn)。 </p><p>　　操作結(jié)果：結(jié)點(diǎn)e賦值為value。 </p><p>　　Parent( T, e ) </p><

32、p>　　初始條件：二叉樹(shù)T存在，e是T中某個(gè)結(jié)點(diǎn)。 </p><p>　　操作結(jié)果：若e是T的非根結(jié)點(diǎn)，則返回它的雙親，否則返回“空”。 </p><p>　　LeftChild( T, e ) </p><p>　　初始條件：二叉樹(shù)T存在，e是T中某個(gè)結(jié)點(diǎn)。 </p><p>　　操作結(jié)果：返回e的左孩子。若e無(wú)左孩子，則返回“

33、空”。 </p><p>　　RightChild( T, e ) </p><p>　　初始條件：二叉樹(shù)T存在，e是T中某個(gè)結(jié)點(diǎn)。 </p><p>　　操作結(jié)果：返回e的右孩子。若e無(wú)右孩子，則返回“空”。 </p><p>　　LeftSibling( T, e ) </p><p>　　初始條件：二叉樹(shù)T

34、存在，e是T中某個(gè)結(jié)點(diǎn)。 </p><p>　　操作結(jié)果：返回e的左兄弟。若e是T的左孩子或無(wú)左兄弟，則返回“空”。 </p><p>　　RightSibling( T, e ) </p><p>　　初始條件：二叉樹(shù)T存在，e是T中某個(gè)結(jié)點(diǎn)。 </p><p>　　操作結(jié)果：返回e的右兄弟。若e是T的右孩子或無(wú)右兄弟，則返回“空”。

35、 </p><p>　　InsertChild( T, p, LR, c ) </p><p>　　初始條件：二叉樹(shù)T存在，p指向T中某個(gè)結(jié)點(diǎn)，LR為0或1，非空二叉樹(shù)c與T不相交且右子樹(shù)為空。 </p><p>　　操作結(jié)果：根據(jù)LR為0或1，插入c為T中p所指結(jié)點(diǎn)的左或右子樹(shù)。p所指結(jié)點(diǎn)的原有左或右子樹(shù)則成為c的右子樹(shù)。 </p><p&

36、gt;　　DeleteChild( T, p, LR ) </p><p>　　初始條件：二叉樹(shù)T存在，p指向T中某個(gè)結(jié)點(diǎn)，LR為0或1。 </p><p>　　操作結(jié)果：根據(jù)LR為0或1，刪除T中p所指結(jié)點(diǎn)的左或右子樹(shù)。 </p><p>　　PreOrderTraverse( T, visit() ) </p><p>　　初始條件

37、：二叉樹(shù)T存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。 </p><p>　　操作結(jié)果：先序遍歷T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗，則操作失敗。 </p><p>　　InOrderTraverse( T, visit() ) </p><p>　　初始條件：二叉樹(shù)T存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。 </p>

38、<p>　　操作結(jié)果：中序遍歷T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗，則操作失敗。 </p><p>　　PostOrderTraverse( T, visit() ) </p><p>　　初始條件：二叉樹(shù)T存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。 </p><p>　　操作結(jié)果：后序遍歷T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visi

39、t一次且僅一次。一旦visit()失敗，則操作失敗。 </p><p>　　LevelOrderTraverse( T, visit() ) </p><p>　　初始條件：二叉樹(shù)T存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。 </p><p>　　操作結(jié)果：層次遍歷T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗，則操作失敗。 </p&g

40、t;<p>　　}ADT BinaryTree </p><p><b>　　本程序包括個(gè)模塊</b></p><p><b>　　【1】主程序模塊</b></p><p>　　先聲明一棵樹(shù)和一棵二叉樹(shù)，然后輸入樹(shù)的含空格先根次序序列，構(gòu)建一棵樹(shù)，然后將其轉(zhuǎn)化為二叉樹(shù)，并對(duì)二叉樹(shù)進(jìn)行先序、中序、后序的遞歸和非

41、遞歸遍歷以及層序遍歷，然后輸出二叉樹(shù)的高度和總結(jié)點(diǎn)數(shù)，最后銷毀這兩棵樹(shù)。</p><p>　　【2】建立樹(shù)模塊——按照樹(shù)的先根序列創(chuàng)建樹(shù)。</p><p>　　【3】樹(shù)轉(zhuǎn)化二叉樹(shù)模塊——將樹(shù)轉(zhuǎn)化為二叉樹(shù)。</p><p>　　【4】二叉樹(shù)的遍歷——二叉樹(shù)的先序、中序、后序的遞歸和非遞歸遍歷以及層序遍歷。</p><p>　　【5】二叉樹(shù)的相關(guān)

42、信息——二叉樹(shù)的高度和總結(jié)點(diǎn)數(shù)。</p><p>　　【6】銷毀樹(shù)和二叉樹(shù)模塊——銷毀創(chuàng)建的樹(shù)和轉(zhuǎn)換出的二叉樹(shù)。</p><p>　　【7】棧和隊(duì)列的模塊——供二叉樹(shù)先序、中序、后序的非遞歸算法調(diào)用</p><p><b>　　各模塊之間關(guān)系：</b></p><p><b>　　詳細(xì)設(shè)計(jì)</b>&

43、lt;/p><p>　　元素類型、結(jié)點(diǎn)類型和指針類型</p><p>　　樹(shù)的結(jié)點(diǎn)元素類型設(shè)置為字符型，這樣既可以接收字符也可以接受數(shù)字。</p><p>　　typedef char TElemType; //樹(shù)中結(jié)點(diǎn)元素類型</p><p>　　//----------------二叉樹(shù)的二叉鏈表存儲(chǔ)表示-----------------

44、--- </p><p>　　typedef struct BiNode{</p><p>　　TElemType data; //數(shù)據(jù)域,存儲(chǔ)結(jié)點(diǎn)名稱</p><p>　　struct BiNode *lchild,*rchild; //孩子結(jié)點(diǎn)指針 </p><p>　　}BiNode,*BiTree;</p>&

45、lt;p>　　二叉樹(shù)的二叉鏈表表示法示意圖：</p><p>　　//-------------------樹(shù)的孩子兄弟表示法----------------------- </p><p>　　typedef struct CSNode{</p><p>　　TElemType data; //數(shù)據(jù)域,存儲(chǔ)結(jié)點(diǎn)名稱 </p><p>

46、;　　struct CSNode *firstchild, *nextsibling; //孩子指針域和兄弟指針域 </p><p>　　} CSNode, *CSTree;</p><p>　　樹(shù)的孩子兄弟表示法示意圖：</p><p><b>　　構(gòu)造一般樹(shù)算法：</b></p><p>　　按照樹(shù)的先根次序序列構(gòu)

47、建一棵樹(shù)：</p><p>　　對(duì)于這棵樹(shù)，按照需求分析第1頁(yè)的測(cè)試數(shù)據(jù)，用戶應(yīng)當(dāng)輸入（↙表示回車確認(rèn)）</p><p>　　ABE F C DGHI J K ↙</p><p>　　正確輸入所需序列后，樹(shù)的建立完成。</p><p>　　Status CreateCSTree(CSTree &CT){ //按先根序列構(gòu)

48、造樹(shù) </p><p>　　//按先根次序輸入樹(shù)中結(jié)點(diǎn)的值（一個(gè)字符），空格字符表示空樹(shù)，構(gòu)造二叉鏈表表示樹(shù)T</p><p><b>　　char ch;</b></p><p>　　ch=getchar();</p><p>　　if(ch==' ')</p><p><

49、b>　　CT=NULL;</b></p><p><b>　　else{</b></p><p>　　if(!(CT=(CSNode *)malloc(sizeof(CSNode)))){</p><p>　　printf("內(nèi)存分配失敗！\n");</p><p>　　exit(O

50、VERFLOW); </p><p><b>　　}//if</b></p><p>　　CT->data=ch; //生成根結(jié)點(diǎn) </p><p>　　CreateCSTree(CT->firstchild); //構(gòu)建左子樹(shù) </p><p>　　Create

51、CSTree(CT->nextsibling); //構(gòu)建右子樹(shù) </p><p><b>　　}//else </b></p><p>　　return OK; </p><p>　　}//CreateCSTree</p><p><b>　　轉(zhuǎn)換為二叉樹(shù) </b></p>

52、<p>　　樹(shù)和二叉樹(shù)的轉(zhuǎn)換關(guān)鍵在于樹(shù)的二叉鏈表與其對(duì)應(yīng)的二叉樹(shù)的二叉鏈表是相同的，只是對(duì)同一個(gè)二叉鏈表的解釋不同，二叉樹(shù)的數(shù)據(jù)域存放結(jié)點(diǎn)名稱，左指針域指向左孩子，右指針域指向右孩子；樹(shù)的數(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)換過(guò)程的實(shí)質(zhì)是按照二叉樹(shù)的定義將二叉鏈表解釋為二叉樹(shù)的過(guò)程。</p><p>　　Sta

53、tus ExchangeToBiTree(CSTree &CT,BiTree &T){ </p><p>　　//將一棵用二叉鏈表表示的樹(shù)遞歸地轉(zhuǎn)換為二叉樹(shù)</p><p>　　if(!CT) //樹(shù)CT為空時(shí)，二叉樹(shù)T為空</p><p><b>　　T=NULL;</b></p><p><b

54、>　　else{ </b></p><p>　　//若樹(shù)的對(duì)應(yīng)結(jié)點(diǎn)不空，申請(qǐng)內(nèi)存空間</p><p>　　if(!(T=(BiNode *)malloc(sizeof(BiNode)))){ </p><p>　　printf("內(nèi)存分配失??！\n");</p><p>　　exit(OVERFL

55、OW); </p><p><b>　　}//if</b></p><p>　　//將樹(shù)的數(shù)據(jù)域復(fù)制到二叉樹(shù)對(duì)應(yīng)的數(shù)據(jù)域</p><p>　　T->data=CT->data; </p><p>　　//若樹(shù)的孩子域不為空，則用樹(shù)的孩子域創(chuàng)建二叉樹(shù)的左子樹(shù) </p>&l

56、t;p>　　ExchangeToBiTree(CT->firstchild,T->lchild); </p><p>　　//若樹(shù)的兄弟域不為空，則用樹(shù)的兄弟域創(chuàng)建二叉樹(shù)的右子樹(shù) </p><p>　　ExchangeToBiTree(CT->nextsibling,T->rchild); </p><p><b>　　}/

57、/else </b></p><p>　　}//ExchangeToBiTree</p><p><b>　　二叉樹(shù)的遍歷</b></p><p>　　二叉樹(shù)有先序、中序、后序、層序四種遍歷方式，而先序、中序、后序遍歷又有遞歸和非遞歸兩種算法，總共有7個(gè)遍歷算法。其中，先序、中序、后序非遞歸遍歷算法需要用到棧，層序遍歷需要使用隊(duì)列

58、，隊(duì)列和棧的相關(guān)定義和算法請(qǐng)參考詳細(xì)設(shè)計(jì)P21。</p><p>　　二叉樹(shù)先序、中序、后序遍歷的區(qū)別僅在于訪問(wèn)根結(jié)點(diǎn)的時(shí)機(jī)不同，而層序遍歷則是逐層從左到右訪問(wèn)每一個(gè)結(jié)點(diǎn)。</p><p>　　先序遍歷二叉樹(shù)算法的框架是：</p><p>　　若二叉樹(shù)為空，則空操作；</p><p>　　否則 訪問(wèn)根結(jié)點(diǎn) (D)； 先序遍歷左子樹(shù)

59、 (L)； 先序遍歷右子樹(shù) (R)。</p><p>　　中序遍歷二叉樹(shù)算法的框架是：</p><p>　　若二叉樹(shù)為空，則空操作；</p><p>　　否則 中序遍歷左子樹(shù) (L)； 訪問(wèn)根結(jié)點(diǎn) (D)； 中序遍歷右子樹(shù) (R)。</p><p>　　后序遍歷二叉樹(shù)算法的框架是：</p><p>

60、　　若二叉樹(shù)為空，則空操作；</p><p>　　否則 后序遍歷左子樹(shù) (L)； 后序遍歷右子樹(shù) (R)； 訪問(wèn)根結(jié)點(diǎn) (D)。</p><p>　　雖然訪問(wèn)根結(jié)點(diǎn)的時(shí)機(jī)不同，但是先左后右的規(guī)則并沒(méi)有改變。</p><p>　　所有的遍歷函數(shù)都調(diào)用元素訪問(wèn)函數(shù)Visit，他們的參數(shù)列表中均含有一個(gè)函數(shù)指針變量Status(* Visit)(TElemTyp

61、e)，通過(guò)主函數(shù)向他們傳遞元素訪問(wèn)函數(shù)Visit的函數(shù)名，就可以實(shí)現(xiàn)按元素訪問(wèn)函數(shù)Visit設(shè)定格式輸出的目的。這樣的好處在于當(dāng)輸出格式改變時(shí)，只需修改元素訪問(wèn)函數(shù)Visit的輸出格式而無(wú)需更改7個(gè)遍歷函數(shù)，做到一改全改。</p><p>　　以下是所有遍歷算法的實(shí)現(xiàn)以及元素訪問(wèn)函數(shù)Visit：</p><p>　　//-----------------------元素訪問(wèn)函數(shù)Visit-

62、------------------------ </p><p>　　Status PrintElement(TElemType e) { //輸出元素e的值 </p><p>　　printf(" %c ",e); //元素類型設(shè)定為字符型</p><p>　　return OK;</p><p>　　}//P

63、rintElement</p><p>　　//--------------------------遞歸算法-------------------------------- </p><p>　　Status PreOrderTraverse(BiTree T,Status(* Visit)(TElemType)){ //先序遍歷遞歸算法 </p><p>　　/

64、/采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)</p><p>　　//先序遍歷二叉樹(shù)T的遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit </p><p><b>　　if(T){</b></p><p>　　if(Visit(T->data)) //訪問(wèn)根結(jié)點(diǎn)</p><p>　　if(PreOrder

65、Traverse(T->lchild,Visit)) //訪問(wèn)左子樹(shù)</p><p>　　if(PreOrderTraverse(T->rchild,Visit)) //訪問(wèn)右子樹(shù)</p><p>　　return OK;</p><p>　　return ERROR;</p><p><b>　　} //if<

66、;/b></p><p>　　else return OK;</p><p>　　}//PreOrderTraverse</p><p>　　Status InOrderTraverse(BiTree T,Status(* Visit)(TElemType)){ //中序遍歷遞歸算法 </p><p>　　//采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，V

67、isit是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)</p><p>　　//中序遍歷二叉樹(shù)T的遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit </p><p><b>　　if(T){</b></p><p>　　if(InOrderTraverse(T->lchild,Visit)) //訪問(wèn)左子樹(shù)</p><p>　　if(Vi

68、sit(T->data)) //訪問(wèn)根結(jié)點(diǎn)</p><p>　　if(InOrderTraverse(T->rchild,Visit)) //訪問(wèn)右子樹(shù)</p><p>　　return OK;</p><p>　　return ERROR;</p><p><b>　　} //if</b></p&

69、gt;<p>　　else return OK;</p><p>　　}//InOrderTraverse </p><p>　　Status PostOrderTraverse(BiTree T,Status(* Visit)(TElemType)){ //后序遍歷遞歸算法 </p><p>　　//采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對(duì)數(shù)據(jù)元素操作

70、的應(yīng)用函數(shù)</p><p>　　//后序遍歷二叉樹(shù)T的遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit </p><p><b>　　if(T){</b></p><p>　　if(PostOrderTraverse(T->lchild,Visit)) //訪問(wèn)左子樹(shù)</p><p>　　if(PostOrderTra

71、verse(T->rchild,Visit)) //訪問(wèn)右子樹(shù)</p><p>　　if(Visit(T->data)) //訪問(wèn)根結(jié)點(diǎn) </p><p>　　return OK;</p><p>　　return ERROR;</p><p><b>　　}//if</b></p><

72、;p>　　else return OK;</p><p>　　}//PostOrderTraverse</p><p>　　//-----------------------非遞歸遍歷算法---------------------------</p><p>　　Status PreOrderTraverse1(BiTree T,Status(* Visit)

73、(TElemType)){ //先序遍歷非遞歸算法 </p><p>　　//采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)</p><p>　　//先序遍歷二叉樹(shù)T的非遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit </p><p><b>　　Stack S;</b></p><p>　　InitStack

74、(S); //初始化棧</p><p>　　BiTree p=T; //設(shè)置工作指針p并對(duì)其賦初值</p><p>　　while(p||!(StackEmpty(S))){</p><p><b>　　if(p){</b></p><p>　　if(!Visit(p->data)) //訪問(wèn)根結(jié)點(diǎn) &

75、lt;/p><p>　　return ERROR;</p><p>　　Push(S,p); //根指針進(jìn)棧 </p><p>　　p=p->lchild; //遍歷左子樹(shù)</p><p><b>　　}//if</b></p><p><b>　　else{</

76、b></p><p>　　Pop(S,p); //根指針退棧 </p><p>　　p=p->rchild; //遍歷右子樹(shù) </p><p><b>　　}//else</b></p><p><b>　　}//while</b></p&

77、gt;<p>　　return OK;</p><p>　　} //PreOrderTraverse1</p><p>　　Status InOrderTraverse1(BiTree T,Status(* Visit)(TElemType)){ //中序遍歷非遞歸算法 </p><p>　　//采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用

78、函數(shù)</p><p>　　//中序遍歷二叉樹(shù)T的非遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit </p><p><b>　　Stack S;</b></p><p>　　InitStack(S);</p><p>　　BiTree p=T;</p><p>　　while(p||!(StackEm

79、pty(S))){</p><p><b>　　if(p){</b></p><p>　　Push(S,p); //根指針進(jìn)棧 </p><p>　　p=p->lchild; //遍歷左子樹(shù)</p><p><b>　　}//if</b></p><p>

80、;<b>　　else{</b></p><p>　　Pop(S,p); //根指針退棧 </p><p>　　if(!Visit(p->data)) //訪問(wèn)根結(jié)點(diǎn) </p><p>　　return ERROR;</p><p>　　p=p->rchild;

81、//遍歷右子樹(shù) </p><p><b>　　}//else</b></p><p><b>　　}//while</b></p><p>　　return OK;</p><p>　　} //InOrderTraverse1</p><p>　　Status PostOrd

82、erTraverse1(BiTree T,Status(* Visit)(TElemType)){ //后序遍歷非遞歸算法 </p><p>　　//采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)</p><p>　　//后序遍歷二叉樹(shù)T的非遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit </p><p>　　BiTree p=T, q=NULL; //

83、 int n=0;</p><p><b>　　Stack s;</b></p><p>　　InitStack(s); </p><p>　　while((p)||(!StackEmpty(s))) {</p><p><b>　　while(p){</b></p><p&

84、gt;　　Push(s,p);</p><p>　　p=p->lchild;</p><p><b>　　}//while</b></p><p><b>　　q=NULL;</b></p><p>　　while(!StackEmpty(s)){</p><p>　　

85、GetTop(s, p);</p><p>　　if((p->rchild==NULL)||(p->rchild==q)){</p><p>　　if(!Visit(p->data)) //訪問(wèn)根結(jié)點(diǎn) </p><p>　　return ERROR; </p><p>　　if(p==T) return ERROR

86、;</p><p><b>　　q=p;</b></p><p><b>　　Pop(s,p);</b></p><p><b>　　}//if</b></p><p><b>　　else{</b></p><p>　　p=p-&

87、gt;rchild;</p><p>　　break;</p><p><b>　　}//else</b></p><p><b>　　}//while</b></p><p><b>　　}//while</b></p><p>　　retur

88、n OK;</p><p>　　} //PostOrderTraverse1</p><p>　　Status LevelOrderTraverse1(BiTree T,Status(* Visit)(TElemType)){ //層序遍歷非遞歸算法 </p><p>　　//采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)</p><

89、;p>　　//層序遍歷二叉樹(shù)T的算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit </p><p><b>　　Queue Q;</b></p><p>　　BiTree p=T;</p><p>　　if(T){ //根結(jié)點(diǎn)入隊(duì)列</p><p>　　InitQueue(Q); //初始化隊(duì)列 &

90、lt;/p><p>　　EnQueue(Q,T); </p><p>　　while(!QueueEmpty(Q)){ //隊(duì)列不空 </p><p>　　DeQueue(Q,p);</p><p>　　if(!Visit(p->data)) //訪問(wèn)根結(jié)點(diǎn) </p><p>　　return ERROR;&

91、lt;/p><p>　　if(p->lchild)</p><p>　　EnQueue(Q,p->lchild); //左孩子入隊(duì)列 </p><p>　　if(p->rchild)</p><p>　　EnQueue(Q,p->rchild); //右孩子入隊(duì)列 </p><p><

92、b>　　}//while</b></p><p>　　printf("\n");</p><p><b>　　}//if</b></p><p>　　return OK;</p><p>　　} //LevelOrderTraverse1</p><p>&l

93、t;b>　　5.二叉樹(shù)的信息</b></p><p>　　int BiTreeDepth(BiTree T){ //遞歸求二叉樹(shù)高度 </p><p>　　//若二叉樹(shù)T存在，返回T的深度（高度），否則返回0</p><p>　　int Thigh,leftThigh,rightThigh; //分別表示二叉樹(shù)高度，左子樹(shù)高度，右子樹(shù)高度<

94、;/p><p>　　if(!T) return 0; //樹(shù)高為0</p><p><b>　　else{</b></p><p>　　leftThigh=BiTreeDepth(T->lchild); //求左子樹(shù)高度 </p><p>　　rightThigh=BiTreeDepth(T->rch

95、ild); //求右子樹(shù)高度 </p><p>　　if(leftThigh>=rightThigh) //求二叉樹(shù)高度 </p><p>　　Thigh=leftThigh+1;</p><p><b>　　else</b></p><p>　　Thigh=rightThigh+1; </p&

96、gt;<p><b>　　}//else</b></p><p>　　return Thigh;</p><p>　　}//BiTreeDepth</p><p>　　int NodeSubNum(BiTree T){ //統(tǒng)計(jì)二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù) </p><p>　　if(!T) return 0;

97、//二叉樹(shù)為空樹(shù)，沒(méi)有結(jié)點(diǎn) </p><p>　　else return(NodeSubNum(T->lchild)+NodeSubNum(T->rchild)+1); </p><p>　　}//NodeSubNum</p><p><b>　　6.銷毀樹(shù) </b></p><p>　　void De

98、storyCSTree(CSTree &CT){</p><p>　　//按照樹(shù)的定義遞歸地銷毀樹(shù)</p><p>　　if(CT){ //非空樹(shù) </p><p>　　if(CT->firstchild) //孩子子樹(shù)非空</p><p>　　DestoryCSTree(CT->firstchild);</p

99、><p>　　if(CT->nextsibling) //兄弟子樹(shù)非空 </p><p>　　DestoryCSTree(CT->nextsibling); </p><p>　　free(CT); //釋放根結(jié)點(diǎn)</p><p>　　CT=NULL; //空指針賦0 </p><p><b&g

100、t;　　}//if </b></p><p>　　}//DestoryTree</p><p>　　void DestoryBiTree(BiTree &T){</p><p>　　//按照二叉樹(shù)定義遞歸地銷毀二叉樹(shù)</p><p>　　if(T){ //非空樹(shù) </p><p>　　if(T-

101、>lchild) //左子樹(shù)非空,銷毀左子樹(shù)</p><p>　　DestoryBiTree(T->lchild);</p><p>　　if(T->rchild) //右子樹(shù)非空,銷毀右子樹(shù) </p><p>　　DestoryBiTree(T->rchild); </p><p>　　free(T); //釋

102、放根結(jié)點(diǎn)</p><p>　　T=NULL; //空指針賦0 </p><p><b>　　}//if </b></p><p>　　}//DestoryTree</p><p>　　void DestoryTree(CSTree &CT,BiTree &T){</p><p&g

103、t;<b>　　//銷毀樹(shù)和二叉樹(shù)</b></p><p>　　DestoryCSTree(CT);</p><p>　　DestoryBiTree(T);</p><p>　　printf("->生成的樹(shù)和二叉樹(shù)已被銷毀！"); </p><p>　　}//DestoryTree</p&

104、gt;<p>　　棧和隊(duì)列的定義及算法</p><p>　　//-------------------棧的順序存儲(chǔ)表示------------------------- </p><p>　　typedef BiTree SElemType; //棧的元素為二叉樹(shù)指針類型 </p><p>　　typedef struct { /

105、/棧的順序存儲(chǔ)表示 </p><p>　　SElemType *base; //棧底指針，在棧構(gòu)造之前和銷毀之后，base的值為NULL </p><p>　　SElemType *top; //棧頂指針</p><p>　　int stacksize;

106、 //當(dāng)前已分配的存儲(chǔ)空間，以元素為單位 </p><p><b>　　}Stack; </b></p><p>　　//------------------隊(duì)列的鏈?zhǔn)酱鎯?chǔ)表示----------------------- </p><p>　　typedef BiTree QElemType; //隊(duì)列元素為二叉樹(shù)指針類型</p

107、><p>　　typedef struct QNode{ //鏈隊(duì)列的C語(yǔ)言表示 </p><p>　　QElemType data; //數(shù)據(jù)域 </p><p>　　struct QNode * next; //指針域 </p><p>　　}QNode,* QueuePtr;</

108、p><p>　　typedef struct{</p><p>　　QueuePtr front; //隊(duì)頭指針 </p><p>　　QueuePtr rear; //隊(duì)尾指針 </p><p><b>　　}Queue; </b></p><p>　　//--------------棧的相關(guān)

109、函數(shù)(供非遞歸后序遍歷使用)-------------------</p><p>　　Status InitStack(Stack &S){//構(gòu)造一個(gè)空的順序棧 </p><p>　　if(!(S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)))){</p><p>　　printf

110、("內(nèi)存分配失敗！\n");</p><p>　　exit(OVERFLOW);</p><p><b>　　} </b></p><p>　　S.top=S.base;</p><p>　　S.stacksize=STACK_INIT_SIZE;</p><p>　　

111、return OK; </p><p>　　}//InitStack</p><p>　　Status DestoryStack(Stack &S){//釋放順序棧S所占內(nèi)存空間 </p><p>　　free(S.base);</p><p>　　S.base=NULL;</p><p>　　S.top=NU

112、LL; </p><p>　　return OK; </p><p>　　}//DestoryStack</p><p>　　Status StackEmpty(Stack S){//判斷順序棧S是否為空棧,是返回1，否返回0 </p><p>　　return S.top==S.base; </p><p>　　}/

113、/StackIsEmpty</p><p>　　Status Push(Stack &S,SElemType e){ //入棧 </p><p>　　if(S.top-S.base >= S.stacksize){</p><p>　　if(!(S.base=(SElemType *)realloc(S.base,(STACK_INIT_SIZE +

114、 STACKINCREMENT)*sizeof(SElemType)))){</p><p>　　printf("內(nèi)存分配失?。n");</p><p>　　exit(OVERFLOW);</p><p><b>　　} </b></p><p>　　S.top = S.base + S.s

115、tacksize;</p><p>　　S.stacksize +=STACKINCREMENT;</p><p><b>　　}</b></p><p>　　*S.top++=e; </p><p><b>　　}//Push</b></p><p>　　Status P

116、op(Stack &S,SElemType &e){ //出棧 </p><p>　　if(StackEmpty(S)) </p><p>　　return ERROR; </p><p>　　e=*--S.top; </p><p>　　return OK; </p><p><b>　　

117、}//Pop</b></p><p>　　Status GetTop(Stack S,SElemType &e){</p><p>　　//若棧不空，用e返回順序棧S棧頂元素的值，并返回OK，否則返回ERRROR </p><p>　　if(StackEmpty(S)) </p><p>　　return ERROR;&

118、lt;/p><p>　　e = *(S.top-1); </p><p>　　return OK; </p><p><b>　　}//GetTop</b></p><p>　　//-----------------隊(duì)列的相關(guān)函數(shù)(供非遞歸層序遍歷使用)---------------</p><p>

119、;　　QueuePtr MallocQNode(){//為鏈隊(duì)列結(jié)點(diǎn)申請(qǐng)內(nèi)存的函數(shù)</p><p>　　QueuePtr p; //工作指針p </p><p>　　if(!(p=(QueuePtr)malloc(sizeof(QNode)))){ //申請(qǐng)結(jié)點(diǎn)的內(nèi)存空間，若失敗則提示并退出程序</p><p>　　printf("內(nèi)存分配失敗，程序即

120、將退出！\n");</p><p>　　exit(OVERFLOW);</p><p><b>　　}</b></p><p><b>　　return p;</b></p><p>　　} //MallocQNode </p><p>　　Status InitQ

121、ueue(Queue &Q) //初始化鏈隊(duì)列 </p><p>　　{ //構(gòu)建一個(gè)空隊(duì)列 Q</p><p>　　Q.front=Q.rear=MallocQNode(); //申請(qǐng)頭結(jié)點(diǎn)的內(nèi)存空間，并使隊(duì)頭和隊(duì)尾指針同時(shí)指向它 </p><p>　　Q.front->next=NULL; </p><p>　　

122、Q.front->data=0; //將隊(duì)長(zhǎng)設(shè)為0 </p><p>　　return OK;</p><p>　　}//InitQueue</p><p>　　Status DestoryQueue(Queue &Q){//銷毀隊(duì)列Q</p><p>　　while(Q.front){ //從頭結(jié)點(diǎn)開(kāi)始向后逐個(gè)釋放結(jié)

123、點(diǎn)內(nèi)存空間 </p><p>　　Q.rear=Q.front->next;</p><p>　　free(Q.front);</p><p>　　Q.front=Q.rear; </p><p><b>　　}//while</b></p><p>　　printf("鏈隊(duì)列已成

124、功銷毀！\n");</p><p>　　return OK;</p><p>　　}//DestoryQueue</p><p>　　Status QueueEmpty(Queue Q){ //若Q為空隊(duì)列，則返回OK;否則返回ERROR</p><p>　　if(Q.rear==Q.front) //隊(duì)列為空的標(biāo)志 </

125、p><p>　　return OK; </p><p>　　return ERROR; </p><p>　　}//QueueEmpty</p><p>　　Status EnQueue(Queue &Q,QElemType e){</p><p>　　//插入元素e為Q的新的隊(duì)尾元素</p><

126、;p>　　QueuePtr p=MallocQNode(); </p><p>　　p->data=e;</p><p>　　p->next=NULL;</p><p>　　Q.rear->next=p;</p><p><b>　　Q.rear=p;</b></p><p&g

127、t;　　Q.front->data++; //隊(duì)長(zhǎng)+1 </p><p>　　return OK; </p><p>　　}//EnQueue</p><p>　　Status DeQueue(Queue &Q,QElemType &e)</p><p>　　{ //若隊(duì)列不空,則刪除Q的隊(duì)頭元素,用e返回其值,并

128、返回OK,否則返回ERROR</p><p>　　if(QueueEmpty(Q)) </p><p>　　return ERROR;</p><p>　　QueuePtr p= Q.front->next;</p><p>　　e = p->data;</p><p>　　Q.front->next

129、 = p->next;</p><p>　　if(Q.rear==p)</p><p>　　Q.rear=Q.front;</p><p><b>　　free(p);</b></p><p>　　Q.front->data--; //隊(duì)長(zhǎng)-1 </p><p>　　return O

130、K; </p><p>　　}//DeQueue</p><p><b>　　主函數(shù)</b></p><p>　　int main(int argc,char *argv[]){</p><p>　　printf("------------------------ 樹(shù)的應(yīng)用 ----------------

131、---------\n");</p><p>　　BiTree T=NULL; //聲明一棵二叉樹(shù)</p><p>　　CSTree CT=NULL; //聲明一棵普通樹(shù)</p><p>　　printf(" -----------------樹(shù)的建立---------------- \n"