利用二叉排序樹對(duì)順序表進(jìn)行排序

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

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

3、段（1）提交可正常執(zhí)行的系統(tǒng)（2）提交系統(tǒng)需求說明書、設(shè)計(jì)說明書、程序代碼（3）撰寫課程設(shè)計(jì)報(bào)告書（4）要求規(guī)范地書寫文檔設(shè)計(jì)工作量：（1）軟件設(shè)計(jì)：完成問題陳述中所提到的所有需求功能（2）論文：要求撰寫不少于3000字的文檔，詳細(xì)說明各階段具體要求工作計(jì)劃:數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)總學(xué)時(shí)數(shù)為 2周，其進(jìn)度及時(shí)間大致分配如下序號(hào)1天數(shù)1設(shè)計(jì)內(nèi)容分析問題，給出數(shù)學(xué)模型，選擇數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)算法，給出算法描述給出源程序清單編輯、編譯、調(diào)試源程序 編寫課程設(shè)計(jì)報(bào)告10注意事項(xiàng)提交文檔?長(zhǎng)沙學(xué)院課程設(shè)計(jì)任務(wù)書（每學(xué)生份）? 長(zhǎng)沙學(xué)院課程設(shè)計(jì)鑒定表（每學(xué)生份）? 長(zhǎng)沙學(xué)院課程設(shè)計(jì)說明書（每學(xué)生份）指導(dǎo)教師簽名日期：

4、教研室主任簽名：日期：系主任簽名：日期：長(zhǎng)沙學(xué)院課程設(shè)計(jì)鑒定表姓名學(xué)號(hào)專業(yè)班級(jí)設(shè)計(jì)題目利用叉排序樹對(duì)順序表進(jìn)行排序指導(dǎo)教師指導(dǎo)教師意見：評(píng)定等級(jí)：教師簽名：日期：答辯小組意見：評(píng)定等級(jí)：答辯小組長(zhǎng)簽名：日期：教研室意見：教研室主任簽名：日期：系（部）意見：系主任簽名：日期：說明課程設(shè)計(jì)成績(jī)分 優(yōu)秀”、“好”、及格”、不及格”四類；摘要數(shù)據(jù)結(jié)構(gòu)是研究與數(shù)據(jù)之間的關(guān)系，我們稱這一關(guān)系為數(shù)據(jù)的邏輯結(jié)構(gòu)，簡(jiǎn)稱數(shù)據(jù) 結(jié)構(gòu)。當(dāng)數(shù)據(jù)的邏輯結(jié)構(gòu)確定以后，數(shù)據(jù)在物理空間中的存儲(chǔ)方式，稱為數(shù)據(jù)的存儲(chǔ)結(jié) 構(gòu)。相同的邏輯結(jié)構(gòu)可以具有不同的存儲(chǔ)結(jié)構(gòu)，因而有不同的算法。本次課程設(shè)計(jì)，是 基于鏈?zhǔn)巾樞虮斫⒍媾判驑?。主?/p>

5、功能有建立、重建、插入、刪除以及遍歷。關(guān)鍵詞：二叉排序樹、中序遍歷、插入結(jié)點(diǎn)、刪除結(jié)點(diǎn)目錄10第1章設(shè)計(jì)內(nèi)容與要求1.Q1.1課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)1.2設(shè)計(jì)要求:1Q.12.需求分析2.1設(shè)計(jì)目的122.2設(shè)計(jì)環(huán)境12第三章概要設(shè)計(jì)133.1功能結(jié)構(gòu).13.3.2函數(shù)的結(jié)構(gòu)體143.3系統(tǒng)主要的函數(shù)1.6第四章詳細(xì)設(shè)計(jì)184.1插入模塊的設(shè)計(jì)184.2刪除模塊的設(shè)計(jì)2Q4.3遍歷模塊設(shè)計(jì)224.4樹型打印模塊的設(shè)計(jì)234.5重建二叉樹模塊的設(shè)計(jì)24第五章模塊測(cè)試265.1插入模塊測(cè)試265.2刪除插入模塊測(cè)試2.7.5.3遍歷模塊測(cè)試285.4樹型打印模塊測(cè)試295.5二叉排序樹重

