數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--- 建立二叉樹并求指定結(jié)點(diǎn)路徑

1、<p><b>　　電子與信息工程學(xué)院</b></p><p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告</p><p>　　( 2010——2011年度第一學(xué)期)</p><p>　　課程名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) </p><p>　　題 目： 建立二叉樹并求指定結(jié)點(diǎn)路徑 </p>

2、;<p>　　院 系： 電信學(xué)院計(jì)算機(jī)系 </p><p>　　班 級： 計(jì)算機(jī)08本（1） </p><p>　　姓 名： ** </p><p>　　學(xué) 號： ** </p>&l

3、t;p>　　指導(dǎo)教師： ** </p><p>　　成 績： </p><p>　　2010 年 12月 4日</p><p>　　[題目]建立二叉樹并求指定結(jié)點(diǎn)路徑</p><p>　　[問題描述]要求能夠按先序遍歷的次序輸入二

4、叉樹的各個(gè)結(jié)點(diǎn)，并能夠輸出中序遍歷的序列，以及指定結(jié)點(diǎn)的路徑</p><p>　　[基本要求]分別建立二叉樹存儲(chǔ)結(jié)構(gòu)的輸入函數(shù)、輸出中序遍歷的函數(shù)，以及輸出指定結(jié)點(diǎn)路徑的函數(shù)</p><p>　　課程設(shè)計(jì)的需求和規(guī)格說明</p><p>　　1、定義二叉樹的存儲(chǔ)結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)中設(shè)置三個(gè)域，即值域、左指針域、右指針域。要建立二叉樹T的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，即建立二叉鏈表。根據(jù)

5、輸入二叉樹結(jié)點(diǎn)的形式不同，建立的方法也不同，本系統(tǒng)采用先序序列遞歸建立二叉樹，建立如下圖所示的二叉樹。應(yīng)該在程序運(yùn)行窗口的主控菜單后，先選擇“1”并回車，緊接著在程序運(yùn)行窗口中提示信息“輸入二叉樹的先序序列結(jié)點(diǎn)值:”之后，采用以下字符序列：ABC@@DE@G@@F@@@ （以@替代空格）作為建立二叉樹T的輸入字符序列并回車，窗口出現(xiàn)：二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)建立完成! </p><p>　　2、二叉樹的遍歷。本系統(tǒng)

6、采用非遞歸中序遍歷算法進(jìn)行中序遍歷，這意味著遍歷右子樹時(shí)不再需要保存當(dāng)前層的根指針，可直接修改棧頂記錄中的指針即可。需要在程序運(yùn)行窗口的主控菜單中選擇“2” 并回車，程序運(yùn)行窗口會(huì)出現(xiàn)以下中序遍歷序列：該二叉樹的中序遍歷序列是: CBEGDFA</p><p>　　3、求二叉樹的指定結(jié)點(diǎn)路徑。在程序運(yùn)行窗口的主控菜單中選擇“3” 并回車，在程序運(yùn)行窗口中提示信息“輸入要求路徑的結(jié)點(diǎn)值:”輸入“G” 并回車，會(huì)得到

7、結(jié)果為：</p><p>　　→A→B→D→E→G如果輸入“I” 并回車，會(huì)得到結(jié)果為：沒有要求的結(jié)點(diǎn)！ </p><p><b>　　設(shè)計(jì)</b></p><p><b>　　設(shè)計(jì)思想：</b></p><p>　　我們知道，在二叉樹上無論采用哪種遍歷方法，都能夠訪問遍樹中的所有結(jié)點(diǎn)。由于訪問結(jié)點(diǎn)

8、的順序不同，前序遍歷和中序遍歷都很難達(dá)到設(shè)計(jì)的要求；但采用后序遍歷二叉樹是可行的，因?yàn)楹笮虮闅v是最后訪問根結(jié)點(diǎn)，按這個(gè)順序?qū)⒃L問過的結(jié)點(diǎn)存儲(chǔ)到一個(gè)順序棧中，然后再輸出即可。因此，我們可以非遞歸地后序遍歷二叉樹T，當(dāng)后序遍歷訪問到結(jié)點(diǎn)*p時(shí)，此時(shí)棧中存放的所有結(jié)點(diǎn)均為給定結(jié)點(diǎn)*p的祖先，而由這些祖先便構(gòu)成了一條從根結(jié)點(diǎn)到結(jié)點(diǎn)*p之間的路徑。</p><p><b>　　設(shè)計(jì)表示：</b><

