數(shù)據(jù)結(jié)構(gòu)課設(shè)-二叉排序樹

1、課程設(shè)計(論文)任務(wù)書 學(xué)院 專業(yè) 班 一、課程設(shè)計(論文)題目 二、課程設(shè)計(論文)工作自 年 月 日起至 年 月 日止。三、課程設(shè)計(論文) 地點(diǎn): 四、課程設(shè)計(論文)內(nèi)容要求：1本課程設(shè)計的目的（1）使學(xué)生熟練掌握抽象數(shù)據(jù)類型的組織和定義； （2）使學(xué)生熟練掌握數(shù)據(jù)類型的定義和實(shí)現(xiàn)； （3）培養(yǎng)學(xué)生組織和分析數(shù)據(jù)的能力；（4）培養(yǎng)學(xué)生分析和應(yīng)用基于不同數(shù)據(jù)結(jié)構(gòu)的算法的能力；（5）提高學(xué)生的科技論文寫作能力。2基本要求：每位同學(xué)在以下題目中任選一題（在方框中打勾），獨(dú)立完成課程設(shè)計： 二叉排序樹：將輸入的n個關(guān)鍵字構(gòu)建成為一棵二叉排序樹，并按照層次輸出。 文檔檢索系統(tǒng)：實(shí)現(xiàn)一個信息檢索系

2、統(tǒng)，包含至少10條記錄。（1）每條記錄至少包含4個數(shù)據(jù)項(xiàng)（2）能夠按照不同數(shù)據(jù)項(xiàng)的關(guān)鍵字進(jìn)行查詢。 校園導(dǎo)游咨詢：參見數(shù)據(jù)結(jié)構(gòu)題集P151。3課程設(shè)計論文編寫要求（1）要按照書稿的規(guī)格打印謄寫課設(shè)報告；（2）報告分為封面、任務(wù)書（本文檔）、正文、課程設(shè)計體會和參考文獻(xiàn)四部分。學(xué)生簽名： 2014年 12月 22日課程設(shè)計(論文)評審意見（1）題目分析（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）； （2）流程分析（30分）：優(yōu)（）、良（）、中（）、一般（）、差（）； （3）數(shù)據(jù)定義（30分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（4）代碼編寫（10分）：優(yōu)（）、良（）、中（）、一般

3、（）、差（）；（5）創(chuàng)新能力（10分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（6）格式規(guī)范性、設(shè)計態(tài)度及考勤是否降等級：是（）、否（）評閱人： 職稱： 講 師 2014年12 月 31日正 文一、 數(shù)據(jù)結(jié)構(gòu)定義1. 抽象數(shù)據(jù)類型本設(shè)計中用到的數(shù)據(jù)結(jié)構(gòu)ADT定義如下：ADT BinaryTree 數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系 R：若D為空集，則稱為二叉樹；    若D僅含有一個數(shù)據(jù)元素，則R為空集，否則R=H，H是如下二元關(guān)系： (1) 在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)

4、系H下無前驅(qū)；  (2)  若D-rootNULL，則存在D-root的一個劃分D1,D2,D3, ,Dm(m>0)，對于任意jk(1j,km)有DjDk=NULL,且對任意的i(1im)，唯一存在數(shù)據(jù)元素xiDi有<root,xi>H; (3) 對應(yīng)于D-root的劃分，H-<root,xi>,<root,xm>有唯一的一個劃分H1，H2,Hm(m>0)，對任意jk(1j,km)有HjHk=NULL，且對任意i(1im),Hi是Di上的二元關(guān)系，(Di,Hi)是一棵符合本定義的樹，稱為根root

5、的子樹?；静僮鱌： CreateTree(&T,definition); 初始條件：definition給出二叉樹T的定義。 操作結(jié)果：按definition構(gòu)造二叉樹T。  InsertChild(&T,&p,I,c); 初始條件：樹存在，指向中某個結(jié)點(diǎn)，1ip指結(jié)點(diǎn)的度，非空樹與不相交。 操作結(jié)果：插入c為中指結(jié)點(diǎn)的第棵子樹。DeleteChild(&T,&p,i); 初始條件：樹T存在，p指向T中某個結(jié)點(diǎn)，1ip指結(jié)點(diǎn)的度。 操作結(jié)果：刪除中所指結(jié)點(diǎn)的第棵子

