利用二叉排序樹對順序表進行排序

1、長 沙 學 院課程設計說明書題目 利用二叉排序樹對順序表進行排序系(部)專業(yè)(班級)姓名學號指導教師起止日期2015.12.82015.12.15課程設計任務書課程名稱：數(shù)據(jù)結構與算法課程設計設計題目：為了充分調動學生的學習積極性與主動性，適應不同興趣、不同程度的學生對課程設計的要求，本課程設計提供四個任選題。每個學生可以根據(jù)本人的興趣及能力選擇教師指定的選題，也可以自定其他的選題。1、一元多項式計算問題2、迷宮問題3、利用二叉排序樹對順序表進行排序4、交通咨詢系統(tǒng)5、內部排序算法的比較已知技術參數(shù)和設計要求：需求說明及要求題目三：利用二叉排序樹對順序表進行排序問題描述：利用二叉排序樹對順序表

2、進行排序?；疽螅?1) 生成一個順序表L;(2) 對所生成的順序表L構造二叉排序樹;(3) 利用棧結構實現(xiàn)中序遍歷二叉排序樹;(4) 中序遍歷所構造的二叉排序樹將記錄由小到大輸出。測試數(shù)據(jù)：用偽隨機數(shù)產生程序產生，表長不小于20。選作內容：用實現(xiàn)二叉排序樹的插入和刪除操作。各階段具體要求：1、需求分析階段熟悉系統(tǒng)業(yè)務，從業(yè)務中抽取出系統(tǒng)的需求，形成完善的需求說明書。2、系統(tǒng)設計階段根據(jù)需求，進行程序設計，包括定義系統(tǒng)的界面、定義系統(tǒng)數(shù)據(jù)的存儲方式等，形成完善的設計說明書。3、編碼實現(xiàn)階段（1）完成代碼編寫 （2）要求代碼編寫規(guī)范4、系統(tǒng)測試階段（1）完成功能調試（2）要求完成必要的測試工作

3、5、交付實施階段（1）提交可正常執(zhí)行的系統(tǒng)（2）提交系統(tǒng)需求說明書、設計說明書、程序代碼（3）撰寫課程設計報告書（4）要求規(guī)范地書寫文檔設計工作量：（1）軟件設計：完成問題陳述中所提到的所有需求功能。（2）論文：要求撰寫不少于3000字的文檔，詳細說明各階段具體要求。工作計劃：數(shù)據(jù)結構課程設計總學時數(shù)為2 周，其進度及時間大致分配如下：序號 設計內容 天數(shù)1 分析問題，給出數(shù)學模型，選擇數(shù)據(jù)結構 12 設計算法，給出算法描述 23 給出源程序清單 14 編輯、編譯、調試源程序 55 編寫課程設計報告 1總 計 10注意事項n 提交文檔Ø 長沙學院課程設計任務書（每學生1份）Ø

4、; 長沙學院課程設計鑒定表（每學生1份）Ø 長沙學院課程設計說明書（每學生1份）指導教師簽名： 日期： 教研室主任簽名： 日期：系主任簽名： 日期：長沙學院課程設計鑒定表姓名學號 專業(yè)班級設計題目利用二叉排序樹對順序表進行排序指導教師指導教師意見：評定等級： 教師簽名： 日期： 答辯小組意見：評定等級：答辯小組長簽名：日期：教研室意見：教研室主任簽名： 日期： 系（部）意見：系主任簽名：日期：說明課程設計成績分“優(yōu)秀”、“良好”、“及格”、“不及格”四類；摘要數(shù)據(jù)結構是研究與數(shù)據(jù)之間的關系，我們稱這一關系為數(shù)據(jù)的邏輯結構，簡稱數(shù)據(jù)結構。當數(shù)據(jù)的邏輯結構確定以后，數(shù)據(jù)在物理空間中的存儲

