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

1、*大學(xué)電子與信息工程學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 ( 20102011年度第一學(xué)期)課程名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 題 目： 建立二叉樹(shù)并求指定結(jié)點(diǎn)路徑 院 系： 電信學(xué)院計(jì)算機(jī)系 班 級(jí)： 計(jì)算機(jī)08本（1） 姓 名： * 學(xué) 號(hào)： * 指導(dǎo)教師： * 成 績(jī)： 2010 年 12月 4日成 績(jī) 評(píng) 定一、 指導(dǎo)教師評(píng)語(yǔ)二、 成績(jī)成績(jī)備注 指導(dǎo)教師： 日 期： 年 月 日題目建立二叉樹(shù)并求指定結(jié)點(diǎn)路徑問(wèn)題描述要求能夠按先序遍歷的次序輸入二叉樹(shù)的各個(gè)結(jié)點(diǎn)，并能夠輸出中序遍歷的序列，以及指定結(jié)點(diǎn)的路徑基本要求分別建立二叉樹(shù)存儲(chǔ)結(jié)構(gòu)的輸入函數(shù)、輸出中序遍歷的函數(shù)，以及輸出指定結(jié)點(diǎn)路徑的函數(shù)課程設(shè)計(jì)的需求

2、和規(guī)格說(shuō)明 1、定義二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)中設(shè)置三個(gè)域，即值域、左指針域、右指針域。要建立二叉樹(shù)t的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，即建立二叉鏈表。根據(jù)輸入二叉樹(shù)結(jié)點(diǎn)的形式不同，建立的方法也不同，本系統(tǒng)采用先序序列遞歸建立二叉樹(shù)，建立如下圖所示的二叉樹(shù)。應(yīng)該在程序運(yùn)行窗口的主控菜單后，先選擇“1”并回車，緊接著在程序運(yùn)行窗口中提示信息“輸入二叉樹(shù)的先序序列結(jié)點(diǎn)值:”之后，采用以下字符序列：abcdegf （以替代空格）作為建立二叉樹(shù)t的輸入字符序列并回車，窗口出現(xiàn)：二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)建立完成! 圖1 二叉樹(shù)的圖形結(jié)構(gòu)2、二叉樹(shù)的遍歷。本系統(tǒng)采用非遞歸中序遍歷算法進(jìn)行中序遍歷，這意味著遍歷右子樹(shù)時(shí)不再需要保

3、存當(dāng)前層的根指針，可直接修改棧頂記錄中的指針即可。需要在程序運(yùn)行窗口的主控菜單中選擇“2” 并回車，程序運(yùn)行窗口會(huì)出現(xiàn)以下中序遍歷序列：該二叉樹(shù)的中序遍歷序列是: cbegdfa 3、求二叉樹(shù)的指定結(jié)點(diǎn)路徑。在程序運(yùn)行窗口的主控菜單中選擇“3” 并回車，在程序運(yùn)行窗口中提示信息“輸入要求路徑的結(jié)點(diǎn)值:”輸入“g” 并回車，會(huì)得到結(jié)果為：abdeg如果輸入“i” 并回車，會(huì)得到結(jié)果為：沒(méi)有要求的結(jié)點(diǎn)！ 設(shè)計(jì)設(shè)計(jì)思想：我們知道，在二叉樹(shù)上無(wú)論采用哪種遍歷方法，都能夠訪問(wèn)遍樹(shù)中的所有結(jié)點(diǎn)。由于訪問(wèn)結(jié)點(diǎn)的順序不同，前序遍歷和中序遍歷都很難達(dá)到設(shè)計(jì)的要求；但采用后序遍歷二叉樹(shù)是可行的，因?yàn)楹笮虮闅v是最后

4、訪問(wèn)根結(jié)點(diǎn)，按這個(gè)順序?qū)⒃L問(wèn)過(guò)的結(jié)點(diǎn)存儲(chǔ)到一個(gè)順序棧中，然后再輸出即可。因此，我們可以非遞歸地后序遍歷二叉樹(shù)t，當(dāng)后序遍歷訪問(wèn)到結(jié)點(diǎn)*p時(shí)，此時(shí)棧中存放的所有結(jié)點(diǎn)均為給定結(jié)點(diǎn)*p的祖先，而由這些祖先便構(gòu)成了一條從根結(jié)點(diǎn)到結(jié)點(diǎn)*p之間的路徑。設(shè)計(jì)表示：為實(shí)現(xiàn)上述的設(shè)計(jì)思想，首先要定義二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，我們采用二叉鏈表的方式，相應(yīng)的類型說(shuō)明為：typedef char datatype;typedef struct nodedatatype data;struct node *lchild,*rchild;bintnode,*bintree;函數(shù)調(diào)用關(guān)系如下圖所示：main（）createbi

