構(gòu)建一棵二叉排序樹的C程序的設(shè)計(jì)

1、學(xué)號(hào)10212815213武漢華夏理工學(xué)院課程設(shè)計(jì)報(bào)告書課程名稱：數(shù)據(jù)結(jié)構(gòu)題 目：構(gòu)建一棵二叉排序樹的 C程序的設(shè)計(jì) 系 名：信息工程學(xué)院專業(yè)班級(jí)： 軟件1152姓 名：李天宇指導(dǎo)教師：王緒梅2016年_6月27日課程設(shè)計(jì)任務(wù)書設(shè)計(jì)題目：構(gòu)建一棵二叉排序樹的 C程序的設(shè)計(jì)設(shè)計(jì)目的1. 鞏固和加深課堂所學(xué)知識(shí)、學(xué)會(huì)分析研究數(shù)據(jù)對象的特性及數(shù)據(jù)的組織方法；2. 選擇的合適數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)以及相應(yīng)操作，實(shí)現(xiàn)二叉排序樹的基本操作；3. 提高程序設(shè)計(jì)能力、加強(qiáng)查閱、運(yùn)用資料的能力、算法分析與程序設(shè)計(jì)素質(zhì)培 養(yǎng)；設(shè)計(jì)任務(wù)（在規(guī)定的時(shí)間內(nèi)完成下列任務(wù)）問題描述建立一棵二叉排序樹，并完成插入結(jié)點(diǎn)、按值

2、查找結(jié)點(diǎn)位置和顯示等功能?；疽蟀炊鏄涞牟迦敕椒?，形成二叉排序樹主模塊給出操作菜單，用函數(shù)實(shí)現(xiàn)不同功能在主函數(shù)中調(diào)用算法提示首先設(shè)定二叉樹的二叉鏈表的存儲(chǔ)結(jié)構(gòu)：在建立二叉樹時(shí)將每一個(gè)結(jié)點(diǎn)按左右子樹的規(guī)定形成掛到樹上；按二叉排序樹的特點(diǎn)進(jìn)行查找，按中序遍歷的方法顯示樹中結(jié)占八、具體要完成的任務(wù)是：A. 編制完成上述問題的 C語言程序、進(jìn)行程序調(diào)試并能得出正確的運(yùn)行結(jié)果。B. 寫出規(guī)范的課程設(shè)計(jì)報(bào)告書；時(shí)間安排：6月27日-7月1日第一天布置題目，確定任務(wù)、查找相關(guān)資料第二天第四天功能分析，編寫程序，調(diào)試程序、運(yùn)行系統(tǒng)；第五天程序驗(yàn)收、答辯；撰寫設(shè)計(jì)報(bào)告。具體要求1. 課程設(shè)計(jì)報(bào)告按統(tǒng)一通用格

3、式書寫，具體內(nèi)容如下： 設(shè)計(jì)任務(wù)與要求 總體方案與說明 軟件主要模塊的流程圖 源程序清單與注釋 問題分析與解決方案（包括調(diào)式報(bào)告，即在調(diào)式過程中遇到的主要問題、解決方法及改進(jìn)設(shè)想）小結(jié)與體會(huì)附錄： 源程序（必須有簡單注釋） 使用說明 參考資料2 每位學(xué)生應(yīng)獨(dú)立完成各自的任務(wù)且每天至少在設(shè)計(jì)室工作半天；指 導(dǎo) 教 師 簽 名：二戸2016年6月25日教研室主任（或責(zé)任教師）簽名：邱珊2016年6月25日目 錄1實(shí)驗(yàn)?zāi)康呐c目標(biāo)42. 問題分析53. 總體設(shè)計(jì)64. 具體設(shè)計(jì)84.1遞歸查找算法84.2非遞歸查找算法 94.3插入算法1仁4.4二叉排序樹的生成算法 1.34.5中序遍歷算法 1.4.

