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

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

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

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

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

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

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

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

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

9、NULL; /根結(jié)點(diǎn)KeyType key;einkey;l=cn4entBST(t,key);l=cn4entBST(t,key);w4cle(key!=-1)return t;void in&Jtg(BSTg 51中序遍歷打印二叉排序樹(shù)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（畢-叫農(nóng)&畢-/*p的左

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

12、入你所要?jiǎng)?chuàng)建的二叉樹(shù)的結(jié)點(diǎn)的值，以-/結(jié)束：n, noot=cneateBST(); do (flag=0；叱Mn中序遍歷二叉樹(shù):edcnondet_bttee(noot);eoatVnVVendl;cou(tt*請(qǐng)選擇你要對(duì)這棵二叉樹(shù)所做的操 作：end/.coutlt*endl;eoutt*S查找你想要尋找的結(jié)點(diǎn)*edeoutt*I插入你想要插入的結(jié)點(diǎn)*泓;eoutt*D刪除你想要?jiǎng)h除的結(jié)點(diǎn)*endl;eoutt*2結(jié)束對(duì)這棵二叉樹(shù)的操作*edcoutlt*蛔;cout tt*endldo4(fag!=0)叱選擇操作錯(cuò)誤！請(qǐng)重新選擇！ 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)叱七對(duì)不起，你所查找的結(jié)點(diǎn)ykey不存在尸；else如七成功找到結(jié)點(diǎn)n紹”,break;case i:case I:站TVV請(qǐng)輸入你要插入結(jié)點(diǎn)的關(guān)鍵字：n,cinkey;noot=cnsentBST(noot,key); /注意必須將值傳回根break;case d: case Dcoot輸入你要?jiǎng)h除結(jié)點(diǎn)的關(guān)鍵字：W

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

15、KJOCKJOCKKKKKKKKJCKJOCKJOOtJOOOCKKKKKKJCKJOCKJOOtJOOOCKKKKKKJCKKZ查找9結(jié)點(diǎn)時(shí)，運(yùn)行結(jié)果如下:請(qǐng)選擇你要對(duì)這棵二叉樹(shù)所做的操作JC J JOC K JOC K作 占點(diǎn)占漆 結(jié)結(jié)結(jié)的 找A除叉 尋孺二 要要暮 想想想這 SS 查MKMMKMKMMXMKXMXMKXMXMMXMMMMXMMMMMMKMMXMKKMXMKXMXMKXKX2刪除結(jié)點(diǎn)6時(shí)運(yùn)行結(jié)果如下:D:Pr-ogram FilesMicrosoft Vrsual StudicMyPrqjject5yuesefuDebugyuese.1請(qǐng)輸入你要?jiǎng)h除結(jié)點(diǎn)的關(guān)鍵字，成功刪除結(jié)

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

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