二叉排序樹的創(chuàng)建、刪除、插入等操作

1、淮陰工學院算法設計技能訓練實習報告題目： 二叉排序樹的創(chuàng)建、插入、刪除系（院），計算機工程學院專 業(yè)：計算機科學與技術班 級：計算機M123學 號：1321124姓名：單永明指導教師：劉作軍/寇海州學年學期.，20142015學年 第土學期算法設計技能訓練任務書課題名稱設計目的1、通過算法設計技能訓練，深入理解算法設計的意義和重要性，更好地掌握算法設計的知識。Z、能夠針對某一具體問題，設計算法進行解決。M、鍛煉實踐動手能力，提高解決問題的能力。實驗環(huán)境硬件：1、PC機，奔騰w以上CPU，512MB以上內存，80G以上硬盤；軟件：的況C+編程工具任務要求1分析問題，給出數(shù)學模型，選擇數(shù)據(jù)結構2設

2、計算法，給出算法描述M給出源程序清單站編輯、編譯、調試源程序5,撰寫課程設計報告工作進度計劃序號起止日期工作內容12014.12.20任務下達，查閱文獻資料22014,12,25 2014,12,28總體設計、素材搜集、課題詳細設計、調試32014,12,29 2013,12,31完善設計、撰寫報告42014.12.31答辯指導教師（簽章）:目錄 TOC o 1-5 h z 7、引言4公課程設計的題目和內容52.7課程設計的題目5 HYPERLINK l bookmark16 o Current Document 2.2課程設計的內容5 HYPERLINK l bookmark21 o Cur

3、rent Document 3、課程設計報告內容63.7課程概述63.2實驗內容73.3源程序代碼703.4測試用例75 HYPERLINK l bookmark27 o Current Document 實驗總結78 HYPERLINK l bookmark30 o Current Document 致謝79參考文獻201.弓|言本算法設計技能訓練的目的就是要達到理論與實際應用相結合，使同學們能夠根據(jù)數(shù)據(jù)對象的特 性，學會數(shù)據(jù)組織的方法，能把現(xiàn)實世界中的實際問題在計算機內部表示出來，并培養(yǎng)基本的、良好 的程序設計技能。公課程設計的題目和內容課程設計的題目二叉排序樹的基本操作2.2、課程設計內

4、容1,用二叉鏈表作存儲結構，2編寫程序實現(xiàn)二叉排序樹上的基本操作:M輸入數(shù)列生成二叉排序樹對二叉排序作中序遍歷；查找二叉排序樹5,刪除二叉排序樹3、課程設計報告內容3.1課題概述1、問題描述：（需求分析和背景意義）利用二叉排序樹實現(xiàn)一個動態(tài)查找表。Z、基本要求：（設計階段，概要設計和詳細設計）實現(xiàn)動態(tài)查找表的三種功能：查找、插入、刪除。3、測試數(shù)據(jù)：自行設定。彳、實現(xiàn)提示：（1）初始，二叉排序樹為空樹，操作界面給出查找、插入和刪除三種操作供選擇。每種操作均要提示輸入關鍵字。每次插入或刪除一個結點后，應更二叉排序樹的顯示。3）二叉排序樹的顯示可采用凹入表現(xiàn)形式，也可以采用圖形界面畫出樹行。（3）

5、教科書已給出查找和插入算法，本題重點在于對刪除算法的設計和實現(xiàn)。假設要刪除關鍵字為/的結點。如果，不在葉子結點上，則用它的左子樹中最大值或右子樹中的最小值取代。如此反 復取代，直到刪除動作傳遞到某個葉子結點。刪除葉子結點時，若需要進行平衡交換，可采用插入的 平衡變換的反變換（如，左子樹變矮對應右子樹長高）。L升始依次輸入.個關鍵字刪除任意結點插入一個結點中序輸出操作后二叉排序樹是結束21M主要模塊:1）主函數(shù)模塊Main()建立n個關鍵字的二叉排序樹并輸出；從二叉樹排序樹T中刪除任意結點，其關鍵字為紹；在二叉樹排序樹T中，插入一個結點，其關鍵字為右；在二叉排序樹T中遞歸查找關鍵字等于郵的數(shù)據(jù)元