6、建模塊測(cè)試30第六章總結(jié)32第七章附錄源代碼34第1章設(shè)計(jì)內(nèi)容與要求1.1課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)設(shè)計(jì)題目：利用二叉排序樹對(duì)順序表進(jìn)行排序問題描述:利用二叉排序樹對(duì)順序表進(jìn)行排序。1.2設(shè)計(jì)要求:(1) 生成一個(gè)順序表L;(2) 對(duì)所生成的順序表L構(gòu)造二叉排序樹；(3) 利用棧結(jié)構(gòu)實(shí)現(xiàn)中序遍歷二叉排序樹；(4) 中序遍歷所構(gòu)造的二叉排序樹將記錄由小到大輸出 測(cè)試數(shù)據(jù)：用偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生，表長(zhǎng)不小于20。 選作內(nèi)容：用實(shí)現(xiàn)二叉排序樹的插入和刪除操作。第2章 需求分析2.1設(shè)計(jì)目的，二叉樹的中本次構(gòu)造的是一個(gè)二叉排序樹，主要的功能有二叉排序樹的建立、節(jié)點(diǎn)的插入與刪除序遍歷、樹型打印、以

7、及重建一個(gè)新的二叉排序樹。圖2.1系統(tǒng)功能模塊圖2.2設(shè)計(jì)環(huán)境Windows 10 系統(tǒng)、visual studio2015 下編譯運(yùn)行第三章概要設(shè)計(jì)3.1功能結(jié)構(gòu)，菜單界面的功本程序主要實(shí)現(xiàn)的有七個(gè)功能，首先創(chuàng)建二叉排序樹，完成后出現(xiàn)菜單界面能有：二叉排序樹的插入、刪除、中序遍歷、樹形輸出、二叉排序樹的重建、退出。圖3.1主要功能結(jié)構(gòu)流程圖3.2函數(shù)的結(jié)構(gòu)體typedef int keytype;typedef int valuetype;typedef int listtype;/struct lin klist struct lin klist *n ext;int eleme nt;

8、/參數(shù)的數(shù)值；順序表結(jié)點(diǎn)的結(jié)構(gòu)體struct in t_li nklist struct lin klist *head; /順序表的頭結(jié)點(diǎn)的定義int cou nts; /對(duì)順序表的元素的多少進(jìn)行統(tǒng)計(jì);/typedef struct BSTNode keytype data; / 存放關(guān)鍵字的datastruct BSTNode *lchild, *rchild; /定義二叉排序樹的指針BTNode, *Btree;/typedef Btree Selem;typedef struct snode Selem data; /定義棧的存儲(chǔ)的數(shù)據(jù)struct sn ode *n ext; /棧的

9、指針sno de, *li nkst;typedef struct li nkstack lin kst top; /定義棧的棧頂指針int count; II統(tǒng)計(jì)棧里面的元素li nkstack;3.3系統(tǒng)主要的函數(shù)struct i nt_li nklist*i nit();II初始化鏈?zhǔn)巾樞虮韛oid add(struct in t_li nklist*, in t);II鏈?zhǔn)巾樞虮碓黾咏Y(jié)點(diǎn)void prin tf_list(struct in t_li nklist *);II輸出已經(jīng)創(chuàng)建好的順序表IIIIIIIIIIIIIIIIIIIIIvoid emptyMessage(char *

10、);II輸出錯(cuò)誤的提示void in itstack(li nkstack *);II初始化鏈?zhǔn)綏oid push_stacks(l in kstack *, Selem );II進(jìn)棧函數(shù)void pop_stacks(l in kstack *,Sele m&);II出棧函數(shù)bool empty_stack(l in kstack *);/判斷棧是否為空的函數(shù)/BTNode *in it_BSTree(Btree);/初始化二叉排序樹Btree BSTree_fu nd();/建立一個(gè)二叉排序樹的函數(shù)bool Search_BSTree(Btree, keytype, BTNode

11、&, BTNode&);/判斷該值是否在二叉樹存在bool in sert_BSTree(Btree&, valuetype);/插入一個(gè)數(shù)值，返回0或1，判斷是否插入成功bool Delete_BSTree(Btree&, keytype);，返回0或1判斷刪除是否/刪除函數(shù)，找到要?jiǎng)h除的數(shù)值，調(diào)用delete_value(Btree &tree)成功void delete_value(Btree &tree);/刪除這個(gè)結(jié)點(diǎn)void ino der_rec(Btree);/中序非遞歸遍歷二叉排序樹void Prin tTree(Btree,

12、in t);/按樹狀圖就行輸出/void menu (Btree);II函數(shù)的菜單界面第四章詳細(xì)設(shè)計(jì)4.1插入模塊的設(shè)計(jì)bool Search_BSTree(Btree tree, keytype value, Btree &pare nts, Btree &child) II尋找函數(shù)，判斷二叉排序樹中是否有該值，有返回1，無返回0child = tree;/子節(jié)點(diǎn)等于根節(jié)點(diǎn)while (child) II如果子節(jié)點(diǎn)child不為空，則執(zhí)行下面代碼if (value = child->data) II如果值等于 child->data ，則表示找到，返回 1retu

