數(shù)據(jù)結(jié)構(gòu)二叉排序樹的實現(xiàn)(用順序和二叉鏈表作存儲結(jié)構(gòu))課程設計

1、課程名稱：數(shù)據(jù)結(jié)構(gòu)專業(yè)2計算機科學與技術指導老師:王岌班 級：10計科一班學 號：1010311114姓名：楊旭HUfffl UMIVfASHVnt TtCHHDIOGY計算機學院一、設計題目1、 題目：二叉排序樹的實現(xiàn)（用順序和二叉鏈表作存儲結(jié)構(gòu)）2、要求（功能）：1）以回車（n）為輸入結(jié)束標志，輸入數(shù)列L,生成一棵二叉排序樹T；2）對二叉排序樹T作中序遍歷，輸出結(jié)果；3）輸入元素X,查找二叉排序樹T,若存在含x的結(jié)點，則刪除該結(jié)點,并作中序遍歷（執(zhí)行操作2）;否則輸出信息 無X”；二、需求分析建立排序二叉樹，主要是建立節(jié)點來存儲輸入的數(shù)據(jù)，需要建立 函數(shù)來創(chuàng)造排序二叉樹。該題目包括三方面的

2、內(nèi)容：一個是二叉排序樹的建立，而是二叉 樹的中序遍歷，三是二叉樹元素的查找并刪除。三、數(shù)據(jù)結(jié)構(gòu)設計在寫算法之前，應對數(shù)據(jù)結(jié)構(gòu)進行設計。本體主要會用到指針變 量，插入節(jié)點函數(shù)和建立二叉樹，以及中序遍歷函數(shù)，還有一些輸入 輸出語句。四、算法設計算法設計思想二插鏈表作存儲結(jié)構(gòu)：建立二插排序樹采用邊查找邊插入的方式。查找函數(shù)采用遞歸的方式進行查找。如果查找成功則不應再插入 原樹，否則返回當前結(jié)點的上一個結(jié)點。然后利用插入函數(shù)將該元素 插入原樹。對二叉樹進行中序遍歷采用遞歸函數(shù)的方式。 在根結(jié)點不為空的 情況下，先訪問左子樹，再訪問根結(jié)點，最后訪問右子樹。刪除結(jié)點函數(shù)，采用邊查找邊刪除的方式。如果沒有查

3、找到， 則不對樹做任何的修改；如果查找到結(jié)點，則分四種情況分別進行討 論：1、該結(jié)點左右子樹均為空；2、該結(jié)點僅左子樹為空；3、該結(jié) 點僅右子樹為空；4、該結(jié)點左右子樹均不為空。在進行算法設計時，應將題目分為五個函數(shù)模塊:1、中序遍歷，符合升序輸出void inorder(node *&root)if(root!二NULL)ino rder(root-left);coutdataright);2、 在查找樹中插入元素void insert(node *&ptr,int item)if(ptr=NULL)ptr二new no de(item);else if(itemdata)i

4、n sert(ptr-left,item);else in sert(ptr-right,item);3、 在查找樹中查找元素node *find(node *&ptr,int item)if(ptr=NULL)return NULL;if(ptr-data=item)return ptr;else if(itemdata)fin d(ptr-left,item);else fin d(ptr-right,item);4、在查找樹中查找肯定存在的元素，并返回其引用node *&findy(node *&ptr,int item)if(ptr-data=item)retu

5、rn ptr;else if(itemdata)fin dy(ptr-left,item);else fin dy(ptr-right,item);no de* rl()return left;no de* rr()return right;5、刪除指定值為所在結(jié)點void dele (node *&ptr)if(ptr-rl()=NULL&ptr-rr()=NULL)ptr二NULL;else if(ptr-rr()=NULL)ptr=ptr-rl();elseptr=ptr-rr();private:int data;node *left;node *right;五、程序?qū)?/p>

6、現(xiàn)1、 調(diào)入文件#in clude 2、 主函數(shù)int mai n()int t,i=0,j;10計科一班 楊 旭(1010311114 endl;coutcout1.二叉排序樹T的輸入: t;coutvv輸入VVtVV個數(shù)字，數(shù)字之間用空格隔開：cinj;node *x=new no de(j);for(;ij;x-i nsert(x,j);coutvv中序遍歷為:;x-i norder(x);/作中序遍歷coutn;cout2.二叉排序樹T的元素查找和刪除:endl;coutn輸入操作(當輸入-1時程序結(jié)束):j;while(j!=-1)node *t=x-fi nd(x,j);/定位結(jié)點

7、if(t!二NULL)node *&y二x-fi ndy(x,j);x-dele(y);coutvv中序遍歷為：；x-i norder(x);else coutvv無j;coutvvn輸入操作(當輸入-1時程序結(jié)束):j;return 0;六、程序編碼#in clude using n amespace std;class node public:node(int i):data(i),left(NULL),right(NULL)void ino rder( node *&root)/中序遍歷，符合升序輸出if(root!=NULL)ino rder(root-left);co