9、;/p><p>　　為實(shí)現(xiàn)上述的設(shè)計(jì)思想，首先要定義二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，我們采用二叉鏈表的方式，相應(yīng)的類型說明為：</p><p>　　typedef char DataType;</p><p>　　typedef struct node{</p><p>　　DataType data;</p><p>　　stru

10、ct node *lchild,*rchild;</p><p>　　}BinTNode,*BinTree;</p><p>　　函數(shù)調(diào)用關(guān)系如下圖所示：</p><p><b>　　函數(shù)接口說明:</b></p><p>　　Status CreateBiTree(BinTree &bt) /*按照先序遍歷次序

11、遞歸建立二叉樹*/</p><p>　　Status Inorder(BinTree bt) /*二叉樹非遞歸中序遍歷算法*/</p><p>　　Void NodePath(BinTree bt,BinTNode *ch) /*求二叉樹根結(jié)點(diǎn)到給定結(jié)點(diǎn)*p的路徑*/</p><p><b>　　實(shí)現(xiàn)注釋：</b></p><

12、;p>　　二叉樹的創(chuàng)建模塊: 按照先序遍歷次序遞歸建立二叉樹,通過讀入的字符，分配存儲(chǔ)空間生成新結(jié)點(diǎn)后再逐個(gè)構(gòu)建根結(jié)點(diǎn)、左子樹和右子樹。程序代碼可參見參考文獻(xiàn)[1]P131算法6.4語句注釋見附錄代碼。</p><p>　　二叉樹中序遍歷模塊：采用非遞歸中序遍歷算法，先逐步掃描二叉樹的左子樹，并壓入堆棧，如果棧不為空，左子樹為空，則彈出棧頂?shù)囊粋€(gè)元素并輸出。然后再掃描右子樹，然后再重復(fù)上面的步驟掃描該分支的

13、左子樹，直至整棵二叉樹都掃描完成。此時(shí)輸出的序列便是該二叉樹的中序遍歷序列。語句注釋見代碼。</p><p>　　二叉樹指定結(jié)點(diǎn)路徑模塊：該模塊由NodePath、FindBT、Findx三個(gè)函數(shù)體構(gòu)成，main函數(shù)通過先調(diào)用Findx 函數(shù)來查找結(jié)點(diǎn)，F(xiàn)indx又通過逐步調(diào)用FindBT函數(shù)遍歷查找結(jié)點(diǎn)的路徑，最后main函數(shù)再通過調(diào)用NodePath函數(shù)得到給定結(jié)點(diǎn)的路徑。該模塊需定義全局變量p和found以

14、方便查找，否則容易出錯(cuò)，出錯(cuò)情況見調(diào)試報(bào)告。語句注釋見代碼。</p><p><b>　　調(diào)試報(bào)告</b></p><p>　　編程的最初階段，在case3語句中，缺少p=NULL;和found=0;兩個(gè)語句，得到的結(jié)果不管查找的結(jié)點(diǎn)是否存在，其結(jié)果均顯示為G結(jié)點(diǎn)的路徑，后經(jīng)設(shè)置斷點(diǎn)、調(diào)試，發(fā)現(xiàn)p指針在更換查找結(jié)點(diǎn)時(shí)，指向的地址始終與第一個(gè)查找的結(jié)點(diǎn)（即G）的地址相同

15、，導(dǎo)致結(jié)果出錯(cuò)，所以應(yīng)在ch1=getchar();獲取新結(jié)點(diǎn)之后令p指針為空。</p><p>　　在編程的后期，暫未考慮到found為全局變量，因此即使加上p=NULL;這條語句，得到的結(jié)果為第一次查找G結(jié)點(diǎn)正確、第二次查找I結(jié)點(diǎn)也正確，此后繼續(xù)查找不管是否存在的結(jié)點(diǎn)，其結(jié)果均與第二次的結(jié)果一致，顯然此為錯(cuò)誤的結(jié)果。經(jīng)過調(diào)試判斷后，得出found為全局變量，第一次查找存在的結(jié)點(diǎn)時(shí)，found被賦值成1，所以導(dǎo)

