動態(tài)查找表(二叉排序樹)

1、北京理工大學珠海學院計算機學院課程設計 動態(tài)查找表 摘 要 數(shù)據(jù)結(jié)構(gòu)是研究與數(shù)據(jù)之間的關(guān)系我們稱這一關(guān)系為數(shù)據(jù)的邏輯結(jié)構(gòu)簡稱數(shù)據(jù)結(jié)構(gòu)。當數(shù)據(jù)的邏輯結(jié)構(gòu)確定以后數(shù)據(jù)在物理空間中的存儲方式稱為數(shù)據(jù)的存儲結(jié)構(gòu)。相同的邏輯結(jié)構(gòu)可以具有不同的存儲結(jié)構(gòu)因而有不同的算法。 本次課程設計程序中的數(shù)據(jù)采用“樹形結(jié)構(gòu)”作為其數(shù)據(jù)結(jié)構(gòu)。具體采用的是“二叉排序樹”并且使用“二叉鏈表”來作為其存儲結(jié)構(gòu)。本課程設計實現(xiàn)了二叉排序樹的創(chuàng)建、中序遍歷、插入、查找和刪除二叉排序樹中某個結(jié)點。 本課程主要實現(xiàn)動態(tài)查找表的功能通過“二叉排序樹”的算法和“二叉鏈表”的存儲結(jié)構(gòu)來實現(xiàn)。本課程設計說明書重點介紹了系統(tǒng)的設計思路、總體設計

2、、各個功能模塊的設計與實現(xiàn)方法。 關(guān)鍵詞數(shù)據(jù)結(jié)構(gòu) C語言 二叉排序樹 動態(tài) 二叉鏈表1北京理工大學珠海學院計算機學院課程設計 2目 錄 摘 要. 1 1 ABSTRACT. 323 抽象數(shù)據(jù)類型動態(tài)查找表定義 . 4 43 系統(tǒng)總體分析. 53.1系統(tǒng)模塊劃分 . 5 3.2 二叉樹的生成過程 . 5 3.3 主要功能模塊設計 . 5 3.4 系統(tǒng)詳細設計 . 7 3.4.1 主函數(shù)菜單模塊 . 7 3.4.2 查找模塊 . 10 3.4.3 刪除模塊 . 11 3.4.4 插入模塊 . 13 3.4.5 中序輸出模塊 . 15 參考文獻. 17 心 得 體 會. 18 教 師 評 語. 19

3、 附 錄. 202北京理工大學珠海學院計算機學院課程設計 1 Abstract(摘要)Data structure is the relationship between research and data, we call this relationship as a logical data structure, referred to as data structures. When the data logical structure is determined, the data stored in the physical space, is known as the data s

4、torage structure. The same logical structure can have different storage structure, which has a different algorithm. The curriculum design, program data is "tree" as its data structure. Specific uses "binary sort tree" and use "binary list" as its storage structure. The

5、course is designed to achieve a binary sort tree creation, in-order traversal, insert, find and delete a binary sort tree nodes. This course is mainly the function of dynamic look-up table, through the "binary search tree" algorithm and "binary list" of storage structures. This c

6、ourse is designed to highlight the system design concept, overall design, each functional module design and implementation. Keywords: C Language Data Structure Dynamic Binary Search Tree, Binary List 3北京理工大學珠海學院計算機學院課程設計 2 抽象數(shù)據(jù)類型動態(tài)查找表定義 ADT DynamicSearchTable 數(shù)據(jù)對象DD是具有相同特性的數(shù)據(jù)元素的集合。各個數(shù)據(jù)元素含有類型相同可唯一標識數(shù)

7、據(jù)元素的關(guān)鍵字。 數(shù)據(jù)關(guān)系R:數(shù)據(jù)元素同屬一個集合。 基本操作P InitDSTable(&DT); 操作結(jié)果構(gòu)造一個空的動態(tài)查找表DT。 DestroyDSTable&DT; 初始條件動態(tài)查找表DT存在。 操作結(jié)果銷毀動態(tài)查找表DT。 SearchDSTableDTkey; 初始條件動態(tài)查找表DT存在key為和關(guān)鍵字類型相同的給定值。 操作結(jié)果若DT中存在其關(guān)鍵字等于key的數(shù)據(jù)元素則函數(shù)值為該元素的值或在表中的位置否則為“空” 。 InsertDSTable&DTe; 初始條件動態(tài)查找表DT存在e為待插入的數(shù)據(jù)元素。 操作結(jié)果若DT中不存在其關(guān)鍵字等于e的數(shù)據(jù)元素則