4、4.6刪除算法1.5.4.7主函數(shù)1.6.4.8注意事項(xiàng)：.1.8.5. 運(yùn)行環(huán)境1.8.6. 上機(jī)調(diào)試18.6.1語法錯(cuò)誤及修改.86.2程序輸出調(diào)整：21.6.3時(shí)間和空間性能分析： 217. 測試結(jié)果及分析 22.8. 用戶使用說明.3.1.9. 參考文獻(xiàn)31.附錄34.1實(shí)驗(yàn)?zāi)康呐c目標(biāo)一、目的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)是學(xué)習(xí)了數(shù)據(jù)結(jié)構(gòu)課后的一個(gè)綜合性實(shí)踐環(huán)節(jié)，是對 課程學(xué)習(xí)的綜合和補(bǔ)充。通過課程設(shè)計(jì)培養(yǎng)學(xué)生運(yùn)用已學(xué)過的理論和技能去分析和解決實(shí)際問題的能力、加強(qiáng)學(xué)生的實(shí)踐動(dòng)手能力和創(chuàng)新能力。二、目標(biāo)1、結(jié)合c和數(shù)據(jù)結(jié)構(gòu)的理論知識(shí)，按要求獨(dú)立設(shè)計(jì)方案，培養(yǎng)獨(dú)立分析和解決實(shí)際問題的能力。加強(qiáng)學(xué)生的實(shí)踐

5、動(dòng)手能力和創(chuàng)新能力。2、學(xué)會(huì)查閱資料，熟悉常用算法的用途與技巧。3、認(rèn)真撰寫課程設(shè)計(jì)報(bào)告，培養(yǎng)嚴(yán)謹(jǐn)?shù)淖黠L(fēng)和科學(xué)態(tài)度。2問題分析本次程序需要完成如下要求：首先輸入任一組數(shù)據(jù)，使之構(gòu)造成二叉排序樹，并 對其作中序遍歷，然后輸出遍歷后的數(shù)據(jù)序列；其次，該二叉排序樹能實(shí)現(xiàn)對數(shù) 據(jù)（即二叉排序樹的結(jié)點(diǎn)）的查找、插入和刪除等基本操作。實(shí)現(xiàn)本程序需要解決以下幾個(gè)問題：1、如何構(gòu)造二叉排序樹。2、如何通過中序遍歷輸出二叉排序樹。3、如何實(shí)現(xiàn)多種查找。4、如何實(shí)現(xiàn)插入刪除等操作。二叉排序樹的定義：其左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值。若其右子樹非空，則右子樹上所有結(jié)點(diǎn)的值大于根結(jié)點(diǎn)的值。其左右子

6、樹也分別為二叉排序樹。本問題的關(guān)鍵在于對于二叉排序樹的構(gòu)造。 根據(jù)上述二叉排序樹二叉排序樹的生成需要通過插入算法來實(shí)現(xiàn)：輸入（插入）的第一個(gè)數(shù)據(jù)即為根結(jié)點(diǎn)；繼續(xù)插入,當(dāng)插入的新結(jié)點(diǎn)的關(guān)鍵值小于根結(jié)點(diǎn)的值時(shí)就作為左孩子，當(dāng)插入的新結(jié)點(diǎn)的關(guān)鍵值大于根結(jié)點(diǎn)的值時(shí)就作為右孩子；在左右子樹中插入方法與整個(gè)二叉排序樹 相同。當(dāng)二叉排序樹建立完成后，要插入新的數(shù)據(jù)時(shí)，要先判斷已建立的二叉排 序樹序列中是否已有當(dāng)前插入數(shù)據(jù)。 因此，插入算法還要包括對數(shù)據(jù)的查找判斷 過程。本問題的難點(diǎn)在于二叉排序樹的刪除算法的實(shí)現(xiàn)。刪除前，首先要進(jìn)行查找，判斷給出的結(jié)點(diǎn)是否已存在于二叉排序樹之中； 在刪除時(shí)，為了保證刪除結(jié)點(diǎn)后

