用順序和二叉鏈表作存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)二叉排序樹全代碼

1、精選優(yōu)質(zhì)文檔-傾情為你奉上安徽新華學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題目：用順序和二叉樹存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)二叉樹排序 學(xué)院：信息工程 專業(yè)：信息與計(jì)算科學(xué) 班級(jí)：12信科本一班 姓名：李智 學(xué)號(hào)： 指導(dǎo)教師：李明 設(shè)計(jì)時(shí)間： 2013-12-16至2013-12-30 課程設(shè)計(jì)任務(wù)書一 設(shè)計(jì)任務(wù)研究關(guān)于如何創(chuàng)建二叉排序樹并對(duì)樹進(jìn)行遍歷，查找和刪除等操作，同時(shí)關(guān)注用順序和二叉鏈表作存儲(chǔ)結(jié)構(gòu)帶來的區(qū)別。二 設(shè)計(jì)要求（1）. 利用順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種算法計(jì)算實(shí)現(xiàn)二叉搜索樹的創(chuàng)建。（2）. 利用順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種算法計(jì)算實(shí)現(xiàn)中序遍歷。（3）. 利用順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種算法計(jì)算實(shí)現(xiàn)查找結(jié)點(diǎn)。（4）. 利用順序存

2、儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種算法計(jì)算實(shí)現(xiàn)刪除結(jié)點(diǎn)。三 設(shè)計(jì)期限2013-12-16至2013-12-30前言數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等的學(xué)科。本課程設(shè)計(jì)中的二叉排序樹，可以用順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種算法計(jì)算。本課程設(shè)中的二叉排序樹，一共要實(shí)現(xiàn)四項(xiàng)基本的功能。它們分別是二叉搜索樹的創(chuàng)建、中序遍歷、查找結(jié)點(diǎn)和刪除結(jié)點(diǎn)。二叉樹是樹形結(jié)構(gòu)的一個(gè)重要的類型，二叉樹是n（n>=0）個(gè)結(jié)點(diǎn)的有限集，它或者是空集（n=0），或者由個(gè)根結(jié)點(diǎn)及兩棵互不相交的、分別稱作這個(gè)根的左子樹和右子樹的二叉樹組成。 二叉樹的存儲(chǔ)結(jié)構(gòu)和算法比較簡單，特別適合計(jì)算機(jī)處理。即使一

3、般形式的樹也可簡單的轉(zhuǎn)換為二叉樹。二叉樹的順序存儲(chǔ)結(jié)構(gòu)是把二叉樹的所有結(jié)點(diǎn)，按照一定的次序順序，存儲(chǔ)到一片連續(xù)的存儲(chǔ)單元中。遍歷二叉樹就是沿某有前序遍歷、中條搜索路徑周游二叉樹，對(duì)樹中每個(gè)結(jié)點(diǎn)訪問一次且僅訪問一次。在遍歷方案中主要序遍歷、后序遍歷。 現(xiàn)實(shí)中有許多應(yīng)用到二叉樹的例子，所以我們要把理論與現(xiàn)實(shí)結(jié)合起來。在學(xué)習(xí)中主要掌握怎么求二叉樹的高度、葉子結(jié)點(diǎn)個(gè)數(shù)、總結(jié)點(diǎn)個(gè)數(shù)以及熟練三種遍歷的方法。目 錄2. 5 總體設(shè)計(jì)流程圖3 專心-專注-專業(yè)1 需求分析1.1 問題的提出 研究關(guān)于如何創(chuàng)建二叉排序樹并對(duì)樹進(jìn)行遍歷，查找和刪除等操作，同時(shí)關(guān)注用順序和二叉鏈表作存儲(chǔ)結(jié)構(gòu)帶來的區(qū)別。1.2任務(wù)與分