6、樹。 LevelOrderTraverse(T,visit(); 初始條件：樹T存在，visit是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)。 操作結(jié)果：層序遍歷T，對每個結(jié)點(diǎn)調(diào)用函數(shù)visit()一次且至多一次。一旦visit()失敗，則操作失敗。 ADT BinaryTree2. 存儲結(jié)構(gòu)定義數(shù)據(jù)存儲結(jié)構(gòu)的C語言定義如下：#define maxx 1000typedef struct node int key; struct node *lchild; struct node *rchild;BSTNode;3. 基本操作數(shù)據(jù)結(jié)構(gòu)的基本操作實(shí)現(xiàn)如下：/* 菜單界

7、面 */void showmenu() system("cls"); printf("nnnn"); printf("tt 請選擇你要進(jìn)行的操作 nn"); printf("ttn"); printf("tt n"); printf("tt 1.創(chuàng)建一顆具有 n 個元素的二叉排序樹 n"); printf("tt 2.層次輸出二叉樹 n"); printf("tt 3.查找元素 n"); printf("tt 4.插入元素 n

8、"); printf("tt 5.刪除元素 n"); printf("tt 6.退出程序 n"); printf("tt n"); printf("ttn");/* 向二叉排序樹中插入元素 */int InsertBST(BSTNode *&p,int k) if(p = NULL) p = (BSTNode *)malloc(sizeof(BSTNode); p->key = k; p->lchild = p->rchild = NULL; return 1; else if(

9、k = p->key) return 0; else if(k < p->key) return InsertBST( p->lchild , k); else if(k > p->key) return InsertBST( p->rchild , k); /*查看關(guān)鍵字k的深度*/int finddepth(BSTNode *p,int k,int depth) if(p != NULL) if(p->key = k) return depth; else if(k > p->key) return finddepth(p->

10、;rchild,k,depth+1); else if(k < p->key) return finddepth(p->lchild,k,depth+1); /* 二叉排序樹的層次遍歷 */void showBST(BSTNode *p) BSTNode *qmaxx; int top,back; top = back = 0; if(p != NULL) printf("n %d",p->key); else return ; q+back = p; BSTNode *Knode; int now = 1; while(back != top) t

