軟件課程設(shè)計(jì)報(bào)告二叉樹的查找

1、華中科技大學(xué)軟件課程設(shè)計(jì)報(bào)告課程設(shè)計(jì)題目：二叉樹的查找院（系）：光電子科學(xué)與工程學(xué)院專業(yè)班：光電1001學(xué)號(hào)：u201013352姓名：譚天弈目錄1.軟件設(shè)計(jì) 21.1 系統(tǒng)分析 21.1.1需求分析 2 1.1.2函數(shù)及文件分析 21.2系統(tǒng)設(shè)計(jì) 21.2.1系統(tǒng)模塊設(shè)計(jì) 21.2.1.1代碼模塊化 21.2.1.2功能模塊化 41.2.1.3流程模塊化 61.2.2函數(shù)設(shè)計(jì) 61.2.3系統(tǒng)流程設(shè)計(jì) 71.2.3.1主函數(shù)流程設(shè)計(jì) 71.2.3.2create_btree流程設(shè)計(jì) 101.2.3.3search_btree流程設(shè)計(jì) 111.2.3.4print_btree流程設(shè)計(jì) 121.

2、2.4用戶界面設(shè)計(jì) 121.2.5容錯(cuò)性設(shè)計(jì) 132.軟件測(cè)試 142.1調(diào)試過程 142.2測(cè)試用例及運(yùn)行結(jié)果 143.任務(wù)的其他要求3.1源代碼的注釋 213.2源代碼的運(yùn)行結(jié)果 233.3設(shè)計(jì)心得與體會(huì) 244.參考文獻(xiàn) 24附錄：二叉樹綜合應(yīng)用程序源碼 251軟件設(shè)計(jì)1.1系統(tǒng)分析1.1.1需求分析本二叉樹綜合應(yīng)用程序集合了大部分二叉樹的相關(guān)功能。主要包含了二叉樹的建立，二叉樹的檢索，二叉樹的遍歷，二叉樹的打印，以及計(jì)算二叉樹的相關(guān)參數(shù)，刪除二叉樹的部分節(jié)點(diǎn)等功能。本著用戶友好的原則，每一項(xiàng)功能都設(shè)計(jì)了相應(yīng)的菜單，并且每一個(gè)功能在主函數(shù)中都對(duì)應(yīng)了一個(gè)循環(huán)，方便客戶使用，而不是調(diào)試程序時(shí)

3、使用的流水線式的運(yùn)行過程。二叉樹可以鍵盤輸入，也可以使用內(nèi)置的二叉樹進(jìn)行測(cè)試。主函數(shù)中每一級(jí)菜單和每一個(gè)功能菜單都是用一個(gè)while(1)循環(huán)包裹起來的，具有很強(qiáng)的獨(dú)立性。并且把一些小的功能做成相應(yīng)的函數(shù)，以縮短代碼。并且每一個(gè)函數(shù)都相對(duì)獨(dú)立，其中void deltree(struct tree *r)和struct tree *binary_search(struct tree *point,char node,char *postion)設(shè)計(jì)了程序接口，方便其它子函數(shù)調(diào)用。并且在發(fā)現(xiàn)bug時(shí)便于更改。做到，可持續(xù)，有余地。1.1.2函數(shù)及文件分析為了盡量的縮短main()函數(shù)，把能設(shè)計(jì)成子

4、函數(shù)的功能都設(shè)計(jì)成了子函數(shù)。包括常用的顯示和分割線都寫成了re1()和re2()函數(shù)。由于每個(gè)大的功能子函數(shù)都只調(diào)用了一次，所以不考慮進(jìn)行文件設(shè)計(jì)。子函數(shù)被分成了3個(gè)部分，第一部分為題目中給出的3個(gè)函數(shù)，具備了建立，打印，檢索3個(gè)基本功能。第二部分為功能部分，主要是4種遍歷，求各種特征參數(shù)，以及用凹表，括號(hào)法打印二叉樹，和兩種刪除（刪除方法暫時(shí)不太承受）。第三個(gè)部分為用戶函數(shù)，除了re1，re2和err這三個(gè)常用函數(shù)，其它全部用c_開頭。為了保證屏幕的整潔，在每一個(gè)菜單函數(shù)的前面都加上了一個(gè)清屏函數(shù)。理論上，在子函數(shù)也復(fù)雜，主函數(shù)調(diào)用不可能簡(jiǎn)單的完成，例如對(duì)create_btree的調(diào)用，需要

