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

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁數(shù)：28 大?。?35.00KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

已閱讀1頁，還剩27頁未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

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

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

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

4、的含有空格的先根次序序列，并按回車結(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é)果

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

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

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

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

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

10、160;　　數(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}≠

11、Φ，則存在D-{root}的一個(gè)劃分D1,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&g

12、t;,?,<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

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

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

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

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

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

18、sign(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)。&

19、#160;　　操作結(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)，則返回它的最

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

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

22、p>　　初始條件：樹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ù)。 <p

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

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

25、ot，它在關(guān)系H下無前驅(qū)； 　?。?）若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={&l

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

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

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

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

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

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

32、p>　　初始條件：二叉樹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無左孩子，則返回“

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

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

35、 　　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的右子樹。 <p&

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

37、：二叉樹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ù)。

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

39、t一次且僅一次。一旦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()失敗，則操作失敗。 </p&g

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

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

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

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

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

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

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

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

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

49、b>　　CT=NULL;　　else{　　if(!(CT=(CSNode *)malloc(sizeof(CSNode)))){　　printf("內(nèi)存分配失?。n");　　exit(O

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

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

52、　　樹和二叉樹的轉(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)換過程的實(shí)質(zhì)是按照二叉樹的定義將二叉鏈表解釋為二叉樹的過程。　　Sta

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

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

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

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

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

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

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

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

61、e)，通過主函數(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-

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

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

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

65、Traverse(T->lchild,Visit)) //訪問左子樹　　if(PreOrderTraverse(T->rchild,Visit)) //訪問右子樹　　return OK;　　return ERROR;　　} //if<

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

81、//遍歷右子樹 　　}//else　　}//while　　return OK;　　} //InOrderTraverse1　　Status PostOrd

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

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

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

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

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

87、gt;rchild;　　break;　　}//else　　}//while　　}//while　　retur

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

110、("內(nèi)存分配失??！\n");　　exit(OVERFLOW);　　} 　　S.top=S.base;　　S.stacksize=STACK_INIT_SIZE;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

眾賞文庫> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

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

文檔簡介

溫馨提示

最新文檔

評(píng)論

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

文檔簡介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載