11、op = (top + 1) % maxx; Knode = qtop; if(Knode->lchild != NULL) if(now != finddepth(p,Knode->lchild->key,1) printf("n"); now = finddepth(p,Knode->lchild->key,1); printf(" %d",Knode->lchild->key); back = (back + 1) % maxx; qback = Knode->lchild; if(Knode->

12、;rchild != NULL) if(now != finddepth(p,Knode->rchild->key,1) printf("n"); now = finddepth(p,Knode->rchild->key,1); printf(" %d",Knode->rchild->key); back = (back + 1) % maxx; qback = Knode->rchild; /a+i = &ai printf("n");/* 創(chuàng)建一顆具有 n 個數(shù)據(jù)元素的二叉排序樹*

13、/void CreateBSTNode(BSTNode *&p) system("cls"); int amaxx; int n, k; printf("請輸入一個整數(shù) n ："); scanf("%d",&n); int i = 0; printf("請輸入 n 個整數(shù)并以空格隔開："); for(i = 0;i < n; +i) scanf("%d",&ai); printf("正在向二叉排序樹中插入元素.n"); i = 0; while(

14、i < n) if(InsertBST(p,ai) = 1) printf("成功插入元素 %d:",ai); showBST(p); else printf("元素 %d 插入失??！n",ai); i+; printf("二叉排序樹創(chuàng)建完成!n"); system("pause"); showmenu();/* 從二叉排序樹中查找數(shù)據(jù)元素 k*/int searchBST(BSTNode *p,int k,int path,int i) if(p = NULL) return 0; if(p->key

15、 = k) printf("成功查找到關(guān)鍵字 %d ,其路徑為: ",k); int j = 0; pathi+ = p->key; printf(" %d",path0); for(j = 1;j < i; +j) printf(" -> %d",pathj); printf("n"); return 1; pathi+ = p->key; if(p->key < k) return searchBST(p->rchild,k,path,i); else return s

16、earchBST(p->lchild,k,path,i); return 0;/* 當(dāng)數(shù)據(jù)元素 k 有左右子樹時的刪除過程 */void deleteBST2(BSTNode *&p,BSTNode *&r) BSTNode *q; if(r->rchild = NULL) p->key = r->key; q = r; if(r->lchild = NULL)r = NULL; else r = r->lchild; free(q); else deleteBST2(p,r->rchild); /* 刪除數(shù)據(jù)元素 k */void d

17、eleteBST1(BSTNode *&p) BSTNode *q; if(p->lchild = NULL) q = p; p = p->rchild; free(q); return ; if(p->rchild = NULL) q = p; p = p->lchild; free(q); return ; deleteBST2(p,p->lchild);/* 查找要被刪除的數(shù)據(jù)元素 k */int deleteBST(BSTNode *&p,int k) if(p = NULL) return 0; else if(k > p->

18、key) return deleteBST(p->rchild,k); else if(k < p->key) return deleteBST(p->lchild,k); else deleteBST1(p); return 1; 二、 解題過程1. 問題分解該問題主要應(yīng)實(shí)現(xiàn)以下功能：1. 創(chuàng)建一顆具有 n 個關(guān)鍵字的二叉排序樹讀取一個整數(shù)n代表有n個關(guān)鍵字需要被儲存進(jìn)二叉排序樹中，然后通過調(diào)用函數(shù)把這n個關(guān)鍵字存進(jìn)一顆二叉排樹中2. 層次輸出該二叉樹要層次輸出二叉樹，就要先進(jìn)行層序遍歷該二叉樹，再在輸出完每一層的所有關(guān)鍵字之后進(jìn)行一次換行，并且每一個關(guān)鍵字之間有一個

19、空格。輸出來的每一層關(guān)鍵字將會左對齊。2. 模塊結(jié)構(gòu)系統(tǒng)主要由7個模塊組成，分別是：菜單模塊：界面展示模塊，顯示整個菜單二叉樹創(chuàng)建模塊：二叉排序樹創(chuàng)建模塊，創(chuàng)建一顆具有n個關(guān)鍵字的二叉排序樹關(guān)鍵字插入模塊：向二叉排序樹中插入關(guān)鍵字二叉樹輸出模塊：層次輸出該二叉排序樹關(guān)鍵字查詢模塊：在二叉排序樹中查詢關(guān)鍵字，并輸出路徑關(guān)鍵字刪除模塊：刪除該二叉排序樹中的關(guān)鍵字退出模塊:一個break語句，跳出循環(huán)模塊之間的結(jié)構(gòu)如下：主函數(shù)菜單模塊關(guān)鍵字刪除模塊退出模塊關(guān)鍵字查詢模塊二叉樹輸出模塊關(guān)鍵字插入模塊二叉樹創(chuàng)建模塊退出程序3. 解題思路各模塊的實(shí)現(xiàn)步驟為菜單模塊：用一連串的printf( )語句輸出一個

20、可視化的操作界面而已，除此之外該模塊本身沒有任何其他功能二叉樹創(chuàng)建模塊：首先，初始化一顆二叉樹，然后根據(jù)要求，要創(chuàng)建一個具有n個關(guān)鍵字的二叉排序樹，所以在此模塊中，需要輸入一個n，代表有n個關(guān)鍵字需要輸入，然后輸入n個關(guān)鍵字，這n個關(guān)鍵字用一個數(shù)組a儲存，因?yàn)闊o法確認(rèn)輸入的n有多大，所以盡量把數(shù)組a的范圍開大一點(diǎn)，在本程序中我把數(shù)組a的儲存大小開到了1000 。如果需要，還可以開到更大。當(dāng)把關(guān)鍵字成功存放在數(shù)組中后，就可以遍歷一遍數(shù)組，并調(diào)用InsertBST( )函數(shù)（該函數(shù)的實(shí)現(xiàn)過程會在下面的插入模塊中進(jìn)行詳細(xì)的解釋）把關(guān)鍵字一個一個插入到我們創(chuàng)建的二叉樹中，并在插入成功后調(diào)用showBS

21、T( )函數(shù)（該函數(shù)的實(shí)現(xiàn)過程在輸出模塊中）把當(dāng)前的二叉樹狀態(tài)輸出來。當(dāng)然，如果插入失敗了，則會提示哪個關(guān)鍵字插入失敗！總之，該模塊其實(shí)就是通過調(diào)用其他模塊來實(shí)現(xiàn)二叉樹的創(chuàng)建功能的。關(guān)鍵字插入模塊：我主要是通過遞歸來實(shí)現(xiàn)關(guān)鍵字的插入功能的。根據(jù)二叉排序樹的性質(zhì)，根節(jié)點(diǎn)儲存的關(guān)鍵字一定大于左子樹中所有存在的關(guān)鍵字，一定小于右子樹中所有存在的關(guān)鍵字。所以，便可通過遞歸，去查找即將要插入的關(guān)鍵字的位置在哪里。即：從根節(jié)點(diǎn)開始，判斷所要插入的關(guān)鍵字和根節(jié)點(diǎn)的關(guān)鍵字的大小關(guān)系，如果當(dāng)前節(jié)點(diǎn)關(guān)鍵字大于我們所要插入的關(guān)鍵字，則去把所要插入的關(guān)鍵字放入到左子樹中進(jìn)行遞歸。如果小于，則把所要插入的關(guān)鍵字放入到右

22、子樹中進(jìn)行遞歸。直到找到一個為“空”的指針，就把我們要插入的關(guān)鍵字放到該節(jié)點(diǎn)的數(shù)據(jù)域上，并返回1，表示關(guān)鍵字插入成功。當(dāng)然，也有可能找到一個與所需要插入的關(guān)鍵字相等的節(jié)點(diǎn)，出現(xiàn)這種情況時則返回0，代表插入關(guān)鍵字失敗，因?yàn)樵撽P(guān)鍵字已經(jīng)在該二叉樹中了，不必再插入了。二叉樹輸出模塊：要實(shí)現(xiàn)二叉樹的層次輸出，要做的便是兩件事。1. 層序遍歷該二叉排序樹。 2. 輸出完每一層的最后一個關(guān)鍵字后要進(jìn)行換行。完成第一個要求很簡單，我用的方法是定義一個數(shù)組，用來模擬隊列。首先把根節(jié)點(diǎn)放入隊列中。用一個while( )循環(huán)開始進(jìn)行遍歷，遍歷的方法為：查看當(dāng)前隊頭節(jié)點(diǎn)的左（右）子樹是否為“空”，如果為空則不做處理