5、在main中進(jìn)行循環(huán)和遞歸。所以應(yīng)當(dāng)設(shè)計(jì)業(yè)務(wù)子函數(shù)，讓主函數(shù)可以直接調(diào)用。但考慮到實(shí)際是大多數(shù)子函數(shù)可以在主函數(shù)中直接得出結(jié)果，并且在re1，re2，err三個(gè)函數(shù)的幫助下就可以很友好地顯示。再加上一旦設(shè)計(jì)了業(yè)務(wù)子函數(shù)，就會(huì)使整個(gè)調(diào)用過程更加復(fù)雜，每一個(gè)業(yè)務(wù)子函數(shù)都要調(diào)用其它子函數(shù)。故不設(shè)計(jì)業(yè)務(wù)函數(shù)，少數(shù)不能在主函數(shù)中直接運(yùn)行得出結(jié)果的子函數(shù)，類似create_btree的處理。系統(tǒng)函數(shù)的調(diào)用，主要調(diào)用的c中的函數(shù)，混雜了少數(shù)的c+函數(shù)如new函數(shù)等，所以在編譯運(yùn)行時(shí)需要一些頭文件如iostream.h，如若編譯器不具備這些頭函數(shù)可能導(dǎo)致程序不能運(yùn)行。所以如果用c語言運(yùn)行請(qǐng)將new改成mall

6、oc函數(shù)。1.2 系統(tǒng)設(shè)計(jì)1.2.1系統(tǒng)模塊設(shè)計(jì)1.2.1.1代碼模塊化將代碼分成幾個(gè)區(qū)域來書寫不同的內(nèi)容，第一個(gè)區(qū)域?yàn)榇a的頭部，包括了頭文件和該程序的核心“結(jié)構(gòu)體”。 第二個(gè)部分，為函數(shù)聲明，包括了兩個(gè)全局變量，并說明函數(shù)功能：第三部分為主函數(shù)部分，包含了主要循環(huán)過程，和容錯(cuò)性設(shè)計(jì)： 第四部分為功能子函數(shù)的定義，都用編號(hào)標(biāo)好，并加上簡(jiǎn)單注釋，方便后期修改和調(diào)用，如：第五部分為界面子函數(shù)的定義，如：1.2.1.2功能模塊化二叉樹綜合應(yīng)用程序二叉樹的建立版本信息遍歷層次后序中序先序凹表打印二叉樹括號(hào)法打印二叉樹求參數(shù)最大最小枝長(zhǎng)葉子樹結(jié)點(diǎn)數(shù)樹深度刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)及子樹僅刪除結(jié)點(diǎn)模塊1：二叉樹的

7、建立模塊2：二叉樹相關(guān)操作的功能選擇模塊3：遍歷模塊4：求參數(shù)模塊5：刪除節(jié)點(diǎn)1.2.1.3流程模塊化通過嵌套循環(huán)的方法進(jìn)行，因?yàn)樾枰玫絙reak進(jìn)行返回，故不使用switch語句，直接在if中進(jìn)行循環(huán)，如圖：1.2.2函數(shù)設(shè)計(jì)對(duì)每一個(gè)功能設(shè)計(jì)一個(gè)子函數(shù)，如輸入函數(shù)create_btree，括號(hào)法輸入函數(shù)create_btree2，層次遍歷函數(shù)levelorder，求結(jié)點(diǎn)個(gè)數(shù)函數(shù)nodenum，等。并且對(duì)每一個(gè)菜單項(xiàng)設(shè)計(jì)了一個(gè)子函數(shù)如主菜單c_first_menu，遍歷菜單c_order_menu。常用輸出函數(shù)re1，re2，報(bào)錯(cuò)函數(shù)err等。子函數(shù)表：struct tree *create