4、析 用順序和二叉鏈表作存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)二叉排序樹：（1）以回車('n')為輸入結(jié)束標(biāo)志,輸入數(shù)列L，生成一棵二叉排序樹T；（2）對(duì)二叉排序樹T作中序遍歷，輸出結(jié)果；（3）輸入元素x,查找二叉排序樹T,若存在含x的結(jié)點(diǎn),則刪除該結(jié)點(diǎn),并作中序遍歷(執(zhí)行操作2)；否則輸出信息“無x”。2 總體設(shè)計(jì)2.1二叉排序樹的建立建二叉樹的結(jié)點(diǎn)至少應(yīng)當(dāng)包含三個(gè)域，分別存放結(jié)點(diǎn)的數(shù)據(jù)data，左子女結(jié)點(diǎn)指針leftChild和右子女結(jié)點(diǎn)指針rightChild。整個(gè)二叉樹的鏈表要有一個(gè)表頭指針，它指向二叉樹的根結(jié)點(diǎn)，其作用是當(dāng)作樹的訪問點(diǎn)從空的二叉排序樹開始，經(jīng)過一系列的查找插入操作以后，生成了一棵

5、二叉排序樹。根據(jù)二叉排序樹的定義，建立一棵二叉排序樹的過程是按照待排序序列元素的先后次序，不斷動(dòng)態(tài)生成二叉樹的結(jié)點(diǎn)，逐個(gè)插入到二叉樹中。若p為根結(jié)點(diǎn)指針，b為當(dāng)前待插入元素，其過程可以描述為：若為空樹（p=nil），動(dòng)態(tài)生成一個(gè)結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)楫?dāng)前待插入元素b，左、右指針域?yàn)椤翱铡?，p指向該結(jié)點(diǎn)。若非空樹，比較b與根結(jié)點(diǎn)數(shù)據(jù)data（p）如果b<data(p), 將b插入左子樹中；如果bdata(p)，將b插入右子樹中；左、右子樹的插入方式與二叉排序樹的插入方式相同。不斷調(diào)用上述的插入過程，直到所有待排序序列均排入后，就形成一棵二叉排序樹。由此可見，建立二叉排序樹就是多次調(diào)用二叉排序樹的

6、插入算法。2.2二叉排序樹的中序遍歷中序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則中序遍歷左子樹（L）；訪問根結(jié)點(diǎn)（V）；中序遍歷右子樹（R）。中序遍歷二叉樹也采用遞歸函數(shù)的方式，先訪問左子樹,然后訪問根結(jié)點(diǎn),最后訪問右子樹.直至所有的結(jié)點(diǎn)都被訪問完畢。2.3二叉排序樹中元素的查找在二叉排序樹上進(jìn)行查找，是一個(gè)從根結(jié)點(diǎn)開始，沿某一個(gè)分支逐層向下進(jìn)行比較判等的過程。它可以是一個(gè)遞歸的過程。假設(shè)我們想要在二叉排序樹中查找關(guān)鍵碼為x的元素，查找過程從根結(jié)點(diǎn)開始。如果根指針為NULL，則查找不成功；否則用給定值x與根結(jié)點(diǎn)的關(guān)鍵碼進(jìn)行比較；如果給定值等于根結(jié)點(diǎn)的關(guān)鍵碼，則查找成功，返回查找成功

7、的信息，并報(bào)告查找到的結(jié)點(diǎn)地址。如果給定值小于根結(jié)點(diǎn)的關(guān)鍵碼，則繼續(xù)遞歸查找根結(jié)點(diǎn)的左子樹；否則，遞歸搜索根結(jié)點(diǎn)的右子樹。2.4二叉排序樹中元素的刪除對(duì)于二叉排序樹，刪去樹上的一個(gè)結(jié)點(diǎn)相當(dāng)于刪去有序序列中的一個(gè)記錄，只要在刪除某個(gè)結(jié)點(diǎn)之后依舊保持二叉排序樹的特性即可。假設(shè)在二叉排序樹上被刪除結(jié)點(diǎn)為*p（指向結(jié)點(diǎn)的指針是p），其雙親結(jié)點(diǎn)為*f（結(jié)點(diǎn)指針為f），且不失一般性，可設(shè)*p是*f的左孩子，若*p結(jié)點(diǎn)為葉子結(jié)點(diǎn)，即p和l均為空，只需修改其雙親結(jié)點(diǎn)指針即可。若*p結(jié)點(diǎn)只有左子樹或者只有右子樹，只要令左子樹或右子樹直接成為其雙親結(jié)點(diǎn)即可。若左子樹和右子樹都不為空，令*p的直接前驅(qū)替代*p，然后