6、素;2)創(chuàng)建二叉排序樹模塊B腿 CeaBSW n)建立n個關鍵字的二叉排序樹；從鍵盤輸入調建立n個關鍵字依次用為初tBST7(插入函數(shù));返回根結點T；輸出過程；M)刪除模塊DeteNodeCBUnee &T, int x)從二叉樹排序樹7中刪除任意結點，其關鍵字為.；可以實現(xiàn)刪除根結點、葉子結點以及其它任意結點的功能；4）插入模塊void InerBSF（B7re &7,Bi7Nde 物在二叉樹排序樹7中，插入一個結點s（遞歸算法）；被CneatBS7函數(shù)調用；5）查找模塊Bi7re seanchBS71（B7nee 7,7EEyp key）在根指針7所指二叉排序樹中遞歸查找關鍵字等于她的數(shù)

7、據(jù)元素;若成功，返回指向該數(shù)據(jù)元素結點的指針；否則返回空指針；源程序代碼:#inclodeusing name space std;typedef int KeyType;typedef struct tree/ 聲明樹的結構struct tree *lft /存放左子樹的指針struct tree night; 存放又子樹的指針KeyType key; /存放節(jié)點的內容 BSTNd * BSW /聲明二叉樹的鏈表BSTree inettBST(BSTiee tptr/KeyType key)/ 在二叉排序樹中插入結點/若二叉排序樹慚中沒有關鍵字為紹的結點，則插入，否則直接返回BSTree f

8、,阡咿;/p的初值指向根結點whie(p)/查找插入位置，循環(huán)結束時，p是空指針，f指向待插入結點的雙親if(p-key=key) /樹中已有 紹，無須插入return tptr;f=p; /f保存當前查找的結點，即f是p的雙親fr=(BSTnee )mdlc(5僧STNd); /生成新結點p-key=key; p-left=p-ncght=NULL;if(tptr=NULL) /原樹為空，新插入的結點為新的根華冗二p;elsef(keykey)if(keykey)f-left=p；elsef-ri佩二p；return tptr;BSTree eneateBSTO/建立二叉樹BSTnee t=

9、NULL; /根結點KeyType key;einkey;l=cn4entBST(t,key);l=cn4entBST(t,key);w4cle(key!=-1)return t;void in&Jtg(BSTg 51中序遍歷打印二叉排序樹4(p!=NUU)(4(p!=NUU)(left );left );keycout keynight );int seanchBSTCBSTnee t,KeyType key)/查找if(key=t-key)if(key=t-key)inorder_btree(p-rcght );int seanchBSTCBSTnee t,KeyType key)/查找4