8、_btree(struct tree *root,struct tree *r,char info); /1建立一棵二叉樹struct tree *search_btree(struct tree *root,char key); /2檢索key函數(shù)void print_btree(struct tree *r,int l); /3將這個(gè)二叉樹打印出來,中序/*二叉樹的遍歷*/void preorder(struct tree *r);/4先序void inorder(struct tree *r);/5中序void postorder(struct tree *r);/6后序void lev

9、elorder(struct tree *r);/7層次遍歷/*其他功能*/void pdisptree(struct tree *r);/8以凹入法顯示二叉樹,先序int treedepth(struct tree *r);/9求二叉樹的深度void nodenum(struct tree *r);/10二叉樹結(jié)點(diǎn)個(gè)數(shù)void leafnum(struct tree *r);/11二叉樹葉子結(jié)點(diǎn)void create_btree2(struct tree *&r,char *str);/12用括號(hào)法建立一個(gè)二叉樹,入?yún)為根節(jié)點(diǎn)，str為其他節(jié)點(diǎn)void print_btree2(struc

10、t tree *r); /13括號(hào)法顯示二叉樹void maxminleaf(struct tree *r,int &m,int &n);/14計(jì)算二叉樹的最小枝長(zhǎng)和最大枝長(zhǎng)struct tree *binary_search(struct tree *point,char node,char *postion);/15查找并記錄父節(jié)點(diǎn)的值，16中調(diào)用struct tree *deletenode(struct tree *root,char node);/16刪除一個(gè)節(jié)點(diǎn)，調(diào)用15void deltree(struct tree *r);/17遞歸刪除void search_deltree(

11、struct tree *r,char x);/18查找并刪除某節(jié)點(diǎn)及其子樹，調(diào)用17/*用戶界面功能*/void c_first_menu();/19一級(jí)菜單void c_information();/20版本信息void c_sec_menu();/21二級(jí)菜單void re1();/22顯示結(jié)果void re2();/23分割線void c_order_menu();/24遍歷菜單void err();/25報(bào)錯(cuò)void c_num_menu();/26參數(shù)菜單void c_del_menu();/27刪除菜單1.2.3系統(tǒng)流程設(shè)計(jì)1.2.3.1主函數(shù)流程設(shè)計(jì)由于主函數(shù)流程過于復(fù)雜，這里

12、將主要的循環(huán)及選擇畫出來，細(xì)節(jié)部分忽略。注：如看不清晰，請(qǐng)調(diào)至150%觀看。接下一面nyynnycho1=0exit(0)cho1=1括號(hào)法輸入error圖1 c_first_menu菜單一的循環(huán)c_first_menu()scanf cho1ny退出ynynnnyyyyynynynynnyc_sec_menu()scanf cho2cho2=0exit(0)cho2=1c_order_menu()scanf cho3cho3=0exit(0)四種遍歷errorcho2=2pdisptreecho2=3print_btree2cho2=4c_num_menu ()scanf cho4cho4=

13、0exit(0)參數(shù)計(jì)算errorcho2=5yc_del_menu() ()scanf cho5cho5=0exit(0)刪除節(jié)點(diǎn)errorcho2=6yerrorscanf choch3=0返回上一面圖2 c_sec_menu菜單二的循環(huán)1.2.3.2create_btree流程設(shè)計(jì)子函數(shù)聲明為struct tree *create_btree(struct tree *root,struct tree *r,char info);用了迭代的思想進(jìn)行流程設(shè)計(jì)。注：沒有指向的框圖為迭代時(shí)的函數(shù)入?yún)?。圖3create_btree流程nnynyr=0r=new (struct tree)r=0r

14、eturn 0初始化root=0y根節(jié)點(diǎn)infoinfoyroot - left=rroot - right=rreturn rinfo infoinfo=r-info(r,r-left,info)(r,r-right,info)1.2.3.3search_btree流程設(shè)計(jì)ynnn！rootyreturn rootkeyinfoyroot=root-leftroot=root-rightroot=0root!=0return rootyyroot-info!=key圖4 search_btree流程1.2.3.4print_btree流程設(shè)計(jì)nr=0yreturn(r-left,l+1)ii