5、treeinordernodepath函數(shù)接口說(shuō)明:status createbitree(bintree &bt) /*按照先序遍歷次序遞歸建立二叉樹(shù)*/status inorder(bintree bt) /*二叉樹(shù)非遞歸中序遍歷算法*/void nodepath(bintree bt,bintnode *ch) /*求二叉樹(shù)根結(jié)點(diǎn)到給定結(jié)點(diǎn)*p的路徑*/實(shí)現(xiàn)注釋： 二叉樹(shù)的創(chuàng)建模塊: 按照先序遍歷次序遞歸建立二叉樹(shù),通過(guò)讀入的字符，分配存儲(chǔ)空間生成新結(jié)點(diǎn)后再逐個(gè)構(gòu)建根結(jié)點(diǎn)、左子樹(shù)和右子樹(shù)。程序代碼可參見(jiàn)參考文獻(xiàn)1p131算法6.4語(yǔ)句注釋見(jiàn)附錄代碼。 二叉樹(shù)中序遍歷模塊：采用非遞歸中序遍

6、歷算法，先逐步掃描二叉樹(shù)的左子樹(shù)，并壓入堆棧，如果棧不為空，左子樹(shù)為空，則彈出棧頂?shù)囊粋€(gè)元素并輸出。然后再掃描右子樹(shù)，然后再重復(fù)上面的步驟掃描該分支的左子樹(shù)，直至整棵二叉樹(shù)都掃描完成。此時(shí)輸出的序列便是該二叉樹(shù)的中序遍歷序列。語(yǔ)句注釋見(jiàn)代碼。 二叉樹(shù)指定結(jié)點(diǎn)路徑模塊：該模塊由nodepath、findbt、findx三個(gè)函數(shù)體構(gòu)成，main函數(shù)通過(guò)先調(diào)用findx 函數(shù)來(lái)查找結(jié)點(diǎn)，findx又通過(guò)逐步調(diào)用findbt函數(shù)遍歷查找結(jié)點(diǎn)的路徑，最后main函數(shù)再通過(guò)調(diào)用nodepath函數(shù)得到給定結(jié)點(diǎn)的路徑。該模塊需定義全局變量p和found以方便查找，否則容易出錯(cuò)，出錯(cuò)情況見(jiàn)調(diào)試報(bào)告。語(yǔ)句注釋見(jiàn)

7、代碼。調(diào)試報(bào)告 編程的最初階段，在case3語(yǔ)句中，缺少p=null;和found=0;兩個(gè)語(yǔ)句，得到的結(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）的地址相同，導(dǎo)致結(jié)果出錯(cuò)，所以應(yīng)在ch1=getchar();獲取新結(jié)點(diǎn)之后令p指針為空。在編程的后期，暫未考慮到found為全局變量，因此即使加上p=null;這條語(yǔ)句，得到的結(jié)果為第一次查找g結(jié)點(diǎn)正確、第二次查找i結(jié)點(diǎn)也正確，此后繼續(xù)查找不管是否存在的結(jié)點(diǎn)，其結(jié)果均與第二次的結(jié)果一致，顯然此為錯(cuò)誤的結(jié)果。經(jīng)過(guò)調(diào)試判斷后，得出found為全局變量，

8、第一次查找存在的結(jié)點(diǎn)時(shí)，found被賦值成1，所以導(dǎo)致接下來(lái)的查找過(guò)程中在findbt函數(shù)中：if(bt!=null) & !found)，因?yàn)閒ound已被賦值為1，所以，直接跳出查找退出findbt函數(shù)，也就是沒(méi)進(jìn)行查找，顯示的結(jié)果均為沒(méi)有找到！實(shí)際上根本就沒(méi)進(jìn)行查找！所以應(yīng)補(bǔ)充語(yǔ)句found=0；以恢復(fù)初值。到此，程序正確！附錄a.源程序清單和結(jié)果：#include #include #define num 100#define ok 1typedef int status;typedef char datatype;typedef struct nodedatatype data;st