5、方式，稱為數(shù)據(jù)的存儲結構。相同的邏輯結構可以具有不同的存儲結構，因而有不同的算法。本次課程設計，是基于鏈式順序表建立二叉排序樹。主要功能有建立、重建、插入、刪除以及遍歷。關鍵詞：二叉排序樹、中序遍歷、插入結點、刪除結點目錄第1章設計內容與要求71.1課程名稱：數(shù)據(jù)結構與算法課程設計71.2 設計要求：7第2章需求分析82.1設計目的82.2 設計環(huán)境8第三章 概要設計93.1 功能結構93.2函數(shù)的結構體103.3系統(tǒng)主要的函數(shù)10第四章 詳細設計124.1插入模塊的設計124.2刪除模塊的設計134.3遍歷模塊設計144.4樹型打印模塊的設計154.5重建二叉樹模塊的設計15第五章 模塊測試

6、165.1插入模塊測試165.2刪除插入模塊測試175.3遍歷模塊測試185.4樹型打印模塊測試195.5二叉排序樹重建模塊測試20第六章 總結22第七章 附錄源代碼23第1章 設計內容與要求 1.1課程名稱：數(shù)據(jù)結構與算法課程設計 設計題目： 利用二叉排序樹對順序表進行排序 問題描述：利用二叉排序樹對順序表進行排序。1.2 設計要求： (1) 生成一個順序表L;(2) 對所生成的順序表L構造二叉排序樹;(3) 利用棧結構實現(xiàn)中序遍歷二叉排序樹;(4) 中序遍歷所構造的二叉排序樹將記錄由小到大輸出。測試數(shù)據(jù)：用偽隨機數(shù)產生程序產生，表長不小于20。選作內容：用實現(xiàn)二叉排序樹的插入和刪除操作。第

7、2章 需求分析2.1設計目的 本次構造的是一個二叉排序樹，主要的功能有二叉排序樹的建立、節(jié)點的插入與刪除，二叉樹的中序遍歷、樹型打印、以及重建一個新的二叉排序樹。 二叉排序樹系統(tǒng)主菜單建立退出中序遍歷樹型打印刪除插入 圖2.1 系統(tǒng)功能模塊圖2.2 設計環(huán)境Windows 10系統(tǒng)、visual studio2015下編譯運行第三章 概要設計 3.1 功能結構 本程序主要實現(xiàn)的有七個功能，首先創(chuàng)建二叉排序樹，完成后出現(xiàn)菜單界面，菜單界面的功能有：二叉排序樹的插入、刪除、中序遍歷、樹形輸出、二叉排序樹的重建、退出。 創(chuàng)建二叉樹Switch(1)插入結點刪除結點重建二叉樹樹型打印Exit(0)退出

8、中序遍歷Switch(2)Switch(3)Switch(4)Switch(5)Switch(6) 圖3.1 主要功能結構流程圖 3.2函數(shù)的結構體typedef int keytype;typedef int valuetype;typedef int listtype;/struct linklist struct linklist *next;int element; /參數(shù)的數(shù)值; /順序表結點的結構體struct int_linklist struct linklist *head; /順序表的頭結點的定義int counts; /對順序表的元素的多少進行統(tǒng)計;/typedef st

9、ruct BSTNode keytype data; /存放關鍵字的datastruct BSTNode *lchild, *rchild; /定義二叉排序樹的指針BTNode, *Btree;/typedef Btree Selem;typedef struct snode Selem data; /定義棧的存儲的數(shù)據(jù)struct snode *next; /棧的指針snode, *linkst;typedef struct linkstack linkst top; /定義棧的棧頂指針int count; /統(tǒng)計棧里面的元素linkstack; 3.3系統(tǒng)主要的函數(shù)struct int_l