15、nfo(r-right,l+1)圖5print_btree流程1.2.4用戶界面設(shè)計(jì)以“有好的交互，清晰的提示，簡(jiǎn)單明了的輸出”為原則，進(jìn)行控制臺(tái)界面設(shè)計(jì)。比如用括號(hào)法輸入時(shí)，給出用戶示例：printf(示例：a(b(d,e(h,i),c(g):n);在輸出時(shí)為了界面的整潔，設(shè)置了專門的輸出函數(shù)：void re1()printf(n);printf(顯示結(jié)果如下：n);printf(-n);void re2()printf(n);printf(-n);getchar();這樣的輸出就會(huì)非常簡(jiǎn)潔。如圖：另外每個(gè)菜單子函數(shù)的前面都有清屏函數(shù)system(“cls”)這樣可以保持界面的整潔，使要操作

16、的功能菜單在控制臺(tái)的最上方。另外，為了保證程序的可用性，要求每一級(jí)菜單和功能都有直接退出和返回上一級(jí)的能力，如圖所示：1.2.5容錯(cuò)性設(shè)計(jì)為了防止用戶輸入錯(cuò)誤，進(jìn)行了容錯(cuò)性設(shè)計(jì)。每一個(gè)輸入功能，如cho1，cho2的輸入都用一個(gè)while(1)永真循環(huán)來包裹，當(dāng)用戶輸入的數(shù)據(jù)錯(cuò)誤時(shí)返回輸入部分。專門設(shè)計(jì)了報(bào)錯(cuò)函數(shù)err，其中包含的system(“pause”)可以是屏幕內(nèi)容暫緩。void err()printf(n);printf(輸入錯(cuò)誤，請(qǐng)重新輸入n);getchar();2.軟件測(cè)試2.1調(diào)試過程用如下函數(shù)調(diào)試子函數(shù)。void main () char;int;string;/變量聲明，

17、初始化。do printf(enter a letter:); gets(s);if (!root)root=create_btree(root,root,*s);elsecreate_btree(root,root,*s);while (*s) ;print_btree(root,0);debugfunction();/被調(diào)試的函數(shù)將每一個(gè)子函數(shù)帶入調(diào)試函數(shù)中，編譯，組件，運(yùn)行。出現(xiàn)的bug很少。一多半是由于printf中缺少n或者缺少system(“puase”),system(“cls”)導(dǎo)致顯示結(jié)果不完美。比較關(guān)鍵的bug是由于nodenum(struct tree *r);void

18、leafnum(struct tree *r);函數(shù)的返回類型原本是int型，且入?yún)橐粋€(gè)int型指針，導(dǎo)致返回的數(shù)據(jù)有問題，最后設(shè)置了兩個(gè)全局count1,count2來記錄結(jié)點(diǎn)數(shù)和葉子樹。返回類型也改成了void。最大的問題在于，creat_btree函數(shù)調(diào)用時(shí)，入?yún)?s用gets函數(shù)獲得，導(dǎo)致輸入流的最后加入了一個(gè)回車符，也就是二叉樹中多了一個(gè)異常的數(shù)據(jù)，所以后面的對(duì)二叉樹的處理都出現(xiàn)了偏差。比如求最大最小枝長(zhǎng)時(shí)，包含較小數(shù)據(jù)的枝長(zhǎng)值會(huì)多出1，這正是多出的回車符導(dǎo)致的。這個(gè)問題目前沒想到解決的辦法，所以用另一種輸入方法既括號(hào)法來代替。但括號(hào)法在輸入大批數(shù)據(jù)時(shí)不太方便，此問題有待日后解決。