16、致接下來的查找過程中在FindBT函數(shù)中：if((bt!=NULL) && !found)，因?yàn)閒ound已被賦值為1，所以，直接跳出查找退出FindBT函數(shù)，也就是沒進(jìn)行查找，顯示的結(jié)果均為沒有找到！實(shí)際上根本就沒進(jìn)行查找！所以應(yīng)補(bǔ)充語句found=0；以恢復(fù)初值。到此，程序正確！</p><p><b>　　附錄</b></p><p>　　a.源

17、程序清單和結(jié)果：</p><p>　　#include <stdio.h></p><p>　　#include <stdlib.h></p><p>　　#define num 100</p><p>　　#define OK 1</p><p>　　typedef int Status;&l

18、t;/p><p>　　typedef char DataType;</p><p>　　typedef struct node{</p><p>　　DataType data;</p><p>　　struct node</p><p>　　*lchild,*rchild;</p><p>　　}

19、BinTNode,*BinTree;</p><p>　　int found;</p><p>　　BinTNode *p;</p><p>　　Status CreateBiTree(BinTree &bt)</p><p>　　{//按照先序遍歷次序遞歸建立二叉樹,參見教材P131算法6.4</p><p>

20、;　　//ABC@@DE@G@@F@@@ 對應(yīng)于教材P127圖6.8(b)</p><p><b>　　char ch;</b></p><p>　　printf("ch=");</p><p>　　scanf("%c",&ch);</p><p>　　getchar()

21、;</p><p>　　if (ch=='@')bt=NULL;</p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　bt=(BinTNode *)malloc(sizeof(BinTNode));</p><

22、;p>　　bt->data=ch; //生成根結(jié)點(diǎn)</p><p>　　CreateBiTree(bt->lchild); //構(gòu)造左子樹</p><p>　　CreateBiTree(bt->rchild); //構(gòu)造右子樹</p><p><b>　　}</b></p><p>　　r

23、eturn OK;</p><p><b>　　}</b></p><p>　　Status Inorder(BinTree bt)</p><p>　　{//二叉樹非遞歸中序遍歷算法</p><p>　　BinTNode *p,*s[100]; //定義數(shù)組棧</p><p>　　in

24、t i=0; //初始化棧 </p><p><b>　　p=bt;</b></p><p><b>　　do</b></p><p>　　{ while(p!=NULL) </p><p>　　//掃描根結(jié)點(diǎn)及其所有的左結(jié)點(diǎn)并將其地址入棧</p>&l

25、t;p>　　{ s[i++]=p;</p><p>　　p=p->lchild;</p><p><b>　　}</b></p><p>　　if (i>0) //判斷棧是否為空</p><p>　　{ p=s[--i]; //出棧<

26、;/p><p>　　printf("%c\t",p->data); //訪問結(jié)點(diǎn)</p><p>　　p=p->rchild; //掃描右子樹 </p><p><b>　　}</b></p><p>　　}while(i>0||p!=NULL);</p>&l

27、t;p>　　return OK;</p><p><b>　　}</b></p><p>　　void NodePath(BinTree bt,BinTNode *ch)</p><p>　　{//求二叉樹根結(jié)點(diǎn)到給定結(jié)點(diǎn)*p的路徑</p><p>　　typedef enum {FALSE,TRUE}boolea

28、n;</p><p>　　BinTNode *stack[num]; //定義棧</p><p>　　int tag[num];</p><p>　　int i,top;</p><p>　　boolean find;</p><p>　　BinTNode *s;</p><p>　　find=

29、FALSE;</p><p><b>　　top=0;</b></p><p><b>　　s=bt;</b></p><p><b>　　do</b></p><p><b>　　{</b></p><p>　　while(s!=

30、NULL)</p><p><b>　　{//掃描左子樹</b></p><p><b>　　top++;</b></p><p>　　stack[top]=s;</p><p>　　tag[top]=0;</p><p>　　s=s->lchild;</p>

31、;<p><b>　　}</b></p><p><b>　　if(top>0)</b></p><p><b>　　{</b></p><p>　　s=stack[top];</p><p>　　if(tag[top]==1)</p><

32、;p><b>　　{</b></p><p><b>　　if(s==ch)</b></p><p>　　{//找到ch,則顯示從根結(jié)點(diǎn)到ch的路徑</p><p>　　for(i=1;i<=top;i++)</p><p>　　printf("->%c",st

33、ack[i]->data);</p><p>　　find=TRUE;</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　top--;</b></p><p>　　s=stack[to

34、p];</p><p><b>　　}//endif</b></p><p>　　if(top>0 && !find)</p><p><b>　　{</b></p><p>　　if(tag[top]!=1)</p><p><b>　　{&

35、lt;/b></p><p>　　s=s->rchild; //掃描右子樹</p><p>　　tag[top]=1;</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　s=NULL;<

36、;/b></p><p><b>　　}//endif</b></p><p><b>　　}//endlif</b></p><p>　　}while(!find && top!=0);</p><p><b>　　}</b></p>&l

37、t;p>　　void FindBT(BinTree bt,DataType x)</p><p><b>　　{</b></p><p>　　if((bt!=NULL) && !found)</p><p><b>　　{</b></p><p>　　if(bt->dat

38、a==x)</p><p>　　{p=bt;found=1;}</p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　FindBT(bt->lchild,x); //遍歷查找左子樹</p><p>　　FindBT(b

39、t->rchild,x); //遍歷查找右子樹</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　BinTNode *Findx(BinTree bt,DataType x)<

40、/p><p>　　{//按給定值查找結(jié)點(diǎn)</p><p>　　int found=0; //用found來作為是否查找到的標(biāo)志</p><p>　　BinTree p=NULL; //置空指針</p><p>　　FindBT(bt,x);</p><p>　　return(p);</p><p>

41、<b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p><p>　　BinTree bt;</p><p><b>　　char ch1;</b></p><p><b>　　int

42、xz=1;</b></p><p><b>　　while(xz)</b></p><p><b>　　{</b></p><p>　　printf("建立二叉樹并求指定結(jié)點(diǎn)路徑\n");</p><p>　　printf(" 歡 迎 光 臨\

43、n");</p><p>　　printf("===========================\n");</p><p>　　printf("1.建立二叉樹的存儲(chǔ)結(jié)構(gòu) \n");</p><p>　　printf("\n");</p><p>　　printf(&qu

44、ot;2.求解二叉樹的中序遍歷 \n");</p><p>　　printf("\n");</p><p>　　printf("3.求二叉樹指定結(jié)點(diǎn)的路徑 \n");</p><p>　　printf("\n");</p><p>　　printf("0. 退

45、 出 系 統(tǒng) \n");</p><p>　　printf("===========================\n");</p><p>　　printf("請選擇:(0-3) \n");</p><p>　　scanf("%d",&xz);</p><p&

46、gt;　　getchar();</p><p>　　switch(xz)</p><p>　　{ //輸入:ABC@@DE@G@@F@@@ </p><p>　　case 1:printf("輸入二叉樹的先序序列結(jié)點(diǎn)值:\n");</p><p>　　CreateBiTree(bt);</p><p&g

47、t;　　printf("二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)建立完成! \n");</p><p>　　printf("\n");</p><p><b>　　break;</b></p><p>　　//輸出: CBEGDFA</p><p>　　case 2:printf("該二叉樹

48、的中序遍歷序列是:\n");</p><p>　　Inorder(bt);</p><p>　　printf("\n");</p><p><b>　　break;</b></p><p>　　//查找指定結(jié)點(diǎn)路徑</p><p>　　case 3:printf(&q

49、uot;路徑的節(jié)點(diǎn)值是：\n");</p><p>　　ch1=getchar();</p><p><b>　　p=NULL;</b></p><p><b>　　found=0;</b></p><p>　　Findx(bt,ch1);</p><p>　　if

50、(p!=NULL)</p><p>　　NodePath(bt,p);</p><p><b>　　else</b></p><p>　　printf("沒有要求的節(jié)點(diǎn)!\n");</p><p>　　printf("\n");</p><p><b&

51、gt;　　break;</b></p><p>　　}// switch</p><p><b>　　}// while</b></p><p><b>　　} </b></p><p><b>　　實(shí)驗(yàn)結(jié)果截屏：</b></p><p>&

52、lt;b>　　b.參考文獻(xiàn)：</b></p><p>　　[1]嚴(yán)蔚敏,吳偉民數(shù)據(jù)結(jié)構(gòu)(C語言版).北京:清華大學(xué)出版社,2006.7</p><p>　　[2]嚴(yán)蔚敏,吳偉民等.數(shù)據(jù)結(jié)構(gòu)題集(C語言版).北京:清華大學(xué)出版社,2005.11</p><p>　　[3]蘇仕華等.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì).北京:機(jī)械工業(yè)出版社,2006.6</p>