10、inklist*init();/ 初始化鏈式順序表void add(struct int_linklist*, int);/鏈式順序表增加結點void printf_list(struct int_linklist *);/輸出已經(jīng)創(chuàng)建好的順序表/void emptyMessage(char *);/輸出錯誤的提示void initstack(linkstack *);/初始化鏈式棧void push_stacks(linkstack *, Selem );/進棧函數(shù)void pop_stacks(linkstack *,Selem&);/出棧函數(shù)bool empty_stack(li

11、nkstack *);/判斷棧是否為空的函數(shù)/BTNode *init_BSTree(Btree);/初始化二叉排序樹Btree BSTree_fund();/建立一個二叉排序樹的函數(shù)bool Search_BSTree(Btree, keytype, BTNode&, BTNode&);/判斷該值是否在二叉樹存在bool insert_BSTree(Btree&, valuetype);/插入一個數(shù)值，返回0或1，判斷是否插入成功bool Delete_BSTree(Btree&, keytype);/刪除函數(shù)，找到要刪除的數(shù)值，調用delete_value(

12、Btree &tree)，返回0或1判斷刪除是否成功 void delete_value(Btree &tree);/刪除這個結點void inoder_rec(Btree);/中序非遞歸遍歷二叉排序樹void PrintTree(Btree, int);/按樹狀圖就行輸出/void menu(Btree);/函數(shù)的菜單界面第四章 詳細設計4.1插入模塊的設計 bool Search_BSTree(Btree tree, keytype value, Btree &parents, Btree &child) /尋找函數(shù)，判斷二叉排序樹中是否有該值，有返回1，無

13、返回0child = tree;/子節(jié)點等于根節(jié)點while (child) /如果子節(jié)點child不為空，則執(zhí)行下面代碼if (value = child->data) /如果值等于child->data，則表示找到，返回1return 1;else if (value < child->data) /如果該值小于child->data，則向左子樹進行查找parents = child; /parents紀錄child結點的上一個結點，相當于記錄父節(jié)點child = child->lchild;else parents = child;child = ch