23、，不為空則把左（右）子樹的指針放入到隊尾，并把左右子樹節(jié)點(diǎn)所儲存的關(guān)鍵字輸出到窗口中。其中，while( )循環(huán)結(jié)束的條件為：隊列為空即跳出。因?yàn)楫?dāng)隊列為空時，便表示已經(jīng)把所有節(jié)點(diǎn)訪問了一遍。至于第二件事，輸出完每一層的最后一個關(guān)鍵字后要進(jìn)行換行。我原本的想法是用一個函數(shù)計算樹的每一層的關(guān)鍵字的個數(shù)，并且把他存儲到一個宏定義的數(shù)組里，每次輸出結(jié)完一層的關(guān)鍵字?jǐn)?shù)量后便進(jìn)行換行，不過這樣寫實(shí)在太麻煩了。所以我改進(jìn)的想法是，再寫一個finddepth(BSTNode *p,int k,int depth) 函數(shù)，用來查詢關(guān)鍵字所在的深度。而finddepth( ) 函數(shù)的實(shí)現(xiàn)方法為，令depth初始

24、值為1，把被查詢的關(guān)鍵字 k 和當(dāng)前節(jié)點(diǎn)的關(guān)鍵字進(jìn)行比較，如果被查詢的關(guān)鍵字大（?。┯诋?dāng)前節(jié)點(diǎn)的關(guān)鍵字則對左（右）子樹進(jìn)行遞歸，并且令 depth+1 ，如果相等，就說明找到了被查詢的關(guān)鍵字，則返回depth 。depth便是該關(guān)鍵字的深度！而要到達(dá)換行的目的，則還需要在輸出模塊中的隊列那個循環(huán)外面再加一個now變量，用來儲存當(dāng)前節(jié)點(diǎn)的深度，在輸出層序遍歷輸出的時候，對每一個找到的關(guān)鍵字做一個判斷，即，查看該關(guān)鍵字的深度是否和now相等，如果不相等則換行，并且把now進(jìn)行更新，如果相等則不做處理。以上，便是我的二叉排序樹的層次輸出的思路。關(guān)鍵字查詢模塊：用一個searchBST(BSTNode

25、 *p,int k,int path,int i) 函數(shù)進(jìn)行遞歸查找關(guān)鍵字 k ，其中path數(shù)組用來儲存查找的路徑，i表示“路徑”上節(jié)點(diǎn)的個數(shù)。至于遞歸的方法，則是把被查詢的關(guān)鍵字 k 和當(dāng)前節(jié)點(diǎn)的關(guān)鍵字進(jìn)行比較，如果被查詢的關(guān)鍵字大（?。┯诋?dāng)前節(jié)點(diǎn)的關(guān)鍵字則對左（右）子樹進(jìn)行遞歸，找到了k則輸出所有路徑并返回1，沒有找到則直接返回0。關(guān)鍵字刪除模塊：因?yàn)閯h除關(guān)鍵字后，要使得該二叉樹依舊是二叉排序樹，所以要進(jìn)行刪除操作時需要考慮到4種情況。這4種情況分別為：1. 被刪除的關(guān)鍵字所在的節(jié)點(diǎn)沒有左右子樹時，則直接刪除該節(jié)點(diǎn)即可。 2. 被刪除的關(guān)鍵字所在的節(jié)點(diǎn)“只”有左子樹或者右子樹，則只需要把