10、(t=NUU)4(t=NUU)return 1;if(keykey)if(keykey)netunn 0;seanchBST(t-left,key);netunn seanchBST(lef,key);elseBSTree deleteBSTBSTree tptr,KeyType 龍y/刪除BSTree p,tmp,panent=NULL;p=tptr;4(p-ky=ky)4(p-ky=ky)while(p)break;pnent二p；if(fp) return NtLL;if(fp) return NtLL;else cf(p=pannt-right)tmp=p;4（畢-叫農&畢-/*p的左

11、右子樹都為空*/（4（!g） /要刪根，須修改根指針tptn=NULL;else cf(p=pannt-right)panen-rcght=NULL;elsepanen-left=NULL;fnee(p);char cmd;BSTree root;do(c&utnnendl;couttt請選擇你要執(zhí)行的操作,endl；ccotnendl;eootVgt C創(chuàng)建一棵二叉排序樹n, coot% E.結束本程序n;endl;coutnntt* fag=0;do(4(fag/=0)coutcmd;f+;、Wde(cmd!=&cmd!=C&cmd!=a&cmd!=AJ;cf(cmd=ecmd=C)叱請輸

12、入你所要創(chuàng)建的二叉樹的結點的值，以-/結束：n, noot=cneateBST(); do (flag=0；叱Mn中序遍歷二叉樹:edcnondet_bttee(noot);eoatVnVVendl;cou(tt*請選擇你要對這棵二叉樹所做的操 作：end/.coutlt*endl;eoutt*S查找你想要尋找的結點*edeoutt*I插入你想要插入的結點*泓;eoutt*D刪除你想要刪除的結點*endl;eoutt*2結束對這棵二叉樹的操作*edcoutlt*蛔;cout tt*endldo4(fag!=0)叱選擇操作錯誤！請重新選擇！ n;ffu戰(zhàn)(sdn);saf(%c”,&cmd);f

13、lag+;Me(她!= S &cmd!= S &md!= i &cmd!=I &cmd!= d &cmd!2 &cmd!= q &md!= 2 ); swctch(emd)case s：case S：eootkey;teS=seawhBS7(noot,key);if(test=0)叱七對不起，你所查找的結點ykey不存在尸；else如七成功找到結點n紹”,break;case i:case I:站TVV請輸入你要插入結點的關鍵字：n,cinkey;noot=cnsentBST(noot,key); /注意必須將值傳回根break;case d: case Dcoot輸入你要刪除結點的關鍵字：W

14、, cinkey;noot=deleteBST(noot,key); /注意必須將值傳回根4(rot=NULL)翊七對不起，你所刪除的結點”右”不存在A/,elsen成功刪除結點key如。成功刪除結點key;whde(cmd!=q&cmd!=2);whde(cmd!=q&cmd!=2);、we(cmd!=e&cmd!=E);、we(cmd!=e&cmd!=E);break;netum 0;實驗內容3.4測試用例：/,程序運行時菜單顯示如下:當輸入的二叉樹序列為：2,698,4時，創(chuàng)建二叉排序樹，并輸出結果如下:中序遍歷二叉樹:24&8請選擇你要對這棵二叉樹所做的操作*S.*I *D.*Q.-.

15、KJOCKJOCKKKKKKKKJCKJOCKJOOtJOOOCKKKKKKJCKJOCKJOOtJOOOCKKKKKKJCKKZ查找9結點時，運行結果如下:請選擇你要對這棵二叉樹所做的操作JC J JOC K JOC K作 占點占漆 結結結的 找A除叉 尋孺二 要要暮 想想想這 SS 查MKMMKMKMMXMKXMXMKXMXMMXMMMMXMMMMMMKMMXMKKMXMKXMXMKXKX2刪除結點6時運行結果如下:D:Pr-ogram FilesMicrosoft Vrsual StudicMyPrqjject5yuesefuDebugyuese.1請輸入你要刪除結點的關鍵字，成功刪除結

16、點6中序遍歷二叉樹;2489M-M-請選擇你要對這棵二叉樹所做的操作:WWWWWWMW想想想這對 找入鑒占5點占操 結結結的 w:的的樹 找入除叉 尋S3二三插入結點7時運行結果如下:D:Pr-ogram FilesMicrosoft Visual StudicMyProjectsyuesefuDebLigyLiese.請輸入你要插入結點的關鍵字:7中序遍歷二叉樹;2478XKJOCJOOOt請選擇你要對這棵二叉樹所做的操作作 占5點占操 結結結的 找A除叉 #1- 要要矗 想想想這 SS 找入纂rrr實驗內容實驗總結通過這次的實驗，我認識到：僅僅掌握課本上的知識是不夠的，在實際操作時，常常

17、遇到一些問題，自己看不懂，更無法解決。不過，經(jīng)過自己不斷的思考，嘗試著去更改代 碼中出現(xiàn)的問題。雖然開始很困難，但在老師和同學的幫助下，我逐漸的熟悉了許多操作， 為后繼工作的順利進行做了準備。個人的力量是薄弱的，我學會了咨詢別人，不再膽怯，不再保守。 在過程中和同學 相互討論，詢問老師，不斷進步。也許，我們可以說，編一個程僅僅是開始，調試和運行相比之下更難。實踐中收獲的 遠比想象的多?？吹阶约和瓿闪怂蟮娜蝿眨幸环N無法用言語來形容的欣慰之感，這也是無法從學 習書本知識中得到的。致謝本設計是在指導教師劉作軍老師和寇海洲老師的親切關懷和細心指導下完成的。劉作 軍老師從設計方案的選定，設計計劃的安排，都給予了精心的指導及嚴格的要求?？芎Ｖ?老師在實驗過程中給予了我們很大的支持與幫助。這個算法設計和報告的完成，凝結著兩 位老師的心血和汗水。二位老師嚴謹?shù)闹螌W態(tài)度，開拓性的工作作風和科學的思維方法都 使我受益非淺。二位老師對我的設計和報告給予了莫大的關心和幫助，在此，我表示衷心 的感謝和誠摯的謝意。在設計過程中也得到了同學們的指點和幫助，特別是在編程中遇到技術性問題的時候， 同學的指點使我茅塞頓開，順利的解決了問題。在此我表示誠摯的感謝。參考文獻1.錢能舛+程序設計教程（修訂版），北京：清華大學出