9、ruct node*lchild,*rchild;bintnode,*bintree;int found;bintnode *p;status createbitree(bintree &bt)/按照先序遍歷次序遞歸建立二叉樹(shù),參見(jiàn)教材p131算法6.4/abcdegf 對(duì)應(yīng)于教材p127圖6.8(b)char ch;printf(ch=);scanf(%c,&ch); getchar(); if (ch=)bt=null;else bt=(bintnode *)malloc(sizeof(bintnode); bt-data=ch; /生成根結(jié)點(diǎn) createbitree(bt-lchild

10、); /構(gòu)造左子樹(shù) createbitree(bt-rchild); /構(gòu)造右子樹(shù)return ok;status inorder(bintree bt)/二叉樹(shù)非遞歸中序遍歷算法 bintnode *p,*s100; /定義數(shù)組棧 int i=0; /初始化棧 p=bt; do while(p!=null) /掃描根結(jié)點(diǎn)及其所有的左結(jié)點(diǎn)并將其地址入棧 si+=p; p=p-lchild; if (i0) /判斷棧是否為空 p=s-i; /出棧 printf(%ct,p-data); /訪問(wèn)結(jié)點(diǎn) p=p-rchild; /掃描右子樹(shù) while(i0|p!=null);return ok;vo

11、id nodepath(bintree bt,bintnode *ch)/求二叉樹(shù)根結(jié)點(diǎn)到給定結(jié)點(diǎn)*p的路徑typedef enum false,trueboolean;bintnode *stacknum; /定義棧int tagnum;int i,top;boolean find;bintnode *s;find=false;top=0;s=bt;dowhile(s!=null)/掃描左子樹(shù)top+;stacktop=s;tagtop=0;s=s-lchild;if(top0)s=stacktop;if(tagtop=1)if(s=ch)/找到ch,則顯示從根結(jié)點(diǎn)到ch的路徑for(i=1

12、;i%c,stacki-data);find=true;elsetop-;s=stacktop;/endifif(top0 & !find)if(tagtop!=1)s=s-rchild; /掃描右子樹(shù)tagtop=1;elses=null;/endif/endlifwhile(!find & top!=0);void findbt(bintree bt,datatype x)if(bt!=null) & !found)if(bt-data=x)p=bt;found=1;elsefindbt(bt-lchild,x); /遍歷查找左子樹(shù)findbt(bt-rchild,x); /遍歷查找右子樹(shù)

13、bintnode *findx(bintree bt,datatype x)/按給定值查找結(jié)點(diǎn)int found=0; /用found來(lái)作為是否查找到的標(biāo)志bintree p=null; /置空指針findbt(bt,x);return(p);void main()bintree bt;char ch1;int xz=1;while(xz)printf(建立二叉樹(shù)并求指定結(jié)點(diǎn)路徑n);printf( 歡 迎 光 臨n);printf(=n);printf(1.建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) n);printf(n);printf(2.求解二叉樹(shù)的中序遍歷 n);printf(n);printf(3.求二

14、叉樹(shù)指定結(jié)點(diǎn)的路徑 n);printf(n);printf(0. 退 出 系 統(tǒng) n);printf(=n);printf(請(qǐng)選擇:(0-3) n);scanf(%d,&xz);getchar();switch(xz) /輸入:abcdegf case 1:printf(輸入二叉樹(shù)的先序序列結(jié)點(diǎn)值:n); createbitree(bt); printf(二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)建立完成! n); printf(n); break;/輸出: cbegdfacase 2:printf(該二叉樹(shù)的中序遍歷序列是:n);inorder(bt);printf(n);break;/查找指定結(jié)點(diǎn)路徑case 3:printf(路徑的節(jié)點(diǎn)值是：n);ch1=getchar();p=null;found=0;findx(bt,ch1);if(p!=null)nodepath(bt,p);elseprintf(沒(méi)有要求的節(jié)點(diǎn)!n);printf(n);break;/ switch/ while 實(shí)驗(yàn)結(jié)果截屏：圖1.創(chuàng)建