8、插入e到DT。 DeleteDSTable&DTkey; 初始條件動態(tài)查找表DT存在key為和關(guān)鍵字類型相同的給定值。 操作結(jié)果若DT中存在其關(guān)鍵字等于key的數(shù)據(jù)元素則刪除之。 InOrderTraverse(DT); 初始條件動態(tài)查找表DT存在。 操作結(jié)果按中序的次序輸出DT中的每個結(jié)點數(shù)據(jù)值。 ADT DynamisSearchTable 4北京理工大學珠海學院計算機學院課程設計 5 3 系統(tǒng)總體分析 3.1系統(tǒng)模塊劃分 二叉排序樹是一種動態(tài)樹表。 二叉排序樹的定義二叉排序樹或者是一棵空樹 或者是一棵具有如下性質(zhì)的二叉樹 若它的左子樹非空則左子樹上所有結(jié)點的值均小于根結(jié)點的值 若

9、它的右子樹非空則右子樹上所有結(jié)點的值均大于根結(jié)點的值 左、右子樹本身又各是一棵二叉排序樹。 3.2 二叉樹的生成過程 二叉排序樹的生成采用遞歸方式的邊查找邊插入的方式。如圖 3.3 主要功能模塊設計 程序主要設計了五個功能首先是創(chuàng)建二叉排序樹完成后出現(xiàn)任務菜單菜單中設計了六個模塊查找刪除插入中序輸出清屏和退出。5北京理工大學珠海學院計算機學院課程設計 創(chuàng)建二叉排序樹N查找數(shù)據(jù)Switch(1) Y N刪除數(shù)據(jù)Switch(2) Y NSwitch(3)插入數(shù)據(jù) Y N中序輸出Switch(4) YSwitch(5) N清屏 Y NSwitch(6)退出 Y N輸出錯誤default Y N圖2

10、.3 主函數(shù)流程圖北京理工大學珠海學院計算機學院課程設計 3.4 系統(tǒng)詳細設計 3.4.1 主函數(shù)菜單模塊 該模塊功能主要是給用戶提供清晰的可操作界面易于人機操作并能很好的調(diào)用其他各模塊使程序更加優(yōu)化絲路更加清晰結(jié)構(gòu)更加明了提高了程序的實用性。其代碼如下 #include "BinaryTree.h" void main() BiTree T = NULL; int arr100; int n, i, k; int data; InitBiTree(T); printf("請輸入結(jié)點數(shù)"); scanf("%d", &n);