8、utdataright);void in sert( node *&ptr,i nt item) /在查找樹中插入元素if(ptr=NULL)ptr二new no de(item);else if(itemdata)in sert(ptr-left,item);else in sert(ptr-right,item);node *find(node *&ptr,int item)在查找樹中查找元素，找到返回所在結(jié)點指針，找不到返回空指針。if(ptr=NULL)return NULL;if(ptr-data=item)return ptr;else if(itemdata)fi

9、n d(ptr-left,item);else fin d(ptr-right,item);node *&findy(node *&ptr,int item) /在查找樹中查找肯定存在的元素,并返回其引用if(ptr-data=item)return ptr;else if(itemdata)fin dy(ptr-left,item);else fin dy(ptr-right,item);no de* rl()retur n left;no de* rr()return right;void dele(node *&ptr)/刪除值為item所在結(jié)點if(ptr-rl

10、()=NULL&ptr-rr()=NULL)ptr二NULL;else if(ptr-rr()=NULL)ptr=ptr-rl();elseptr=ptr-rr();private:int data;n ode *left;/左孩子結(jié)點n ode *right;/右孩子結(jié)點;int mai n()int t,i=0,j;coutvv10計科一班 楊 旭(1010311114 endl;cout1.二叉排序樹T的輸入: t;coutvv輸入vvtvv個數(shù)字，數(shù)字之間用空格隔開：；ci nj;node *x=new no de(j);for(;ij;x-i nsert(x,j);coutv

11、v中序遍歷為：；x-i norder(x);/作中序遍歷coutn;cout2.二叉排序樹T的元素查找和刪除:endl;coutvn輸入操作(當輸入-1時程序結(jié)束):j;while(j!=-1)node *t=x-fi nd(x,j);/定位結(jié)點if(t!二NULL)node *&y二x-fi ndy(x,j);x-dele(y);coutvv中序遍歷為:;x-i norder(x);else cout無j;coutvvn輸入操作（當輸入-1時程序結(jié)束）:j;return 0;七、運行結(jié)果輸入節(jié)點數(shù)輸入二叉樹數(shù)，并輸出中序遍歷當輸入 25 時，二叉樹中無該數(shù)據(jù)，輸出無25輸入-1 表示

12、退出八、時間復雜度分析1、查找函數(shù)最壞的情況是要找的點正好是二叉樹的最深的葉子結(jié)點, 此時時間復雜度二 O (n)。2、插入函數(shù)最壞的情況是要插入的點正是二叉樹的最深的那一支的葉子結(jié)點，此時時間復雜度二 O (n)。3、中序遍歷函數(shù)，刪除函數(shù)，其時間復雜度均與以上情況類似，等于 05)。注：對時間復雜度的分析，均指在最壞情況下的時間復雜度。九、心得與體會這次數(shù)據(jù)結(jié)構(gòu)的課程設計作業(yè)在第15周作業(yè)布置下來的，但緊接 著是我們的英語四級考試，數(shù)字邏輯、離散數(shù)學等一系列考試，既要 做這次的課程設計，也要認真準備考試，因此時間非常緊。但基于我 對編程的極大興趣，我對這次的課程設計非常重視。通過這次實驗我

13、 也著實又感受了一次編程的樂趣，從中也學到了不少知識。雖然都說 程序=數(shù)據(jù)結(jié)構(gòu)+算法”但我在學習運用數(shù)據(jù)結(jié)構(gòu)編 程之前，并沒能深刻體會到這一點，直到這次課設實踐。我感受最深的一點是：以前用C、C+編程，只是注重如何編寫 函數(shù)能夠完成所需要的功能，似乎沒有明確的戰(zhàn)術，只是憑單純的意 識和簡單的語句來堆砌出一段程序。感覺有點像張飛打仗，有勇無謀， 只要能完成任務就行。但現(xiàn)在編程感覺完全不同了。在編寫一個程序 之前，自己能夠綜合考慮各種因素，首先選取自己需要的數(shù)據(jù)結(jié)構(gòu)， 是樹還是圖或是別的什么？然后選定一種或幾種存儲結(jié)構(gòu)來具體的 決定后面的函數(shù)的主要風格。最后在編寫每一個函數(shù)之前，可以仔細 斟酌比對，挑選出最適合當前狀況的算法。這樣，即使在完整的程序 還沒有寫出來之前，自己心中已經(jīng)有了明確的原圖了。 這樣無形中就 提咼了自己編寫的程序的質(zhì)量。另外，我還體會到深刻理解數(shù)據(jù)結(jié)構(gòu)的重要性。 只有真正理解這樣定 義數(shù)據(jù)類型的好處，才能用好這樣一種數(shù)據(jù)結(jié)構(gòu)。了解典型數(shù)據(jù)結(jié)構(gòu) 的性質(zhì)是非常有用的，它往往是編寫程序的關鍵。我以前對遞歸算法一直很害怕，總是看不明白究竟這遞歸是怎么進行 的。在這次實驗中我終于克服了這一障礙， 一次次單步執(zhí)行書中遞歸 函數(shù)的例子，并一遍遍在心中自己默默的走，終于弄明白了，真的是 功夫不負有心人?。⊥瑫r我