8、從二叉排序樹中刪除它的直接前驅(qū)，即可。2.5 總體設(shè)計(jì)流程圖 初始化輸入數(shù)據(jù)無X查找函數(shù)中序遍歷遍歷結(jié)果插入節(jié)點(diǎn)X1 2刪除節(jié)點(diǎn)存在含x的結(jié)點(diǎn)不存在輸出遍歷結(jié)果 4.1程序總體流程圖3詳細(xì)設(shè)計(jì) · Tnode的聲明typedef struct Tnode int data; struct Tnode *lchild,*rchild; *node,BSTnode;· searchBST的聲明searchBST(node t,int key,node f,node *p) if(!t)*p=f;return (0); else if(key=t->data) *p=t;r

9、eturn (1); else if(key<t->data) searchBST(t->lchild,key,t,p); else searchBST(t->rchild,key,t,p); · insertBST的聲明 insertBST(node *t,int key) node p=NULL,s=NULL; if(!searchBST(*t,key,NULL,&p) s=(node)malloc(sizeof(BSTnode); s->data=key; s->lchild=s->rchild=NULL; if(!p) *t=

10、s; else if(key<p->data) p->lchild=s; else p->rchild=s; return (1); else return (0);· inorderTraverse類的聲明inorderTraverse(node *t) if(*t) if(inorderTraverse(&(*t)->lchild) printf("%d ",(*t)->data); if(inorderTraverse(&(*t)->rchild); return(1) ;· Delete類

11、的聲明node Delete(node t,int key) node p=t,q=NULL,s,f; while(p!=NULL) if(p->data=key) break; q=p; if(p->data>key) p=p->lchild; else p=p->rchild; if(p=NULL) return t; if(p->lchild=NULL) if(q=NULL) t=p->rchild; else if(q->lchild=p) q->lchild=p->rchild; else q->rchild=p-&g

12、t;rchild; free(p); else f=p; s=p->lchild; while(s->rchild) f=s; s=s->rchild; if(f=p) f->lchild=s->lchild; else f->rchild=s->lchild; p->data=s->data; free (s); return t;3.1 中序遍歷模塊系統(tǒng)將提示用戶輸入新添加的數(shù)據(jù)，輸入結(jié)束后進(jìn)行中序遍歷關(guān)鍵代碼： inorderTraverse(node *t) /*中序遍歷函數(shù)*/ if(*t) if(inorderTraverse(

13、&(*t)->lchild) /*中序遍歷根的左子樹*/ printf("%d ",(*t)->data); /*輸出根結(jié)點(diǎn)*/ if(inorderTraverse(&(*t)->rchild); /*中序遍歷根的右子樹*/ return(1) ;3.2 刪除模塊系統(tǒng)將對(duì)用戶輸入的數(shù)進(jìn)行查找，查找到之后刪除此數(shù)，并對(duì)全部數(shù)據(jù)進(jìn)行中序遍歷。關(guān)鍵代碼：node Delete(node t,int key) /*刪除函數(shù)*/ node p=t,q=NULL,s,f; while(p!=NULL) /*查找要?jiǎng)h除的點(diǎn)*/ if(p->dat

14、a=key) break; q=p; if(p->data>key) p=p->lchild; else p=p->rchild; if(p=NULL) return t; /*查找失敗*/ if(p->lchild=NULL) /*p指向當(dāng)前要?jiǎng)h除的結(jié)點(diǎn)*/ if(q=NULL) t=p->rchild; /*q指向要?jiǎng)h結(jié)點(diǎn)的父母*/ else if(q->lchild=p) q->lchild=p->rchild; /*p為q的左孩子*/ else q->rchild=p->rchild;/*p為q的右孩子*/ free(p

15、); else /*p的左孩子不為空*/ f=p; s=p->lchild; while(s->rchild) /*左拐后向右走到底*/ f=s; s=s->rchild; if(f=p) f->lchild=s->lchild; /*重接f的左子樹*/ else f->rchild=s->lchild; /*重接f的右子樹*/ p->data=s->data; free (s);return t;4編碼與調(diào)試首先進(jìn)入VC+6.0，打開工程zjr.dsw，然后進(jìn)入源程序，也可以不打開工程，直接雙擊zjr文件夾下的zjr.exe文件即可運(yùn)行程

16、序。4.1 順序存儲(chǔ)圖7.1.1 打開程序，成功顯示提示信息圖7.1.2 輸入數(shù)據(jù)，以0結(jié)束輸入，操作成功圖7.1.3 功能1：中序輸出數(shù)據(jù)，操作成功圖7.1.4 功能2：刪除數(shù)據(jù)，顯示提示信息，操作成功圖7.1.5 刪除數(shù)據(jù)，操作成功圖7.1.6 重復(fù)執(zhí)行程序，操作成功4.2 二叉鏈表存儲(chǔ)圖7.2.1打開程序，顯示提示信息，操作成功圖7.2.2功能1：輸入數(shù)據(jù)，進(jìn)行中序遍歷，操作成功圖7.2.3功能2：輸入數(shù)據(jù)，進(jìn)行刪除，操作失敗，因?yàn)闆]有此數(shù)據(jù)，顯示 錯(cuò)誤信息圖7.2.4功能2：輸入數(shù)據(jù)，進(jìn)行中序遍歷，操作成功通過上述測試，本系統(tǒng)實(shí)現(xiàn)了二叉樹的生成，中序遍歷，查找刪除功能，能避免數(shù)據(jù)的輸入

17、錯(cuò)誤等。驗(yàn)證結(jié)果正確，說明其符合算法設(shè)計(jì)的要求：(1)正確性、可讀性、健壯性、效率與低儲(chǔ)存量需求.要寫一個(gè)優(yōu)質(zhì)的算法，就必須考慮其時(shí)間復(fù)雜度（它表示隨問題的規(guī)模n的增大，算法執(zhí)行時(shí)間的增長率和f（n）的增長率相同）和空間復(fù)雜度。遍歷二叉樹的算法中的基本操作是訪問結(jié)點(diǎn)，則不論按哪一次次序進(jìn)行遍歷，對(duì)含n個(gè)結(jié)點(diǎn)的二叉樹，其時(shí)間復(fù)雜度都為O（n）。所需空間為遍歷過程中棧的最大容量，即樹的深度，最壞情況下為n，則空間復(fù)雜度也為O（n）。5 總結(jié)這次課程設(shè)計(jì)使我對(duì)數(shù)據(jù)結(jié)構(gòu)認(rèn)識(shí)深刻了許多，其中最深刻的是我理解了用二叉鏈表結(jié)構(gòu)存儲(chǔ)實(shí)現(xiàn)二叉排序樹，同時(shí)也加深了對(duì)二叉樹的理解。本課程設(shè)計(jì)實(shí)現(xiàn)了二叉排序樹的創(chuàng)建、

18、中序遍歷、刪除二叉排序樹中某個(gè)結(jié)點(diǎn),。在進(jìn)行搜索時(shí)，還可以采用更好的搜索結(jié)構(gòu)即動(dòng)態(tài)搜索結(jié)構(gòu)。當(dāng)沒有找到時(shí)，可以將其插入，而不是僅僅提示未找到。通過這一次的課程設(shè)計(jì)，我已經(jīng)會(huì)用二叉鏈表存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)對(duì)二叉排序樹的的創(chuàng)建，中序遍歷，查找和某個(gè)刪除結(jié)點(diǎn)等基本操作。但我同時(shí)也發(fā)現(xiàn)了自己許多不足之處 。首先，對(duì)數(shù)據(jù)結(jié)構(gòu)的掌握還不夠。雖然完成了程序，但是只用到了基本的結(jié)點(diǎn)以及鏈表，在數(shù)據(jù)結(jié)構(gòu)的選擇上避重就輕，覆蓋面較小，不能很好的體現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)的掌握度，同時(shí)也缺少了適當(dāng)?shù)腻憻?，在這方面還需要自己主動(dòng)去提高。其次，在程序整體的設(shè)計(jì)上還不夠完善，各模塊可以適當(dāng)增加內(nèi)容，界面還可以更加的人性化些，這樣整個(gè)程序才

19、具有更強(qiáng)的美觀性與實(shí)用性?？偠灾@次課程設(shè)計(jì)給了我很大啟發(fā)，我明白了，不管遇到什么問題，只要抓住根源，不氣餒，從不同方面去攻破它，終究會(huì)成功，生活也是如此。在今后的工作、學(xué)習(xí)中我將認(rèn)真總結(jié)經(jīng)驗(yàn)教訓(xùn)，努力使自己成為一名技術(shù)過硬、工作嚴(yán)謹(jǐn)、思維活躍的工程人員，為提高人們的生活質(zhì)量做出更大的貢獻(xiàn)。心得體會(huì)課程設(shè)計(jì)結(jié)束了，在這次的課程設(shè)計(jì)中不僅檢驗(yàn)了我所學(xué)的知識(shí)，也培養(yǎng)了我如何去把握一件事情，如何去做一件事情，課程設(shè)計(jì)是我們專業(yè)課程知識(shí)綜合應(yīng)用的實(shí)踐訓(xùn)練是我們邁向社會(huì)，從事職業(yè)工作前一個(gè)必不可少的過程。我這次設(shè)計(jì)的科目是數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)，是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象（數(shù)據(jù)