26、左子樹或者右子樹接到被刪除節(jié)點(diǎn)的雙親節(jié)點(diǎn)上即可。3. 被刪除的關(guān)鍵字所在的節(jié)點(diǎn)既有左子樹又有右子樹，那么，就需要進(jìn)行特殊的替換了，通過遞歸查找被刪除節(jié)點(diǎn)的左子樹的最右節(jié)點(diǎn)。把該最右節(jié)點(diǎn)的關(guān)鍵字直接替換原節(jié)點(diǎn)的關(guān)鍵字，再把最右節(jié)點(diǎn)的左子樹接到最右節(jié)點(diǎn)的雙親節(jié)點(diǎn)上。4. 被刪除的關(guān)鍵字不在該二叉排序樹中,此時則不做處理。三、 實(shí)現(xiàn)代碼及注釋#include <stdio.h>#include <windows.h>#include <malloc.h>#include <conio.h>int main( ) BSTNode *p = NULL; i

27、nt amaxx; int n, i; showmenu(); while(1) int c; c = getch(); c = c - '0' if(c = 1) CreateBSTNode(p); else if(c = 2) printf("該二叉樹的層次遍歷為："); showBST(p); system("pause"); showmenu(); else if(c = 3) int k; int pathmaxx; printf("請輸入你要查找的元素："); scanf("%d",&a

28、mp;k); if(searchBST(p,k,path,0) printf("元素 %d 在該二叉樹中存在！n"); else printf("元素 %d 在該二叉樹中不存在！n"); system("pause"); showmenu(); else if(c = 4) system("cls"); int k; while(1) printf("請輸入你要插入的數(shù)據(jù)元素："); scanf("%d",&k); if(InsertBST(p,k) = 1) pri

29、ntf("成功插入元素 %d:",k); showBST(p); printf("n"); else printf("元素 %d 插入失??！nn",k); int x; printf("是否需要繼續(xù)插入數(shù)據(jù)元素？ 1.是 2.否nn"); x = getch(); x -= '0' if(x = 2) break; showmenu(); else if(c = 5) system("cls"); int k; while(1) printf("請輸入你要刪除的數(shù)據(jù)元素

30、："); scanf("%d",&k); if(deleteBST(p,k) printf("成功刪除元素 %d!n"); printf("現(xiàn)在該二叉樹如下："); showBST(p); printf("n"); else printf("刪除失??！二叉樹中沒有該元素！"); int x; printf("是否需要繼續(xù)刪除數(shù)據(jù)元素？ 1.是 2.否nn"); x = getch(); x -= '0' if(x = 2) break; showmenu(); else if(c = 6) break; else printf("您輸入的指令有誤，請重新輸入！n"); return 0;四、 實(shí)驗(yàn)結(jié)果1. 實(shí)驗(yàn)數(shù)據(jù)實(shí)驗(yàn)中輸入的數(shù)據(jù)如下（數(shù)據(jù)右邊的為解釋）：1 /