14、ild->rchild;return 0; /如果不執(zhí)行上面一段代碼，或者沒有找到，返回0/ bool insert_BSTree(Btree &tree, keytype value) Btree parents, child; /定義指針if (!Search_BSTree(tree, value, parents, child) /如果二叉排序樹找不到該值，則插入Btree S = (BTNode*)malloc(sizeof(BTNode); /申請一個結構體空間S->data = value; /賦值S->lchild = NULL;S->rchild

15、 = NULL;if (!tree) tree = S; /如果tree為空，則tree為s，設置根結點else if (value < parents->data) /如果value < parents->data，就插入到左子樹parents->lchild = S;else parents->rchild = S; /反之，插入到右子樹return 1;/ return tree;4.2刪除模塊的設計 bool Delete_BSTree(Btree &tree, keytype value) /刪除函數(shù)if (!tree)return 0;

16、/tree為空，則表示刪除功能不能執(zhí)行else if (value = tree->data) /如果找到與value值相同的指針，調用delete_value函數(shù)進行刪除delete_value(tree);return 1;else if (value < tree->data) /value小于結點的值，往左子樹進行尋找return Delete_BSTree(tree->lchild, value);else return Delete_BSTree(tree->rchild, value);/printf("%dn", tree-&g

17、t;data);void delete_value(Btree &p) Btree q = NULL, s = NULL;if (p->lchild && p->rchild) /刪除的結點，左右子樹都不為空的情況q = p; s = p->lchild; /q記錄,s設為刪除結點的左結點while (s->rchild) q = s; s = s->rchild;/進行循環(huán)，找到最右邊的那個結點p->data = s->data; /把找到的最右邊結點的關鍵字賦值給p的關鍵字if (q != p) q->rchild =

18、 s->lchild; /掛接左右子樹else q->lchild = s->lchild;/printf("%dt%dt%dt%dn", q->data, q->data, s->data, tree->data);free(s); /刪除s這個結點else if (!p->rchild) /右子樹為空，所以掛接到左子樹上q = p; p = p->lchild; free(q);else q = p; p = p->rchild; free(q); /左子樹為空，所以掛接到右子樹上/printf("%

19、dt%dt%dn",q -> data,q -> data,tree->data);4.3遍歷模塊設計 void inoder_rec(Btree T) linkstack S ;initstack( &S);/初始化一個棧Selem e;Btree p = T;while (p | !(S.count = 0) /當棧不為空或者p不為空時執(zhí)行while(p) push_stacks(&S, p); /p不為空，則進棧p = p->lchild; /對左子樹進行遍歷if(!empty_stack(&S) e = Get_top(S, e

20、); /當棧不為空時，取棧頂，輸出棧頂指針所指向的data值printf("%dn",e -> data);pop_stacks(&S, p); /出棧，對右子樹進行遍歷p = p->rchild;/*if (T) inoder_rec(T->lchild);printf("%dn", T->data);inoder_rec(T->rchild);*/menu(tree);4.4樹型打印模塊的設計 void PrintTree(Btree bt, int nlayer) /采用先序遍歷的方法，進行樹型打印 if(bt

21、)PrintTree(bt->rchild, nlayer + 10);for (int i = 0; i<nlayer; i+)printf(" ");printf("%d n", bt->data);PrintTree(bt->lchild, nlayer + 10);4.5重建二叉樹模塊的設計 Btree BSTree_fund() struct int_linklist *lists = NULL;Btree tree = NULL;int n;lists = init();/初始化順序表srand(unsigned)ti

22、me(NULL); /偽隨機函數(shù)的初始化printf("please input how many numbers:n");scanf_s("%d", &n); /輸入要插入多少的數(shù)for (int i = 0; i < n; i+) add(lists, rand();/構造順序表struct linklist *p;/Btree tree = NULL;tree = init_BSTree(tree); /初始化二叉樹p = lists->head->next;while (p != NULL) insert_BSTree(

23、tree, p->element);p = p->next;/調用insert_BSTree函數(shù)構造二叉樹return tree; 第五章 模塊測試5.1插入模塊測試5.2刪除插入模塊測試5.3遍歷模塊測試5.4樹型打印模塊測試5.5二叉排序樹重建模塊測試第六章 總結通過這次課程設計，我對二叉排序樹的整個構造流程更加了解了，同時也對順序表和棧這兩種數(shù)據(jù)結構做了一次復習，但同時也存在了很多問題。我在刪除函數(shù)中因為有些指針沒有用好，所以最開始只是跟我報錯說是read()出錯，我反復的檢查許久一直找不到出錯的地方在哪，不得已，只能重新寫了一遍刪除函數(shù)，發(fā)現(xiàn)我分成兩個刪除函數(shù)去執(zhí)行（一個函

24、數(shù)去找那個需要刪除的結點，另一個函數(shù)則是對這已經(jīng)找到的結點進行刪除），沒有問題。而對于中序遍歷函數(shù)，我先用遞歸做測試，先把其他功能做完善以后，再用棧來實現(xiàn)中序非遞歸遍歷。第七章 附錄源代碼 #include<iostream>#include<malloc.h>#include<cstdio>#include<stdlib.h>#include<time.h>/#include<graphics.h>/using namespace std;/unsigned int n = 30;/typedef int keytype

25、;typedef int valuetype;typedef int listtype;/struct linklist struct linklist *next;int element;struct int_linklist struct linklist *head;int counts;/typedef struct BSTNode keytype data;struct BSTNode *lchild, *rchild;BTNode, *Btree;/typedef Btree Selem;typedef struct snode Selem data;struct snode *n

26、ext;snode, *linkst;typedef struct linkstack linkst top;int count;linkstack;/struct int_linklist*init();void add(struct int_linklist*, int);void printf_list(struct int_linklist *);/void emptyMessage(char *);void initstack(linkstack *);void push_stacks(linkstack *, Selem );void pop_stacks(linkstack *,

27、Selem&);bool empty_stack(linkstack *);/BTNode *init_BSTree(Btree);Btree BSTree_fund();bool Search_BSTree(Btree, keytype, BTNode&, BTNode&);bool insert_BSTree(Btree&, valuetype);bool Delete_BSTree(Btree&, keytype);void delete_value(Btree &tree);void inoder_rec(Btree);void Prin

28、tTree(Btree, int);/void menu(Btree);/、int main() Btree tree = NULL;/printf_list(lists);tree = BSTree_fund();/printf("n");/printf("%dn", tree->data);/printf("n");/inoder_rec(tree);menu(tree);return 0;/struct int_linklist* init() struct int_linklist*lists;lists = (stru

29、ct int_linklist*)malloc(sizeof(struct int_linklist*);lists->head = (struct linklist*)malloc(sizeof(struct linklist);lists->head->element = -1;lists->counts = 0;lists->head->next = NULL;return lists;void add(struct int_linklist *lists, int value) struct linklist *p;p = (struct linkl

30、ist *)malloc(sizeof(struct linklist);p->next = NULL;p->element = value;p->next = lists->head->next;lists->head->next = p;lists->counts+;/return lists;void printf_list(struct int_linklist *lists) struct linklist *p;p = lists->head->next;while (p != NULL) printf("%dn

31、", p->element);p = p->next;/void emptyMessage(char *s) printf("%sn", s);exit(1);void initstack(linkstack *stacks) /linkst *p;stacks->top = (linkst)malloc(sizeof(snode);if (stacks->top = NULL)emptyMessage("it is false");stacks->top = NULL;stacks->count = 0;/

32、stacks.top -> next = NULL;Selem Get_top(linkstack stacks, Selem &e) if (stacks.top = NULL)emptyMessage("it is empty");e = stacks.top->data;return e;void push_stacks(linkstack *stacks, Selem e) linkst p = (linkst)malloc(sizeof(snode);if (p = NULL)emptyMessage("False");p-

33、>data = e;p->next = stacks->top;stacks->top = p;stacks->count+;void pop_stacks(linkstack *stacks,Selem &e) linkst p;if (stacks->count = 0)emptyMessage("it is empty");e = stacks->top->data;p = stacks->top;/printf("%dn", p->data);stacks->top = s

34、tacks->top->next;free(p);stacks->count-;bool empty_stack(linkstack *stacks) if (stacks->count = 0)return 1;else return 0;/BTNode *init_BSTree(Btree tree) Btree root = tree;return root;bool Search_BSTree(Btree tree, keytype value, Btree &parents, Btree &child) /if(tree != NULL)chi

35、ld = tree;while (child) if (value = child->data) return 1;else if (value < child->data) parents = child;child = child->lchild;else parents = child;child = child->rchild;return 0;/ bool insert_BSTree(Btree &tree, keytype value) Btree parents, child;if (!Search_BSTree(tree, value, p

36、arents, child) Btree S = (BTNode*)malloc(sizeof(BTNode);S->data = value;S->lchild = NULL;S->rchild = NULL;if (!tree) tree = S;else if (value < parents->data) parents->lchild = S;else parents->rchild = S;return 1;/ return tree;/ menu(tree);Btree BSTree_fund() struct int_linklist

37、*lists = NULL;Btree tree = NULL;int n;lists = init();srand(unsigned)time(NULL);printf("please input how many numbers:n");scanf_s("%d", &n);for (int i = 0; i < n; i+) add(lists, rand();struct linklist *p;/Btree tree = NULL;tree = init_BSTree(tree);p = lists->head->nex

38、t;while (p != NULL) insert_BSTree(tree, p->element);p = p->next;return tree;bool Delete_BSTree(Btree &tree, keytype value) if (!tree)return 0;else if (value = tree->data) delete_value(tree);return 1;else if (value < tree->data) return Delete_BSTree(tree->lchild, value);else ret

39、urn Delete_BSTree(tree->rchild, value);printf("%dn", tree->data);void delete_value(Btree &p) Btree q = NULL, s = NULL;if (p->lchild && p->rchild) q = p; s = p->lchild;while (s->rchild) q = s; s = s->rchild;p->data = s->data;if (q != p) q->rchild =

40、s->lchild;else q->lchild = s->lchild;/printf("%dt%dt%dt%dn", q->data, q->data, s->data, tree->data);free(s);else if (!p->rchild) q = p; p = p->lchild; free(q);else q = p; p = p->rchild; free(q);/printf("%dt%dt%dn",q -> data,q -> data,tree->d

41、ata);void inoder_rec(Btree T) linkstack S ;initstack( &S);Selem e;Btree p = T;while (p | !(S.count = 0) while(p) push_stacks(&S, p);p = p->lchild;if(!empty_stack(&S) e = Get_top(S, e);printf("%dn",e -> data);pop_stacks(&S, p);p = p->rchild;/*if (T) inoder_rec(T->lchild);printf("%dn", T->data);inoder_rec(T->rchild);*/menu(tree);void PrintTree(Btree bt, int nlayer) /*if(bt=NULL