20、元素）以及它們之間的關(guān)系和運(yùn)算等的學(xué)科，而且確保經(jīng)過這些運(yùn)算后所得到的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型。這次通過對(duì)二叉排序樹的深入研究，我又一次的溫習(xí)了c，c+和數(shù)據(jù)結(jié)構(gòu)的有關(guān)知識(shí)，盡管這中間經(jīng)歷好多困難，但我通過查找多種資料，利用網(wǎng)絡(luò)優(yōu)勢，完成了任務(wù)。我這次課程設(shè)計(jì)代碼中主要使用了鏈表的循環(huán)和遍歷這兩種操作。循環(huán)鏈表是單鏈表的另一種形式。遍歷是指沿著某條收索路線，依次對(duì)樹中每個(gè)節(jié)點(diǎn)均作一次且僅作一次訪問。通過這次的課程設(shè)計(jì)，更是讓我深刻認(rèn)識(shí)到自己在學(xué)習(xí)中的不足，同時(shí)也找到了克服這些不足的方法，這是一筆很大的資源。在以后的學(xué)習(xí)中，我們應(yīng)該利用更多的時(shí)間去上機(jī)實(shí)驗(yàn)，加強(qiáng)自學(xué)的能力、多編寫程序，相信不久

21、以后我們的編程能力都會(huì)有很大的提高，能創(chuàng)作出更多更完善更有新意的作品出來。參考文獻(xiàn)1 譚浩強(qiáng) 編著. 程序設(shè)計(jì). 北京:清華大學(xué)出版社，2000 2 王珊珊，張志航 編著. C+程序設(shè)計(jì)教程. 北京:機(jī)械工業(yè)出版社，20113 嚴(yán)蔚敏，吳偉民 編著. 數(shù)據(jù)結(jié)構(gòu). 北京:清華大學(xué)出版社，2001全部代碼二叉鏈表結(jié)構(gòu)c#include<stdio.h>#include<stdlib.h>typedef struct Tnode int data; /*輸入的數(shù)據(jù)*/ struct Tnode *lchild,*rchild; /*結(jié)點(diǎn)的左右指針，分別指向結(jié)點(diǎn)的左右孩子*/