19、另外，在對(duì)結(jié)點(diǎn)進(jìn)行刪除時(shí)，成功率不能達(dá)到百分之一百，因?yàn)橛行┙Y(jié)點(diǎn)一旦被刪除會(huì)導(dǎo)致整個(gè)二叉樹不再為二叉樹，所以對(duì)指定的結(jié)點(diǎn)是有特殊要求的。2.2測(cè)試用例及運(yùn)行結(jié)果測(cè)試環(huán)境：系統(tǒng)：win7家庭普通版cpu：測(cè)試所用的二叉樹如下：a(g(u(o,p(t(e,c),d(q,w),n(f(i(h(z(e,d),b),t(f,k),s),a),v(l,d),u(o,p(t(e,c),d(q,w),n(f(i(h(z(p,y),b),t(x,z),s),m),v(l,d)該二叉樹為對(duì)稱的，便于檢查。1括號(hào)法輸入數(shù)據(jù)2回車查看從左向右顯示結(jié)果，及左邊為根節(jié)點(diǎn)，向右為子樹3繼續(xù)回車選擇界面4選擇功能1，再選先序

20、遍歷5遍歷結(jié)果，正確6中序遍歷7層次遍歷8凹表打印9括號(hào)法顯示10求相關(guān)參數(shù)11深度12結(jié)點(diǎn)數(shù)13葉子樹14最大最小枝長(zhǎng)15刪除結(jié)點(diǎn)16僅刪除節(jié)點(diǎn)t根據(jù)凹表打印 前序遍歷到的第一個(gè)節(jié)點(diǎn)t被刪除17刪除t的節(jié)點(diǎn)及子樹18返回上一級(jí)結(jié)果：輸入1返回19退出程序直接退出了。測(cè)試結(jié)果非常理想，鑒于第二種建樹方法在調(diào)試時(shí)的bug，故不對(duì)其進(jìn)行測(cè)試。3.任務(wù)的其他要求3.1源代碼的注釋#include#includestruct tree char info; /數(shù)據(jù)元素 struct tree *left,*right; /數(shù)的左指針域和右指針域 ;struct tree *create_btree(s

21、truct tree *root,struct tree *r,char info); /函數(shù)聲明：建立一棵二叉樹struct tree *search_btree(struct tree *root,char key); /函數(shù)聲明：檢索key函數(shù)void print_btree(struct tree *r,int l); /函數(shù)聲明：將這個(gè)二叉樹打印出來void main () char s100,c,key= ;/聲明一個(gè)字符串，兩個(gè)字符變量待用 struct tree *root=0 ; do printf(enter a letter:); gets(s);/從控制臺(tái)得到字符串si

22、f (!root)root=create_btree(root,root,*s);/當(dāng)根節(jié)點(diǎn)為空的時(shí)候，從根節(jié)點(diǎn)開始建立elsecreate_btree(root,root,*s);/否則添加新的子樹 while (*s) ;/當(dāng)不在輸入時(shí)，建立完成，按回車結(jié)束print_btree(root,0);/將建立的二叉樹打印出來key=1;/初始化keywhile ( key)printf(enter a key to find:);scanf(%s,&c);root=search_btree(root,c);printf(press to continuen);/檢索key的值 /* btree

23、.c 結(jié)束 */ /*子函數(shù)1*/struct tree *create_btree(struct tree *root,struct tree *r,char info) if (r =0 ) r=new (struct tree);/ 申請(qǐng)一塊內(nèi)存，在c中用：malloc(sizeof()if ( r = 0) printf(out of memoryn); return 0 ; /如果r=0則申請(qǐng)內(nèi)存失敗 直接退出程序r-left= 0; r-right=0; r-info=info;/將r的左右節(jié)點(diǎn)設(shè)置為空 數(shù)據(jù)data為infoif (root) if(infoinfo) root

24、- left=r;/要插入的data比根節(jié)點(diǎn)中data小 則將其放在左枝else root - right=r;/當(dāng)root不為空時(shí) 創(chuàng)造一個(gè)子節(jié)點(diǎn)else r-right = 0; r-left = 0; /當(dāng)root為空時(shí) 創(chuàng)造一個(gè)根節(jié)點(diǎn)return r;if (info info)create_btree(r,r-left,info);if(info=r-info)create_btree(r,r-right,info);/r不為空時(shí)，當(dāng)data小于r中的data則創(chuàng)造左子樹，反之創(chuàng)造右子樹 /*子函數(shù)2*/struct tree *search_btree(struct tree *r

25、oot,char key) if (!root) printf(emptu btreen); return root; /當(dāng)root為空時(shí)，提示空樹 while(root-info!=key) if(keyinfo) root=root-left;elseroot=root-right;/要檢索的值比當(dāng)前結(jié)點(diǎn)的值小，到左子樹中繼續(xù)檢索，反之同理if(root=0) printf(search failuren);break ; /root為空 提示檢索失敗 并退出循環(huán) /檢索到key時(shí)退出循環(huán)if (root !=0)printf(successful searchn key=%cn,root

26、-info);/當(dāng)檢索到的值不為空時(shí)，提示檢索成功，并將檢索到的key值打印return root ;/返回檢索值 /*子函數(shù)3*/void print_btree(struct tree *r,int l) int i;if (r = 0) return ;/當(dāng)r為空樹時(shí) 跳出print_btree(r-left,l+1);/對(duì)左子樹使用打印函數(shù)for(i=0;iinfo);print_btree(r-right,l+1);/將該節(jié)點(diǎn)右子樹以及右子樹的右子樹等全部打印出來，并對(duì)其中所有左子樹使用打印函數(shù)3.2源代碼的運(yùn)行結(jié)果查找 6 成功查找a 失敗3.3設(shè)計(jì)心得與體會(huì)編程是一件很枯燥很無聊

27、的事情，但是出于完成作業(yè)，得到學(xué)分的壓力，還必須強(qiáng)破自己堅(jiān)持下去，按照老師所說的模塊化思想，分部分的進(jìn)行編寫。而且編程是一件高精度、模范化的事情，稍有疏乎都會(huì)影響全局，也可能因?yàn)槟骋惶幍男〉腻e(cuò)誤而導(dǎo)致整個(gè)程序的無法運(yùn)行。所以認(rèn)真仔細(xì)就是非常重要的了。開始的時(shí)候真的感覺編程是一件很無聊的事情，不過當(dāng)一個(gè)程序運(yùn)行成功的時(shí)候那種喜悅是無法言語的，那種成就感是無法比擬的。又經(jīng)過幾天的努力，終于把程序完成了，盡管程序還是有很多錯(cuò)誤和漏洞，不過還是很高興的。無論如何是自己的勞動(dòng)成果，是自己經(jīng)過努力得到的成績(jī)，同時(shí)也是學(xué)習(xí)c語言的一次實(shí)踐作業(yè)，自己進(jìn)步的證明。通過這次課程設(shè)計(jì)，使我對(duì)c語言有了更進(jìn)一步的認(rèn)識(shí)

28、和了解，要想學(xué)好它要重在實(shí)踐，要通過不斷的上機(jī)操作才能更好地學(xué)習(xí)它，我也發(fā)現(xiàn)我的好多不足之處，首先是自己在指法上還不行，經(jīng)常按錯(cuò)字母，通過學(xué)習(xí)也有所改進(jìn)；再有對(duì)c語言的一些標(biāo)準(zhǔn)庫函數(shù)不太了解，還有對(duì)函數(shù)調(diào)用的正確使用不夠熟悉，還有對(duì)c語言中經(jīng)常出現(xiàn)的錯(cuò)誤也不了解，通過實(shí)踐的學(xué)習(xí)，我認(rèn)識(shí)到學(xué)好計(jì)算機(jī)要重視實(shí)踐操作，不僅僅是學(xué)習(xí)c語言，還是其它的語言，以及其它的計(jì)算機(jī)方面的知識(shí)都要重在實(shí)踐，所以后在學(xué)習(xí)過程中，我會(huì)更加注視實(shí)踐操作，使自己便好地學(xué)好計(jì)算機(jī)。并且，更加深入的，我知道了如何設(shè)計(jì)用戶友好程序，和具有強(qiáng)大容錯(cuò)性的程序。也從深層次的理解了子函數(shù)，和文件存在的意義。在課程設(shè)計(jì)過程中，收獲知識(shí)，

29、提高能力的同時(shí)，我也學(xué)到了很多人生的哲理，懂得怎么樣去制定計(jì)劃，怎么樣去實(shí)現(xiàn)這個(gè)計(jì)劃，并掌握了在執(zhí)行過程中怎么樣去克服心理上的不良情緒。因此在以后的生活和學(xué)習(xí)的過程中，我一定會(huì)把課程設(shè)計(jì)的精神帶到生活中，不畏艱難，勇往直前！4.參考文獻(xiàn)1c語言程序設(shè)計(jì)2c語言實(shí)戰(zhàn)100例3數(shù)據(jù)結(jié)構(gòu)4博客園算法頻道附錄：二叉樹綜合應(yīng)用程序源碼：#include #include #include #include #define treemax 100struct tree char info; /數(shù)據(jù)元素 struct tree *left,*right; /數(shù)的左指針域和右指針域 ;/-int count1

30、 = 0;/全局變量，用來記錄結(jié)點(diǎn)個(gè)數(shù)int count2 = 0;/全局變量，用來記錄葉子節(jié)點(diǎn)數(shù)/*函數(shù)聲明*/*二叉樹的基本功能*/struct tree *create_btree(struct tree *root,struct tree *r,char info); /1建立一棵二叉樹struct tree *search_btree(struct tree *root,char key); /2檢索key函數(shù)void print_btree(struct tree *r,int l); /3將這個(gè)二叉樹打印出來,中序/*二叉樹的遍歷*/void preorder(struct tr

31、ee *r);/4先序void inorder(struct tree *r);/5中序void postorder(struct tree *r);/6后序void levelorder(struct tree *r);/7層次遍歷/*其他功能*/void pdisptree(struct tree *r);/8以凹入法顯示二叉樹,先序int treedepth(struct tree *r);/9求二叉樹的深度void nodenum(struct tree *r);/10二叉樹結(jié)點(diǎn)個(gè)數(shù)void leafnum(struct tree *r);/11二叉樹葉子結(jié)點(diǎn)void create_b

32、tree2(struct tree *&r,char *str);/12用括號(hào)法建立一個(gè)二叉樹,入?yún)為根節(jié)點(diǎn)，str為其他節(jié)點(diǎn)void print_btree2(struct tree *r); /13括號(hào)法顯示二叉樹void maxminleaf(struct tree *r,int &m,int &n);/14計(jì)算二叉樹的最小枝長(zhǎng)和最大枝長(zhǎng)struct tree *binary_search(struct tree *point,char node,char *postion);/15查找并記錄父節(jié)點(diǎn)的值，16中調(diào)用struct tree *deletenode(struct tree

33、*root,char node);/16刪除一個(gè)節(jié)點(diǎn)，調(diào)用15void deltree(struct tree *r);/17遞歸刪除void search_deltree(struct tree *r,char x);/18查找并刪除某節(jié)點(diǎn)及其子樹，調(diào)用17/*用戶界面功能*/void c_first_menu();/19一級(jí)菜單void c_information();/20版本信息void c_sec_menu();/21二級(jí)菜單void re1();/22顯示結(jié)果void re2();/23分割線void c_order_menu();/24遍歷菜單void err();/25報(bào)錯(cuò)vo

34、id c_num_menu();/26參數(shù)菜單void c_del_menu();/27刪除菜單/-void main () while(1)char str100,s100,node;/s為輸入數(shù)組，node為要?jiǎng)h去的結(jié)點(diǎn) struct tree *root=0 ; intcho,cho1,cho2,cho3,cho4,cho5;int dep,max,min;/深度，最大枝長(zhǎng)，最小枝長(zhǎng)while(1)c_first_menu();cho1 = 0;scanf(%d%*c,&cho1);/用%*c來儲(chǔ)存回車符if(cho1 = 0)exit(0);else if(cho1 = 1)/括號(hào)法輸

35、入二叉樹printf(請(qǐng)輸入你想建立的二叉樹n);printf(示例：a(b(d,e(h,i),c(g):n);gets(str);create_btree2(root,str);re1();print_btree(root,0);re2();break;else if(cho1 = 2)do printf(enter a letter:); gets(s);if (!root)root=create_btree(root,root,*s);elsecreate_btree(root,root,*s);while (*s) ;re1();print_btree(root,0);re2();/將

36、建立的二叉樹打印出來break;else if(cho1 = 3)c_information();elseerr();while(1)c_sec_menu();cho2 = 0;scanf(%d%*c,&cho2);if(cho2 = 0)exit(0);else if(cho2 = 1)c_order_menu();cho3 = 0;scanf(%d%*c,&cho3);while(1)if(cho3 = 0)exit(0);else if(cho3 = 1)re1();preorder(root);re2();break;else if(cho3 = 2)re1();inorder(roo

37、t);re2();break;else if(cho3 = 3)re1();postorder(root);re2();break;else if(cho3 = 4)re1();levelorder(root);re2();break;else if(cho3 = 5)break;elseerr();else if(cho2 = 2)re1();pdisptree(root);re2();else if(cho2 = 3)re1();print_btree2(root);re2();else if(cho2 = 4)c_num_menu();cho4 = 0;scanf(%d%*c,&cho4

38、);while(1)if(cho4 = 0)exit(0);else if(cho4 = 1)dep = treedepth(root);re1();printf(深度為：%d,dep);re2();break;else if(cho4 = 2)nodenum(root);re1();printf(結(jié)點(diǎn)個(gè)數(shù)為:%d,count1);re2();break;else if(cho4 = 3)leafnum(root);re1();printf(葉子個(gè)數(shù)為:%d,count2);re2();break;else if(cho4 = 4)maxminleaf(root,max,min);re1();

39、printf(最大枝長(zhǎng)=%dn,max);printf(最小枝長(zhǎng)=%dn,min);re2();break;else if(cho4 = 5)break;elseerr();else if(cho2 = 5)c_del_menu();cho5 = 0;scanf(%d%*c,&cho5);while(1)if(cho5 = 0)exit(0);else if(cho5 = 1)printf(您要?jiǎng)h去的結(jié)點(diǎn)是：);scanf(%c%*c,&node);deletenode(root,node);re1();print_btree(root,0);re2;system(pause);break;e

40、lse if(cho5 = 2)printf(您要?jiǎng)h去的結(jié)點(diǎn)是：);scanf(%c%*c,&node);search_deltree(root,node);re1();print_btree(root,0);re2;system(pause);break;else if(cho5 = 3)break;elseerr();else if(cho2 = 6)break;elseerr();printf(是否退出程序(輸入0退出程序，輸入1返回)：n);scanf(%d%*c,&cho);if(cho = 0)break; /-/*1*/struct tree *create_btree(stru

41、ct tree *root,struct tree *r,char info) if (r =0 ) r=new (struct tree);/ 申請(qǐng)一塊內(nèi)存，在c中用：malloc(sizeof()if ( r = 0) printf(out of memoryn); return 0 ; /如果r=0則申請(qǐng)內(nèi)存失敗 直接退出程序r-left= 0; r-right=0; r-info=info;/將r的左右節(jié)點(diǎn)設(shè)置為空 數(shù)據(jù)data為infoif (root) if(infoinfo) root - left=r;/要插入的data比根節(jié)點(diǎn)中data小 則將其放在左枝else root -

42、 right=r;/當(dāng)root不為空時(shí) 創(chuàng)造一個(gè)子節(jié)點(diǎn)else r-right = 0; r-left = 0; /當(dāng)root為空時(shí) 創(chuàng)造一個(gè)根節(jié)點(diǎn)return r;if (info info)create_btree(r,r-left,info);if(info=r-info)create_btree(r,r-right,info);/r不為空時(shí)，當(dāng)data小于r中的data則創(chuàng)造左子樹，反之創(chuàng)造右子樹 /*2*/struct tree *search_btree(struct tree *root,char key) if (!root) printf(emptu btreen); ret

43、urn root; /當(dāng)root為空時(shí)，提示空樹 while(root-info!=key) if(keyinfo) root=root-left;elseroot=root-right;/要檢索的值比當(dāng)前結(jié)點(diǎn)的值小，到左子樹中繼續(xù)檢索，反之同理if(root=0) printf(search failuren);break ; /root為空 提示檢索失敗 并退出循環(huán) /檢索到key時(shí)退出循環(huán)if (root !=0)printf(successful searchn key=%cn,root-info);/當(dāng)檢索到的值不為空時(shí)，提示檢索成功，并將檢索到的key值打印return root ;/返回檢索值 /*3*/void print_btree(struct tree *r,int l) int i;if (r = 0) return ;/當(dāng)r為空樹時(shí) 跳出print_btree(r-left,l+1);/對(duì)左子樹使用打印函數(shù)for(i=0;iinfo);print_btree(r-right,l+1);/將該節(jié)點(diǎn)右子樹以及右子樹的右子樹等全部打印出來，并對(duì)其中所有左子樹使用打印函數(shù)/*4*/ void preorder(struct tree *r)if(r != 0)prin