11、printf("請輸入數(shù)據(jù)"); for(i = 0; i < n; i+) /輸入要排序的數(shù)據(jù) scanf("%d", &arri); for(i = 0; i < n; i+) /構(gòu)造二叉排序樹 InsertBiTree(T,arri); printf("按中序輸出"); InOrderTraverse(T); /調(diào)用中序輸出函數(shù)將二叉排序樹按中序輸出 printf("n"); Z: /語句塊供用戶選擇操作7北京理工大學珠海學院計算機學院課程設計 printf("tt-n"

12、;); printf("tt| 功能菜單 |n"); printf("tt-n"); printf("tt| 1.查找數(shù)據(jù) |n"); printf("tt-n"); printf("tt| 2.刪除數(shù)據(jù) |n"); printf("tt-n"); printf("tt| 3.插入數(shù)據(jù) |n"); printf("tt-n"); printf("tt| 4.輸出有序序列 |n"); printf("tt-n

13、"); printf("tt| 5.清屏 |n"); printf("tt-n"); printf("tt| 6.退出 |n"); printf("tt-nn"); X: /該語句塊用于循環(huán)選擇 printf("請輸入選擇功能的序號"); V: /該語句塊用于輸入序號錯誤時重新輸入 scanf("%d", &k); /end V switch(k) case 1: printf("請輸入要查找的數(shù)據(jù)"); scanf("%d&q

14、uot;, &data); if(InsertBiTree(T, data) printf("不存在數(shù)據(jù)元素%dn", data); else8北京理工大學珠海學院計算機學院課程設計 printf("存在數(shù)據(jù)元素%dn", data); break; case 2: printf("請輸入要刪除的數(shù)據(jù)"); scanf("%d", &data); if(!DeleteBiTree(T, data) printf("不存在要輸出的數(shù)據(jù)%dn", data); else printf

15、("刪除操作成功n"); break; case 3: printf("請輸入要插入的數(shù)據(jù)"); scanf("%d", &data); if(!InsertBiTree(T, data) printf("要插入的數(shù)據(jù)%d已存在插入失敗n", data); else printf("插入操作成功n"); break; case 4: printf("有序序列為"); InOrderTraverse(T); printf("n"); break; c

16、ase 5: system("cls"); 9北京理工大學珠海學院計算機學院課程設計 10 goto Z; break; case 6: DestroyBiTree(T); exit(0); default: printf("輸入字符錯誤請重新輸入:"); goto V; /end switch printf("nn"); /end X goto X; /end Z 圖2.4.13.4.2 查找模塊 該模塊是給用戶提供查找功能。其查找過程是若二叉排序樹為空則查找失敗結(jié)束查找返回信息 NULL否則將要查找的值與二叉排序樹根結(jié)點的值進行比

17、較若相等則查找成功結(jié)束查找返回被查找到結(jié)點的地址若不等則根據(jù)要查找的值與根結(jié)值的大小關(guān)系決定時到根結(jié)點的左子樹還是右子樹中繼續(xù)查找查找過程同上直到查找成功或者查找失敗為止。其代碼如下: Status SearchBiTree(BiTree T, Elem key, BiTree f, BiTree &p) /在根指針T所指二叉排序樹中遞歸地查找某關(guān)鍵字等于key的數(shù)據(jù)元素 /若查找成功則指針p指向該數(shù)據(jù)元素結(jié)點并返回TRUE否則指針p /指向查找路徑上訪問的最后一個結(jié)點并返回FALSE指針f指向T的雙親其初始調(diào)用值為NULL if(!T) p = f; return FALSE; /查

18、找不成功 else if(key = T->data) p = T; return TRUE; /查找成功 else if(key < T->data) /在左子樹中繼續(xù)查找 return (SearchBiTree(T->left, key, T, p); else /在右子樹中繼續(xù)查找 return (SearchBiTree(T->right, key, T, p); 圖2.4.23.4.3 刪除模塊 刪除結(jié)點函數(shù)采用邊查找邊刪除的方式。如果沒有查找到則不對樹做任何的修改；如果查找到結(jié)點則分四種情況分別進行討論 A該結(jié)點左右子樹均為空可以直接進行刪除 B該結(jié)

19、點僅左子樹為空右子樹不為空用右子樹的根結(jié)點取代被刪除結(jié)點的位置 C該結(jié)點僅右子樹為空左子樹不為空 D該結(jié)點左右子樹均不為空找到被刪除結(jié)點左子樹中最大的結(jié)點并用該結(jié)點取代被刪除節(jié)點的位置。其代碼如下 Status Delete(BiTree &p) /從二叉排序樹中刪除結(jié)點p并重接它的左或右子樹 BiTree q, s; /q = (BiTree)malloc(sizeof(BiTree); /s = (BiTree)malloc(sizeof(BiTree); if(!p->right) /右子樹為空則重接它的左子樹 q = p; p = p->left; q->le

20、ft = NULL; / free(q); 有錯誤 else if(!p->left) /只需重接它的右子樹 q = p; p = p->right; q->right = NULL; / free(q); /有錯誤 else /左右子樹都不空 q = p; s = p->left; while(s->right) q = s; s = s->right; /轉(zhuǎn)右然后向右走到盡頭找到被刪點的“前驅(qū)” p->data = s->data; /s指向被刪結(jié)點的“前驅(qū)” s->data = NULL; if(q != p) q->right

21、 = s->left; /重接*q的右子樹 else q->left = s->left; /重接*q的左子樹任何的修改如果查找到結(jié)點則分四種情況分別進行討論 A該結(jié)點左右子樹均為空可以直接進行刪除 B該結(jié)點僅左子樹為空右子樹不為空用右子樹的根結(jié)點取代被刪除結(jié)點的位置 C該結(jié)點僅右子樹為空左子樹不為空 D該結(jié)點左右子樹均不為空找到被刪除結(jié)點左子樹中最大的結(jié)點并用該結(jié)點取代被刪除節(jié)點的位置。其代碼如下 Status Delete(BiTree &p) /從二叉排序樹中刪除結(jié)點p并重接它的左或右子樹 BiTree q, s; /q = (BiTree)malloc(siz

22、eof(BiTree); /s = (BiTree)malloc(sizeof(BiTree); if(!p->right) /右子樹為空則重接它的左子樹 q = p; p = p->left; q->left = NULL; / free(q); 有錯誤 else if(!p->left) /只需重接它的右子樹 q = p; p = p->right; q->right = NULL; / free(q); /有錯誤 else /左右子樹都不空 q = p; s = p->left; while(s->right) q = s; s = s-&

23、gt;right; /轉(zhuǎn)右然后向右走到盡頭找到被刪點的“前驅(qū)” p->data = s->data; /s指向被刪結(jié)點的“前驅(qū)” s->data = NULL; if(q != p) q->right = s->left; /重接*q的右子樹 else q->left = s->left; /重接*q的左子樹/ free(s); 有錯誤 return TRUE; Status DeleteBiTree(BiTree &T, Elem key) /若二叉排序樹T中存在關(guān)鍵字等于key的數(shù)據(jù)元素時 /則刪除該數(shù)據(jù)元素結(jié)點并返回TRUE否則返回FAL

24、SE if(!T) return FALSE; /不存在關(guān)鍵字等于key的數(shù)據(jù)元素 else if(key = T->data) return Delete(T); /找到關(guān)鍵字等于key的數(shù)據(jù)元素 else if(key <= T->data) /從左子樹繼續(xù)查找等于key的數(shù)據(jù)元素 return DeleteBiTree(T->left, key); else /從右子樹繼續(xù)查找等于key的數(shù)據(jù)元素 return DeleteBiTree(T->right,key); 圖2.4.33.4.4 插入模塊 在二叉排序樹種插入新結(jié)點要保證插入后的二叉樹仍符合二叉排序

25、樹的定義。插入過程若二叉排序樹為空則待插入結(jié)點*p作為根結(jié)點插入到空樹中當非空時將待插結(jié)點關(guān)鍵字p->item和樹根關(guān)鍵字t->item進行比較若p->item=t->item則無須插入若p->item<t->item則插入到根的左子樹中若p->item>t->item則插入到根的右子樹中。而子樹種的插入過程和在樹中的插入過程相同如此進行下去直到把結(jié)點*p作為一個新的樹葉插入到二叉排序樹中或者直到發(fā)現(xiàn)數(shù)已有相同關(guān)鍵字的結(jié)點為止。其代碼如下 Status InsertBiTree(BiTree &T, Elem key) /當二

26、叉排序樹T中不存在關(guān)鍵字等于key的數(shù)據(jù)元素時插入key并返回TRUE /否則返回FALSE BiTree s = NULL; BiTree p = NULL; if(!SearchBiTree(T, key, NULL, p) s = (BiTree)malloc(sizeof(BiTree); if(!s) /內(nèi)存分配失敗時給出提示然后退出操作 printf("內(nèi)存空間分配失敗n"); exit(OVERFLOW); s->data = key; s->left = s->right = NULL; if(!p) T = s; else if(key

27、< p->data) p->left = s; else p->right = s; return TRUE; else return FALSE; 圖2.4.4 3.4.5 中序輸出模塊 遍歷Traversal是指沿著某條搜索路線依次對樹中每個結(jié)點均做一次且僅做一次訪問。訪問結(jié)點所做的操作依賴于具體的應用問題。二叉樹共有三個部分組成即根結(jié)點根結(jié)點的左子樹根結(jié)點的右子樹。限定以從左至右方式共有三種遍歷方式即前序遍歷中序遍歷后序遍歷。中序遍歷的原則若被遍歷的二叉樹為非空則依次執(zhí)行如下操作 A以中序遍歷方式遍歷左子樹 B訪問根結(jié)點 C以中序遍歷方式遍歷右子樹。其代碼如下 Status InsertBiTree(BiTree &T, Elem key) /當二叉排序樹T中不存在關(guān)鍵字等于key的數(shù)據(jù)元素時插入key并返回TRUE /否則返回FALSE BiTree s = NULL;