22、*node,BSTnode;searchBST(node t,int key,node f,node *p) /*查找函數(shù)*/ if(!t)*p=f;return (0); /*查找不成功*/else if(key=t->data) *p=t;return (1); /*查找成功*/ else if(key<t->data) searchBST(t->lchild,key,t,p); /*在左子樹中繼續(xù)查找*/else searchBST(t->rchild,key,t,p); /*在右子樹中繼續(xù)查找*/insertBST(node *t,int key) /*插

23、入函數(shù)*/ node p=NULL,s=NULL; if(!searchBST(*t,key,NULL,&p) /*查找不成功*/ s=(node)malloc(sizeof(BSTnode); s->data=key; s->lchild=s->rchild=NULL; if(!p) *t=s; /*被插結(jié)點(diǎn)*s為新的根結(jié)點(diǎn)*/ else if(key<p->data) p->lchild=s;/*被插結(jié)點(diǎn)*s為左孩子*/ else p->rchild=s; /*被插結(jié)點(diǎn)*s為右孩子*/ return (1); else return (0)

24、;/*樹中已有關(guān)鍵字相同的結(jié)點(diǎn)，不再插入*/ inorderTraverse(node *t) /*中序遍歷函數(shù)*/ if(*t) if(inorderTraverse(&(*t)->lchild) /*中序遍歷根的左子樹*/ printf("%d ",(*t)->data); /*輸出根結(jié)點(diǎn)*/ if(inorderTraverse(&(*t)->rchild); /*中序遍歷根的右子樹*/ return(1) ;node Delete(node t,int key) /*刪除函數(shù)*/ node p=t,q=NULL,s,f; while

25、(p!=NULL) /*查找要?jiǎng)h除的點(diǎn)*/ if(p->data=key) break; q=p; if(p->data>key) p=p->lchild; else p=p->rchild; if(p=NULL) return t; /*查找失敗*/ if(p->lchild=NULL) /*p指向當(dāng)前要?jiǎng)h除的結(jié)點(diǎn)*/ if(q=NULL) t=p->rchild; /*q指向要?jiǎng)h結(jié)點(diǎn)的父母*/ else if(q->lchild=p) q->lchild=p->rchild; /*p為q的左孩子*/ else q->rchi

26、ld=p->rchild;/*p為q的右孩子*/ free(p); else /*p的左孩子不為空*/ f=p; s=p->lchild; while(s->rchild) /*左拐后向右走到底*/ f=s; s=s->rchild; if(f=p) f->lchild=s->lchild; /*重接f的左子樹*/ else f->rchild=s->lchild; /*重接f的右子樹*/ p->data=s->data; free (s); return t;void main() node T=NULL; int num; int

27、 s=0,j=0,i=0; int ch=0; node p=NULL; printf("輸入一串?dāng)?shù)，每個(gè)數(shù)以空格分開:"); do scanf("%d",&num); if(!num) printf("完成輸入!n"); else insertBST(&T,num); while(num); printf("n 1: 中序輸出"); printf("n 2: 輸入元素"); while(ch=ch) scanf("%d",&ch); switch(c

28、h) case 0: exit(0); /*0退出*/ case 1: printf(" 中序遍歷輸出結(jié)果為:n "); inorderTraverse(&T); /*1中序遍歷*/ break; case 2: printf(" 輸入元素x,查找二叉排序樹T,若存在含x的結(jié)點(diǎn),則刪除該結(jié)點(diǎn),并作中序遍歷，否則輸出無x :"); scanf("%d",&num); /*3刪除某個(gè)結(jié)點(diǎn)*/ if(searchBST(T,num,NULL,&p) T=Delete(T,num); printf(" 刪除成

29、功!中序遍歷輸出：n "); inorderTraverse(&T); else printf(" 無%d",num); break; default: printf("無此結(jié)點(diǎn)n"); break; /*輸入無效字符*/ 二叉鏈表結(jié)構(gòu)c+#include <iostream>using namespace std;class nodepublic: node(int i):data(i),left(NULL),right(NULL) void inorder(node *&root) /中序遍歷，符合升序輸出 if

30、(root!=NULL) inorder(root->left); cout<<root->data<<' ' inorder(root->right); void insert(node *&ptr,int item) /在查找樹中插入元素 if(ptr=NULL) ptr=new node(item); else if(item<ptr->data) insert(ptr->left,item); else insert(ptr->right,item); node *find(node *&

31、ptr,int item) /在查找樹中查找元素,找到返回所在結(jié)點(diǎn)指針，找不到返回空指針。 if(ptr=NULL) return NULL; if(ptr->data=item) return ptr; else if(item<ptr->data) find(ptr->left,item); else find(ptr->right,item); node *&findy(node *&ptr,int item) /在查找樹中查找肯定存在的元素,并返回其引用 if(ptr->data=item) return ptr; else if(i

32、tem<ptr->data) findy(ptr->left,item); else findy(ptr->right,item); node* rl()return left; node* rr()return right; void dele(node *&ptr) /刪除值為item所在結(jié)點(diǎn) if(ptr->rl()=NULL&&ptr->rr()=NULL) ptr=NULL; else if(ptr->rr()=NULL) ptr=ptr->rl(); else ptr=ptr->rr(); private

33、: int data; node *left; /左孩子結(jié)點(diǎn) node *right; /右孩子結(jié)點(diǎn);int main() int t,i=0,j; cout<<"輸入數(shù)字個(gè)數(shù)(結(jié)點(diǎn)個(gè)數(shù)):" cin>>t; cout<<"輸入"<<t<<"個(gè)數(shù)字，數(shù)字之間用空格隔開:" cin>>j; node *x=new node(j); for(;i<t-1;i+) cin>>j; x->insert(x,j); cout<<"

34、;中序遍歷為:" x->inorder(x); /作中序遍歷 cout<<"n輸入操作(當(dāng)輸入-1時(shí)程序結(jié)束):"<<endl; cin>>j; while(j!=-1) node *t=x->find(x,j); /定位結(jié)點(diǎn) if(t!=NULL) node *&y=x->findy(x,j); x->dele(y); cout<<"中序遍歷為:" x->inorder(x); else cout<<"無"<<j;

35、 cout<<"n輸入操作(當(dāng)輸入-1時(shí)程序結(jié)束):"<<endl; cin>>j; return 0;順序存儲(chǔ)結(jié)構(gòu)c#include"stdio.h"#include"malloc.h"#include"windows.h"#define endflag #define N 1000int bN;typedef struct int data;int other;int flag1;Link;void Build(Link aN)int w,i,j,k; for(i=0;i&l

36、t;=N;i+) ai.flag1=0; ai.data=0; printf("nttt 請(qǐng)輸入樹的根結(jié)點(diǎn)：");scanf("%d",&a1.data);a1.flag1=1;printf("nttt 請(qǐng)輸入結(jié)點(diǎn)個(gè)數(shù)：");scanf("%d",&k);for(j=1;j<=k;j+)printf("nttt 請(qǐng)輸入結(jié)點(diǎn)的數(shù)值：");scanf("%d",&w);printf("nttt 第%d位：%d",j,w);a0.d

37、ata=w;a0.flag1=1;i=1;if(a0.data<ai.data)loop:if(a2*i.flag1=0) a2*i.data=a0.data;a2*i.flag1=a0.flag1;if(a2*i.flag1=1)i=2*i;if(a0.data<ai.data)goto loop;if(a0.data>ai.data)goto loop1; if(a0.data<ai.data) loop1:if(a2*i+1.flag1=0) a2*i+1.data=a0.data;a2*i+1.flag1=a0.flag1;if(a2*i+1.flag1=1)i

38、=2*i+1;if(a0.data<ai.data)goto loop;if(a0.data>ai.data)goto loop1; void Sdel(Link aN)int i;int flag=0;int q;int number=1;int j=1;int bN;printf("nttt 請(qǐng)輸入需要?jiǎng)h除的結(jié)點(diǎn)的數(shù)值：");scanf("%d",&q);for(i=1;i<=N;i+)if(ai.data=q)ai.data=0;printf("nttt 已刪除%d：",q);flag=1;for(i=

39、1;i<=N;i+)if(ai.data!=0)bj=ai.data;j+;number+;for(i=1;i<=N;i+)ai.flag1=0;ai.data=0;a1.data=b1;a1.flag1=1;for(j=2;j<=number-1;j+)a0.data=bj;a0.flag1=1;i=1;if(a0.data<ai.data)loop:if(a2*i.flag1=0) a2*i.data=a0.data;a2*i.flag1=a0.flag1; if(a2*i.flag1=1)i=2*i;if(a0.data<ai.data)goto loop;if(a0.data>ai.data)goto loop1;if(a0.data>ai.data)loop1:if(a2*i+1.flag1=0)a2*i+1