13、rn 1;else if (value < child->data) II 如果該值小于child->data ，則向左子樹進(jìn)行查找 parents = child; IIparents紀(jì)錄child 結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn) ，相當(dāng)于記錄父節(jié)點(diǎn)child = child->lchild;else pare nts = child; child = child->rchild;return 0; /如果不執(zhí)行上面一段代碼，或者沒有找到，返回0/ bool in sert_BSTree(Btree &tree, keytype value) Btree pare n

14、ts, child; /定義指針if (!Search_BSTree(tree, value, parents, child) /如果二叉排序樹找不到該值，則插入Btree S = (BTNode*)malloc(sizeof(BTNode); /申請(qǐng)一個(gè)結(jié)構(gòu)體空間S->data = value; / 賦值S->lchild = NULL;S->rchild = NULL;if (!tree) tree = S; / 如果tree為空，則tree為s，設(shè)置根結(jié)點(diǎn)else if (value < parents->data) /女口果 value < pare

15、nts->data， 就插入至U左子樹pare nts->lchild = S;else parents->rchild = S; / 反之，插入到右子樹return 1;/ return tree;4.2刪除模塊的設(shè)計(jì)bool Delete_BSTree(Btree &tree, keytype value) / 刪除函數(shù)if (!tree)return 0; /tree 為空，則表示刪除功能不能執(zhí)行else if (value = tree->data) /如果找到與value值相同的指針，調(diào)用delete_value函數(shù)進(jìn)行刪除delete_value(t

16、ree);return 1;else if (value < tree->data) /value小于結(jié)點(diǎn)的值，往左子樹進(jìn)行尋找retur n Delete_BSTree(tree->lchild, value);else return Delete_BSTree(tree->rchild, value);/printf("%dn", tree->data);.學(xué)習(xí)幫手.void delete_value(Btree &p) Btree q = NULL, s = NULL;if (p->lchild && p-&

17、gt;rchild) / 刪除的結(jié)點(diǎn)，左右子樹都不為空的情況q = p; s = p->lchild; /q 記錄目設(shè)為刪除結(jié)點(diǎn)的左結(jié)點(diǎn)while (s->rchild) q = s; s = s->rchild;/進(jìn)行循環(huán)，找到最右邊的那個(gè)結(jié)點(diǎn)p->data = s->data; /把找到的最右邊結(jié)點(diǎn)的關(guān)鍵字賦值給p的關(guān)鍵字if (q != p) q->rchild = s->lchild; /掛接左右子樹else q->lchild = s->lchild;/prin tf("%dt%dt%dt%dn", q->

18、;data, q->data, s->data, tree->data);free(s); /刪除s這個(gè)結(jié)點(diǎn)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->data);4.3遍歷模塊設(shè)計(jì)void ino der_rec(Btree T) l

19、in kstack S ;in itstack( & S);/ 初始化一個(gè)棧Selem e;Btree p = T;while (p | !(S.count = 0) /當(dāng)棧不為空或者p不為空時(shí)執(zhí)行while(p) push_stacks(&S, p); /p 不為空，則進(jìn)棧p = p->lchild; /對(duì)左子樹進(jìn)行遍歷if(!empty_stack(&S) data 值e = Get_top(S, e); /當(dāng)棧不為空時(shí)，取棧頂，輸出棧頂指針?biāo)赶虻?prin tf("%dn",e -> data);pop_stacks(&S

20、, p); /出棧，對(duì)右子樹進(jìn)行遍歷p = p_>rchild;/*if (T) ino der_rec(T->lchild);printf("%dn", T->data);ino der_rec(T->rchild);*/men u(tree);4.4樹型打印模塊的設(shè)計(jì)void PrintTree(Btree bt, int nlayer) /.學(xué)習(xí)幫手./采用先序遍歷的方法，進(jìn)行樹型打印if(bt)PrintTree(bt->rchild, nlayer + 10);for (int i = 0; i<nl ayer; i+)prin

21、tf(” ");printf("%d n", bt->data);Prin tTree(bt->lchild, n layer + 10);4.5重建二叉樹模塊的設(shè)計(jì)Btree BSTree_fu nd() struct in t_li nklist *lists = NULL;Btree tree = NULL;int n;lists = in it();/ 初始化順序表sran d(u nsig ned)time(NULL); /偽隨機(jī)函數(shù)的初始化prin tf("please in put how many nu mbers:n&quo

22、t;);scan f_s("%d", &n); /輸入要插入多少的數(shù)for (int i = 0; i < n; i+) .學(xué)習(xí)幫手.add(lists, ran d(); 構(gòu)造順序表struct lin klist *p;/ Btree tree = NULL;tree = in it_BSTree(tree); /初始化二叉樹p = lists->head->n ext;while (p != NULL) in sert_BSTree(tree, p->eleme nt);p = p_>n ext;/調(diào)用insert_BSTree函

23、數(shù)構(gòu)造二叉樹 return tree;第五章模塊測(cè)試5.1插入模塊測(cè)試5.2刪除插入模塊測(cè)試5.3遍歷模塊測(cè)試5.4樹型打印模塊測(cè)試5.5二叉排序樹重建模塊測(cè)試第六章總結(jié)通過這次課程設(shè)計(jì)，我對(duì)二叉排序樹的整個(gè)構(gòu)造流程更加了解了，同時(shí)也對(duì)順序表和棧這兩種數(shù)據(jù)結(jié)構(gòu)做了一次復(fù)習(xí)，但同時(shí)也存在了很多問題 。我在刪除函數(shù)中因?yàn)橛行┲羔槢]有用好，所以最開始只是跟我報(bào)錯(cuò)說是 read()出錯(cuò)，我反復(fù)的檢查許久一直找不到出錯(cuò)的地方在哪，不得已，只能重新寫了一遍刪除函數(shù)，發(fā)現(xiàn)我分成兩個(gè)刪除函數(shù)去執(zhí)行(一個(gè)函數(shù)去找那個(gè)需要?jiǎng)h除的結(jié)點(diǎn)，另一個(gè)函數(shù)則是對(duì)這已經(jīng)找到的結(jié)點(diǎn)進(jìn)行刪除)，沒有問題。而對(duì)于中序遍歷函數(shù)，我先用