7、的 二叉樹仍為二叉排 序樹，要考慮各種情況，選擇正確的方法。刪除操作要分幾種情況討 論，在后面有介紹。3. 總體設(shè)計(jì)用二叉鏈表作為二叉排序樹的存儲(chǔ)結(jié)構(gòu)，其中key為結(jié)點(diǎn)關(guān)鍵值，*lchlid、*rchild分別為左右孩子指針N進(jìn)入主菜單*1=0退出1輸入i1=11=2查找輸入J=1J=2遞歸查找非遞歸查找插入fdata=x)return t;if(xdata)return(Bsearch(t-lchild,x);elsereturn(Bsearch(t-rchild,x);二叉排序樹歸查找算法流程圖4.2非遞歸查找算法查找過程是從根結(jié)點(diǎn)開始逐層向下進(jìn)行的。并定義一個(gè)標(biāo)記量記錄是否找到結(jié) 占八、

8、Bst node *searchBST(Bst node *t,i nt x)Bstnode *p;int flag=O;p=t; 定義*p結(jié)點(diǎn)用于逐層查找，叢根結(jié)點(diǎn)開始查if(p-key=x)查找成功printf(該結(jié)點(diǎn)值存在!);flag=1;break;/查找不成功，到下一層繼續(xù)查找if(xkey)p=p-lchild;查找左子樹elsep=p-rchild;查找右子樹if(flag=0)printf(找不到值為%d的結(jié)點(diǎn)!,x); p=NULL;return p;p=p-rchil d N 找不到節(jié)點(diǎn)查找成功二叉排序樹非遞歸查找算法流程圖4.3插入算法從根結(jié)點(diǎn)開始，根據(jù)比較規(guī)則，逐一與

9、待插入結(jié)點(diǎn)的值比較，查找到插入結(jié)點(diǎn)在 二叉排序樹中的未來位置，然后插入該結(jié)點(diǎn)。將一個(gè)關(guān)鍵字的值為x的結(jié)點(diǎn)s插入到二叉排序樹中，方法如下：(1) 若二叉排序樹為空，則關(guān)鍵字值為x的結(jié)點(diǎn)s成為二叉排序樹的根。(2) 若二叉排序樹非空，則將x與二叉排序樹的根進(jìn)行比較，如果 x的值等于 根結(jié)點(diǎn)關(guān)鍵字的值，則停止插入；如果 x的值小于根結(jié)點(diǎn)關(guān)鍵字的值，則將 x 插入左子樹；如果x的值大于根結(jié)點(diǎn)關(guān)鍵字的值，則將x插入右子樹。在左右子 樹中插入方法與整個(gè)二叉排序樹相同。Bstnode *lnsertBST(Bstnode *t,int x)插入關(guān)鍵值為 x 的元素Bstnode *s,*p,*f;/*s為待

10、插結(jié)點(diǎn)，*p為逐層查找結(jié)點(diǎn)，*f為待插結(jié)點(diǎn)的父結(jié)點(diǎn)p=t；while(p!=NULL)f=p；/查找過程中，f指向*p的父結(jié)點(diǎn)if(x=p-key)若二叉樹中已有關(guān)鍵值為x的元素，無需插入return t;if(xkey)p=p-lchild;elsep=p-rchild;s=(Bst node *)malloc(sizeof(Bst no de);s_key=x;s-lchild=NULL;s-rchild=NULL;if(t=NULL)原樹為空，新結(jié)點(diǎn)作為二叉排序樹的根return s;if(xkey)f-lchild=s;新結(jié)點(diǎn)作為*f左孩子elsef-rchild=s; 新結(jié)點(diǎn)作為*f

11、右孩子return t;開始調(diào)用插入函 數(shù)結(jié)束插入算法流程圖4.4二叉排序樹的生成算法建立二叉排序樹，就是反復(fù)在二叉排序樹中插入新的結(jié)點(diǎn)。插入的原則是如果待插入結(jié)點(diǎn)的值小于根結(jié)點(diǎn)的值，貝朋入到左子樹中，否則插入到右子樹中。大致方法是：首先建一棵空二叉排序樹，然后逐個(gè)讀入元素，每讀入一個(gè)元素，就建一個(gè)新結(jié)點(diǎn)，并調(diào)用上述二叉排序樹的插入算法，將新結(jié)點(diǎn)插入到當(dāng)前已生 成的二叉排序樹中，最終生成一棵二叉排序樹。Bst node *CreateBST()Bstn ode *t;int key;t=NULL;設(shè)置二叉排序樹的初態(tài)為空sea nf(%d,&key);while(key!=e ndflag)t

12、=ln sertBST(t,key);scan f(%d,&key);return t;4.5中序遍歷算法void Ino rder(Bst node *t)if(t!=NULL)In order(t-lchild);Printf( “ %4dn ” ,t-key);In order(t-rchild);先遍歷左孩子，再遍歷父結(jié)點(diǎn)，最后遍歷右孩子。由于是對一個(gè)二叉排序樹進(jìn)行 中序遍歷，遍歷結(jié)果則是一個(gè)有序序列4.6刪除算法1待刪除結(jié)點(diǎn)*p無左孩子，也無右孩子，則*p的父結(jié)點(diǎn)對應(yīng)的孩子指針置空；2待刪除結(jié)點(diǎn)*p有左孩子，無右孩子，則*p的左孩子替代自己；3待刪除結(jié)點(diǎn)*p無左孩子，有右孩子，則*p

13、的右孩子替代自己；4待刪除結(jié)點(diǎn)*p有左孩子，也有右孩子，本課程(數(shù)據(jù)結(jié)構(gòu)與算法)給出了兩 種法：方法一：首先找到待刪結(jié)點(diǎn)*p的前驅(qū)結(jié)點(diǎn)*s，然后將*p的左子樹改為*p父結(jié)點(diǎn)的 左子樹，而*p的右子樹改為*s的右子樹：f- lchild=p-ichild;s-rchild=p-rchild;free(p);方法二：首先找到待刪結(jié)點(diǎn)*p的前驅(qū)結(jié)點(diǎn)*s，然后用結(jié)點(diǎn)*s的值替代結(jié)點(diǎn)*p的值,再將結(jié)點(diǎn)*s刪除，結(jié)點(diǎn)*s的原左子樹改為*s的雙親結(jié)點(diǎn)*q的右子樹：p-data=s-data;q-rchild=s-lchild;free(s);我采用的是第二種算法。開始p=NULLs- dataT-s=I n

14、serBST(T-)rchilds=I nserBST(T-)lchil d刪除算法流程圖4.7主函數(shù)void mai n()int i,j,k;Bst node *tree,*p;system(cls);printf(請先建立一棵二叉排序nn);printf(輸入其結(jié)點(diǎn)信息(輸入一組正整數(shù)，當(dāng)輸入0時(shí)結(jié)束):n);tree=CreateBST();printf(中序遍歷的二叉排序樹:n);Ino rder(tree);printf(” 二叉排序樹的根為:%dn,tree-key);for(;)switch(i=ma inmenu()case O:exit(O);case 1:switch(j

15、=searchme nu()case 1:search_Bitree(tree);break;case 2:pri ntf(n請輸入要查找的結(jié)點(diǎn)的值：”);scan f(%d, &k);p=searchBST(tree,k);prin tf(n ”);break;default:printf(輸入有誤!);break;case 2:tree=i nsert_Bitree(tree);break;case 3:tree=delete_Bitree(tree);break;case 4:pri ntf(n);printf(二叉排序樹的根為:%din,tree-key);prin tf(中序遍歷后的

16、序列為:n);prin t_Bitree(tree);printf（”中序遍歷的二叉排序樹:n）;prin tf(n);break;default:printf(輸入有誤!);4.8注意事項(xiàng)：其中，某些函數(shù)順序一定不能顛倒。例如建立二叉排序樹函數(shù)一定是在插入算法 之后。編寫完基本操作算法后，為最后主函數(shù)的輸出模塊作準(zhǔn)備，又分別寫了遞歸查找 模塊、插入模塊、刪除模塊、顯示模塊。5. 運(yùn)行環(huán)境Microsoft Visual C+ 6.0； Microsoft Word 20106. 上機(jī)調(diào)試6.1語法錯(cuò)誤及修改在編寫程序時(shí)，很容易出現(xiàn)分號(hào)漏寫和括號(hào)不匹配的現(xiàn)象，以及缺少返回值的問題。例如：在編寫

17、非遞歸查找算法時(shí):Bst node * searchBST (Bst node *t,i nt x) Bst node *p;i nt flag=O;p=t；while(p!=NULL)if(p-key=x)printf(找到了 !);flag=1; return p;break;if(xkey)p=p-lchild;elsep=p-rchild;if(flag=0)printf(找不到值為%d的結(jié)點(diǎn),x);return NULL;結(jié)果編譯時(shí)出現(xiàn)了警告 warning : searchBST : not all control paths return a value然后我做了改動(dòng)，改后程序如

18、下：Bst node *searchBST(Bst node *t, int x)Bst node *p;i nt flag=O;p=t;while(p!=NULL)if(p-key=x)printf(該結(jié)點(diǎn)值存在!);flag=1;break;if(xkey)p=p-lchild;elsep=p-rchild;if(flag=0)printf(找不到值為%d的結(jié)點(diǎn)!,x);p=NULL;return p;將NULL值賦給指針p，再在程序結(jié)尾返回p，此時(shí)，編譯結(jié)果就正確了！6.2程序輸出調(diào)整：在遞歸查找算法(Bsearch)中針對查找結(jié)果如何，沒有用明確的輸出函數(shù)表示出來。于是我添加了一個(gè)遞歸

19、查找模塊如下：search_Bitree(Bst node *t)int s;Bst node *p;printf(n 請輸入要查找的結(jié)點(diǎn)的值:);sca nf(%d,&s);if(s!=O) p=Bsearch(t,s);if(p=NULL)printf(該結(jié)點(diǎn)值不存在!n);elseprintf(找不到值為%d的結(jié)點(diǎn)!n,s);這樣主函數(shù)便可直接調(diào)用該函數(shù)來實(shí)現(xiàn)查找過程。6.3時(shí)間和空間性能分析：由于二叉排序樹的中序遍歷序列為一個(gè)遞增的有序序列，這樣可以將二叉排序樹看作是一個(gè)有序表。其查找過程：若查找成功，則是從根結(jié)點(diǎn)出發(fā)走了一條從根到某個(gè)結(jié)點(diǎn)的路徑；若查找不成功，則是從根結(jié)點(diǎn)出發(fā)走了一條

20、從根 到某個(gè)葉子結(jié)點(diǎn)的路徑。和關(guān)鍵字比較次數(shù)不超過二叉排序樹的深度。二叉排 序樹的平均查找長度與其形態(tài)有關(guān)。 最壞情況是具有n個(gè)結(jié)點(diǎn)的單支樹，其平均查找長度與順序查找相同，為(n+1 )/2 ；即平均查找長度的數(shù)量級(jí)為 0 (n)0 在最好情況下，二叉排序樹形態(tài)均勻，它的平均查找長度與二分查找相似，大 約是Iog2n，其平均查找長度的數(shù)量級(jí)為 0 (Iog2n / /1、經(jīng)驗(yàn)與體會(huì)：由于該設(shè)計(jì)問題是對數(shù)據(jù)結(jié)構(gòu)與算法課程中二叉樹章節(jié)的靈活應(yīng)用，所以課本給了我很大的幫助，結(jié)合所學(xué)知識(shí)以及對二叉排序樹的理解，來編寫該程 序。7. 測試結(jié)果及分析(0圖（a）圖（b）圖（1）WW序 序江i竊 叉叉X叉岀

21、 二二二1R - - - 12 3 4 0請選擇您喪進(jìn)行的項(xiàng)巨;嚴(yán)對二文排序樹進(jìn)行操犀4C ECTfi二叉排序樹的根為土兀輸入其結(jié)直當(dāng)敷輸入一組ZE塾教.當(dāng)輸入B時(shí)結(jié)東:3G 24 陥 7S 4 22 IS 6R 0 中序遍歷衙二叉排序校，S 10232435_|ol x找入除示 _ 一 一 _2、選擇方框中給定的項(xiàng)目（輸入 04中任意數(shù)）。若輸入錯(cuò)誤會(huì)有提示，可以重新輸入。lOtXK W KW NW X Jf N 連 X淹廠對二叉排序樹進(jìn)行操ft*-*圖（2）Et GS恥二叉排疼樹的根為12 3 4 0叉叉叉義岀 二二二二很 - 找入除不 宜插刪基 - 請七訐涼更步廠笊比i_|ol x口3、

22、輸入1，則出現(xiàn)查找菜單。選擇查找方法。廠氐退出段程序興貝換*住!覽1111旳11*用黃貝）（貝：貝盤瞬靜歌謂也辛圧玲出的取3丄* 一叟樹的查找萬法*1|1 2.t方方- 1- -Z我找 音杳 Eqm JsnTJb-J-_ 41猜選擇直找冇闿圖（3）4、在查找菜單選1，則進(jìn)行遞歸查找。圖（4）5、同理，若選擇2，則進(jìn)行非遞歸查找。查找的值存在與否都會(huì)有顯示。請迄擇恕曼進(jìn)行旳取巨：請選擇查找方注注嚴(yán)對二強(qiáng)排序樹進(jìn)行操年5圖（5）W苦茫g呼 -5 3EJCJIL=IF注g 叉義叉見岀 三二二退 1 2 3 4 0技入除示 童莓 _ 一 _ _6、選2，則進(jìn)行插入操作。插入關(guān)鍵值為13的結(jié)點(diǎn)后，顯示如

23、圖（6）,即插入13后的橫置的二叉排序樹（圖（c）圖（d ）。圖（c）圖（d）-回列誦選擇悠要逬行的項(xiàng)目S 1316232435 4S 66878二叉拆序樹尚棍次:芻又叉叉叉出 二二二二退5塞嚴(yán)-對二更挑序樹遊行操作|查找插入虢X1WeXJMKlWXIMXKXKmtX X oe at KMT請這擇撐旻進(jìn)行的項(xiàng)目、圖（6）1、選3，進(jìn)行刪除操作。刪除關(guān)鍵值為24的結(jié)點(diǎn)后，顯示如圖（7）,即刪除24后的橫置的二叉排序樹（圖（e）圖（f）圖（e）圖（f）也兇汪盤予亠5壬 E -二+rp 士XXFnx.岀-一一 一一 一 1:12.3.4.仏pFWWTIP您聲進(jìn)行的項(xiàng)目:-I請選擇想要進(jìn)行的項(xiàng)目想請輸

24、入慕刪犀曲結(jié)點(diǎn)的值，m刪嗪結(jié)點(diǎn)啟串序逋歷的二戛排序樹=13 1S 22 3G 4C “ g 70二叉非序樹的根為:勢嚴(yán)對二叉朋序樹迸行操乍一JWAfife顯不圖（7）2、選4則顯示詳細(xì)信息。如圖（8）所示，按中序遍歷（從小到大）依次輸出，并顯示每個(gè)結(jié)點(diǎn)的孩子情況，最后打印出橫置的二叉排序樹。 n x-I3、選0則退出程序。圖（8）嚴(yán)對二叉捱序樹注行操作* Sir Bii- B aw ri# 8 mF-冋請選擇悔要講行的頂巨油Press anjuF keyi to continue,叉叉兄xHd-=一一 U:aJ2.3.4.乩查找描入刪除fl yJZ:MXJlJCJIJCJIJCitX iiHi

25、諼屛 *M-H號(hào)去XTft圖（9）8. 用戶使用說明(二叉用戶可以根據(jù)本程序運(yùn)行過程中出現(xiàn)的提示性語句來進(jìn)行操作。要注意括號(hào)中的提示, 若沒有按照提示輸入的話，程序可能將無法繼續(xù)進(jìn)行下去。例如開始輸入數(shù)據(jù)時(shí)直到輸入 時(shí)才算結(jié)束輸入，從而進(jìn)行下一步操作。在遇到選項(xiàng)時(shí)，選擇錯(cuò)誤會(huì)給你重新選擇的機(jī)會(huì)。 提示：進(jìn)行一系列插入刪除等操作后，可以選擇顯示項(xiàng)來顯示最后的二叉排序樹狀態(tài) 排序樹顯示的是中序遍歷后的序列)。9. 參考文獻(xiàn)(1) 王昆侖李紅數(shù)據(jù)結(jié)構(gòu)與算法北京：中國鐵道出版社，2007.6(2) 王昆侖.李紅.數(shù)據(jù)結(jié)構(gòu)與算法試驗(yàn)指導(dǎo)，2009(3) 譚浩強(qiáng).c程序設(shè)計(jì).北京：清華大學(xué)出版社，2005

26、.7(4) 嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)：c語言版.北京：清華大學(xué)出版社，2002耿國華.等 .數(shù)據(jù)結(jié)構(gòu)：用c語言描述.北京：高等教育出版社，2004設(shè)計(jì)過程中質(zhì)疑（或答辯）記載：1.二叉樹運(yùn)行過程中用了什么排序？答：運(yùn)用了中序遍歷排序。2 中序遍歷排序是怎樣的？答：先遍歷左孩子，再遍歷父結(jié)點(diǎn)，最后遍歷右孩子3.在設(shè)計(jì)過程中遇到過那些困難？答:在編程序的過程的程序一直不能正確運(yùn)行，最后發(fā)現(xiàn)函數(shù)的調(diào)用出現(xiàn)了問 題。最后通過修改解決。指導(dǎo)教師評(píng)語:簽名:2016年 7 月5日附錄#i nclude stdio.h#i nclude malloc.h#in elude stdlib.h#define endfl

27、ag 0/ 定義endflag 為關(guān)鍵字輸入結(jié)束的標(biāo)志/二叉排序樹的結(jié)點(diǎn)結(jié)構(gòu) typedef struct nodeint key;/關(guān)鍵字項(xiàng)struct n ode *lchild,*rchild;左右孩子指針Bst no de;/二叉排序樹的查找算法之一(遞歸)Bstnode *Bsearch(Bstnode *t,int x)if(t=NULL)二叉排序樹為空，查找失敗return NULL;elseif(t-key=x)查找成功，返回當(dāng)前結(jié)點(diǎn)return t;if(xkey)return(Bsearch(t-lchild,x);進(jìn)入左子樹遞歸查找elsereturn(Bsearch(t

28、-rchild,x);進(jìn)入右子樹遞歸查找/遞歸查找函數(shù)(顯示查找結(jié)果) void search_Bitree(Bs tnode *t)int s;定義待查結(jié)點(diǎn)的關(guān)鍵值Bst node *p;定義待查的結(jié)點(diǎn)prin tf(n請輸入要查找的結(jié)點(diǎn)的值：”)；scan f(%d, &s);if(s!=0)p=Bsearch(t,s);遞歸查找if(p!=NULL)printf(該結(jié)點(diǎn)值存在!n);elseprintf(找不到值為%d的結(jié)點(diǎn)!n,s);/二叉排序樹的查找算法之二(非遞歸)Bstn ode *searchBST(Bst node *t,i nt x)Bstnode *p;int flag=

29、O;p=t;定義*p結(jié)點(diǎn)用于逐層查找，叢根結(jié)點(diǎn)開始查找while(p!=NULL)二叉排序樹不為空if(p-key=x)查找成功printf(” 該結(jié)點(diǎn)值存在!”);flag=1;break;/查找不成功，到下一層繼續(xù)查找if(xkey)p=p-lchild;查找左子樹elsep=p-rchild;/查找右子樹if(flag=0)printf(”找不到值為%d的結(jié)點(diǎn)!,x);p=NULL;return p;/二叉排序樹的結(jié)點(diǎn)插入算法Bstnode *lnsertBST(Bstnode *t,int x)/插入關(guān)鍵值為 x 的元素Bstnode *s,*p,*f;/*s為待插結(jié)點(diǎn)，*p為逐層查找

30、結(jié)點(diǎn)，*f為待插結(jié)點(diǎn)的父結(jié)點(diǎn)p=t;while(p!=NULL)f=p；/查找過程中，f指向*p的父結(jié)點(diǎn)if(x=p-key)若二叉樹中已有關(guān)鍵值為x的元素，無需插入return t;if(xkey)p=p-lchild;elsep=p_rchild;s=(Bst node *)malloc(sizeof(Bst no de);s-key=x;s-lchild=NULL;s-rchild=NULL;if(t=NULL)/原樹為空，新結(jié)點(diǎn)作為二叉排序樹的根return s;if(xkey)f-lchild=s;/ 新結(jié)點(diǎn)作為*f左孩子elsereturn t;/中序遍歷(遞歸法)void In

31、order(Bst node *t)if(t!=NULL)若二叉樹不空In order(t-lchild);遍歷左孩子prin tf(%4d,t-key);In order(t-rchild);遍歷右孩子/二叉排序樹的結(jié)點(diǎn)刪除算法Bstnode *DeleteBST(Bstnode *t,int k)/刪除關(guān)鍵值為 k 的元素Bstnode *p,*f,*s,*q;/*p 為待刪結(jié)點(diǎn)，*f為*p父結(jié)點(diǎn)，*s為*p的中序前驅(qū)結(jié)點(diǎn)，*q為*s的父結(jié)點(diǎn)p=t;f=NULL;/從根結(jié)點(diǎn)開始查找，并將*f置空/查找關(guān)鍵值為k的待刪結(jié)點(diǎn)*pwhile(p!=NULL)if(p-key=k) break;/

32、若找到，則退出循環(huán)f=p;未找到時(shí)將*f替代*p , *p則下移進(jìn)入左右子樹繼續(xù)查找if(p-keyk)p=p-lchild;elsep=p_rchild;if(p=NULL) return t;/若找不到，則返回原二叉排序樹的根指針/查找成功后，對*p的刪除過程if(p-lchild=NULL|p-rchild=NULL)/若*p 無左子樹或無右子樹if(f=NULL)/ 若*p是原二叉排序樹的根if(p-lchild=NULL) t=p-rchild;/無左孩子，右孩子做根else t=p-lchild;/無右孩子，左孩子做根else if(p-lchild=NULL)/ 若 *p 無左子

33、樹else /若*p無右子樹if(f-lchild=p) f-lchild=p-lchild;/p是 *f 的左孩子else f-rchild=p-lchild;/p是 *f 的右孩子free(p);else/若*p有左右子樹q=p;s=p_lchild;while(s-rchild)在*p的左子樹中查找最右下結(jié)點(diǎn)(即其中序前驅(qū)結(jié)點(diǎn))q=s;s=s-rchild;if(q=p) q-lchild=s-lchild;else q-rchild=s-lchild;p-key=s-key;將 *s 的值賦給 *pfree(s);return t;/插入函數(shù)(顯示插入結(jié)果)Bstnode *in se

34、rt_Bitree(Bst node *t)int s;/定義待插結(jié)點(diǎn)的關(guān)鍵值Bst node *p;定義待插的結(jié)點(diǎn)prin tf(n);printf(請輸入要插入的結(jié)點(diǎn)的值:);scan f(%d, &s);if(s!=0)p=Bsearch(t,s);if(p=NULL)t=ln sertBST(t,s);printf(插入結(jié)點(diǎn)中序遍歷后的二叉排序樹:n);Ino rder(t);prin tf(n二叉排序樹的根為：dn ,t-key);else printf（該結(jié)點(diǎn)值存在，不插入!n）;return t;/刪除函數(shù)(顯示刪除結(jié)果)Bstnode *delete_Bitree(Bstnod

35、e *t)int s;/定義待刪結(jié)點(diǎn)的關(guān)鍵值Bst node *p;定義待刪的結(jié)點(diǎn)prin tf(n請輸入要?jiǎng)h除的結(jié)點(diǎn)的值:);scan f(%d, &s);if(s!=O)p=Bsearch(t,s);if(p=NULL)printf(找不到值為%d的結(jié)點(diǎn)!,s);elset=DeleteBST(t,s);:n);printf(刪除結(jié)點(diǎn)后中序遍歷的二叉排序樹Ino rder(t);prin tf(n二叉排序樹的根為:%dn ,t-key);return t;/設(shè)置二叉排序樹的初值Bstn ode *CreateBST()Bst node *t;int s;t=NULL;設(shè)置二叉排序樹的初態(tài)為

36、空scan f(%d, &s);while(s!=e ndflag)/輸?shù)浇Y(jié)束符為止t=ln sertBST(t,s);scan f(%d, &s);return t;/顯示函數(shù)void prin t_Bitree(Bst node *t)prin t_Bitree(t-lchild);printf(” 遍歷結(jié)點(diǎn) %d,t-key);if(t-lchild!=NULL)printf(該結(jié)點(diǎn)的左孩子為 %d,t-lchild-key); elseprintf(該結(jié)點(diǎn)的左孩子為空);if(t-rchild!=NULL)prin tf(該結(jié)點(diǎn)的右孩子為 %d),t-rchild-key); elseprin tf(該結(jié)點(diǎn)的右孩子為空門；prin tf(nn ”);prin t_Bitree(t-rchild);/主菜單int mainmenu()int choice;int flag=1;標(biāo)記量prin tf(nnn);prin tf(ttt產(chǎn)*對二叉排序樹進(jìn)行操作* nnprin tf(ttt1;-n片一11 :prin tf(ttt1I n);prin tf(ttt:1二叉排序樹-一查找I:n);prin tf(ttt:2二叉排序樹-插入I:n);prin tf(ttt:3二叉排