24、遞歸做測(cè)試，先把其他功能做完善以后，再用棧來實(shí)現(xiàn)中序非遞歸遍歷 。第七章附錄源代碼#in clude<iostream>#in clude<malloc.h>#in clude<cstdio>#in clude<stdlib.h>#in clude<time.h>#in clude<graphics.h>/us ing n amespace std;/un sig ned int n = 30;/typedef int keytype;typedef int valuetype;typedef int listtype;/

25、struct li nklist struct lin klist *n ext; int eleme nt;；struct i nt_li nklist struct lin klist *head;int coun ts;/typedef struct BSTNode keytype data;struct BSTNode *lchild, *rchild;BTNode, *Btree;/typedef Btree Selem;typedef struct snode Selem data;struct snode *n ext;sno de, *li nkst;typedef struc

26、t lin kstack lin kst top;int count;li nkstack;/struct i nt_li nklist*i nit();void add(struct in t_li nklist*, in t);void prin tf_list(struct in t_li nklist *);/void emptyMessage(char *);void in itstack(li nkstack *);void push_stacks(l in kstack *, Selem );void pop_stacks(l in kstack *,Sele m&);b

27、ool empty_stack(l in kstack *);/BTNode *in it_BSTree(Btree);Btree BSTree_fu nd();bool Search_BSTree(Btree, keytype, BTNode&, BTNode&);bool in sert_BSTree(Btree&, valuetype);bool Delete_BSTree(Btree&, keytype);void delete_value(Btree &tree);void ino der_rec(Btree);void Prin tTree(

28、Btree, in t);/void menu (Btree);/ 、int mai n() Btree tree = NULL;/prin tf_list(lists);tree = BSTree_fu nd();/prin tf("n ”);/printf("%dn", tree->data);/prin tf("n ”);ino der_rec(tree);men u(tree);return 0;/struct int_linklist* init() struct in t_li nklist*lists;lists = (struct

29、in t_li nklist*)malloc(sizeof(struct in t_li nklist*);lists->head = (struct lin klist*)malloc(sizeof(struct lin klist);lists->head->eleme nt = -1;lists->co unts = 0;lists->head-> next = NULL;return lists;void add(struct in t_li nklist *lists, int value) struct lin klist *p;p = (str

30、uct linklist *)malloc(sizeof(struct linklist);p->next = NULL;p->eleme nt = value;p->next = lists->head->n ext;lists->head->n ext = p;lists->co un ts+;/return lists;void prin tf_list(struct in t_li nklist *lists) struct lin klist *p;p = lists->head->n ext;while (p != NUL

31、L) printf("%dn", p->element);p = p_>n ext;/void emptyMessage(char *s) prin tf("%sn", s);exit(1);void in itstack(li nkstack *stacks) /li nkst *p;stacks->top = (li nkst)malloc(sizeof(s no de);if (stacks->top = NULL)emptyMessage("it is false");stacks->top =

32、NULL;stacks->co unt = 0;/stacks.top -> next = NULL;Selem Get_top(l in kstack stacks, Selem &e) if (stacks.top = NULL)emptyMessage("it is empty");e = stacks.top->data;return e;void push_stacks(l in kstack *stacks, Selem e) lin kst p = (li nkst)malloc(sizeof(s no de);if (p = NUL

33、L)emptyMessage("False");p->data = e;p->next = stacks->top; stacks->top = p; stacks->co un t+;void pop_stacks(l in kstack *stacks,Selem &e) lin kst p;if (stacks->co unt = O)emptyMessage("it is empty");e = stacks->top->data;p = stacks->top;/printf(&qu

34、ot;%dn", p->data); stacks->top = stacks->top->n ext; free(p);stacks->co un t-;bool empty_stack(l in kstack *stacks) if (stacks->co unt = 0)retur n 1; else return 0;/BTNode *i ni t_BSTree(Btree tree) Btree root = tree;return root;bool Search_BSTree(Btree tree, keytype value, Bt

35、ree &pare nts, Btree &child) /if(tree != NULL)child = tree;while (child) if (value = child->data) return 1;else if (value < child->data) pare nts = child;child = child->lchild;else pare nts = child;child = child->rchild;return 0;/ bool in sert_BSTree(Btree &tree, keytype v

36、alue) Btree pare nts, child;if (!Search_BSTree(tree, value, parents, child) Btree S = (BTNode*)malloc(sizeof(BTNode);S->data = value;S->lchild = NULL;S->rchild = NULL;if (!tree) tree = S;else if (value < pare nts->data) pare nts->lchild = S;else pare nts->rchild = S;return 1;/ r

37、eturn tree;/ men u(tree);Btree BSTree_fu nd() struct in t_li nklist *lists = NULL;Btree tree = NULL;int n;lists = in it();sran d( un sig ned)time(NULL);prin tf("please in put how many nu mbers:n");scan f_s("%d", &n);for (int i = 0; i < n; i+) add(lists, ran d();struct lin

38、klist *p;/ Btree tree = NULL;tree = ini t_BSTree(tree);p = lists->head->n ext;while (p != NULL) in sert_BSTree(tree, p->eleme nt);p = p_>n ext;return tree;boolDelete_BSTree(Btree & tree, keytype value) if (!tree)return 0;else if (value = tree->data) delete_value(tree);return 1;els

39、e if (value < tree->data) retur n Delete_BSTree(tree->lchild, value);else retur n 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-

40、>rchild) q = s; s = s->rchild;p->data = s->data;if (q != p) q->rchild = s->lchild;else q->lchild = s->lchild;/prin tf("%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 =

41、 p->rchild; free(q);/prin tf("%dt%dt%dn",q -> data,q -> data,tree->data);void ino der_rec(Btree T) lin kstack S ;ini tstack( & S);Selem e;Btree p = T;while (p | !(S.cou nt = 0) while(p) push_stacks(&S, p); p = p->lchild;if(!empty_stack(&S) e = Get_top(S, e);prin tf("%dn",e -> data);pop_stacks(&S, p);p = p->rchild;/*if (T) ino der_rec(T->lchild);printf("%dn", T->data);ino der_rec(T->rchild);*/men u(tree);void Prin tTree(Btree bt, i nt nl ayer) /*if(bt=NULL)e