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

1、長(zhǎng) 沙 學(xué) 院課程設(shè)計(jì)說(shuō)明書(shū)題目 利用二叉排序樹(shù)對(duì)順序表進(jìn)行排序系(部)專(zhuān)業(yè)(班級(jí))姓名學(xué)號(hào)指導(dǎo)教師起止日期2015.12.82015.12.15課程設(shè)計(jì)任務(wù)書(shū)課程名稱(chēng)：數(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ì)算問(wèn)題2、迷宮問(wèn)題3、利用二叉排序樹(shù)對(duì)順序表進(jìn)行排序4、交通咨詢系統(tǒng)5、內(nèi)部排序算法的比較已知技術(shù)參數(shù)和設(shè)計(jì)要求：需求說(shuō)明及要求題目三：利用二叉排序樹(shù)對(duì)順序表進(jìn)行排序問(wèn)題描述：利用二叉排序樹(shù)對(duì)順序表

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

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

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

5、方式，稱(chēng)為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。相同的邏輯結(jié)構(gòu)可以具有不同的存儲(chǔ)結(jié)構(gòu)，因而有不同的算法。本次課程設(shè)計(jì)，是基于鏈?zhǔn)巾樞虮斫⒍媾判驑?shù)。主要功能有建立、重建、插入、刪除以及遍歷。關(guān)鍵詞：二叉排序樹(shù)、中序遍歷、插入結(jié)點(diǎn)、刪除結(jié)點(diǎn)目錄第1章設(shè)計(jì)內(nèi)容與要求71.1課程名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)71.2 設(shè)計(jì)要求：7第2章需求分析82.1設(shè)計(jì)目的82.2 設(shè)計(jì)環(huán)境8第三章 概要設(shè)計(jì)93.1 功能結(jié)構(gòu)93.2函數(shù)的結(jié)構(gòu)體103.3系統(tǒng)主要的函數(shù)10第四章 詳細(xì)設(shè)計(jì)124.1插入模塊的設(shè)計(jì)124.2刪除模塊的設(shè)計(jì)134.3遍歷模塊設(shè)計(jì)144.4樹(shù)型打印模塊的設(shè)計(jì)154.5重建二叉樹(shù)模塊的設(shè)計(jì)15第五章 模塊測(cè)試

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

7、2章 需求分析2.1設(shè)計(jì)目的 本次構(gòu)造的是一個(gè)二叉排序樹(shù)，主要的功能有二叉排序樹(shù)的建立、節(jié)點(diǎn)的插入與刪除，二叉樹(shù)的中序遍歷、樹(shù)型打印、以及重建一個(gè)新的二叉排序樹(shù)。 二叉排序樹(shù)系統(tǒng)主菜單建立退出中序遍歷樹(shù)型打印刪除插入 圖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)建二叉排序樹(shù)，完成后出現(xiàn)菜單界面，菜單界面的功能有：二叉排序樹(shù)的插入、刪除、中序遍歷、樹(shù)形輸出、二叉排序樹(shù)的重建、退出。 創(chuàng)建二叉樹(shù)Switch(1)插入結(jié)點(diǎn)刪除結(jié)點(diǎn)重建二叉樹(shù)樹(shù)型打印Exit(0)退出

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

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

10、inklist*init();/ 初始化鏈?zhǔn)巾樞虮韛oid add(struct int_linklist*, int);/鏈?zhǔn)巾樞虮碓黾咏Y(jié)點(diǎn)void printf_list(struct int_linklist *);/輸出已經(jīng)創(chuàng)建好的順序表/void emptyMessage(char *);/輸出錯(cuò)誤的提示void initstack(linkstack *);/初始化鏈?zhǔn)綏oid push_stacks(linkstack *, Selem );/進(jìn)棧函數(shù)void pop_stacks(linkstack *,Selem&);/出棧函數(shù)bool empty_stack(li

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

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

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

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

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

16、/tree為空，則表示刪除功能不能執(zhí)行else if (value = tree->data) /如果找到與value值相同的指針，調(diào)用delete_value函數(shù)進(jìn)行刪除delete_value(tree);return 1;else if (value < tree->data) /value小于結(jié)點(diǎn)的值，往左子樹(shù)進(jìn)行尋找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) /刪除的結(jié)點(diǎn)，左右子樹(shù)都不為空的情況q = p; s = p->lchild; /q記錄,s設(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 =

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

19、dt%dt%dn",q -> data,q -> data,tree->data);4.3遍歷模塊設(shè)計(jì) void inoder_rec(Btree T) linkstack S ;initstack( &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ì)左子樹(shù)進(jìn)行遍歷if(!empty_stack(&S) e = Get_top(S, e

20、); /當(dāng)棧不為空時(shí)，取棧頂，輸出棧頂指針?biāo)赶虻膁ata值printf("%dn",e -> data);pop_stacks(&S, p); /出棧，對(duì)右子樹(shù)進(jìn)行遍歷p = p->rchild;/*if (T) inoder_rec(T->lchild);printf("%dn", T->data);inoder_rec(T->rchild);*/menu(tree);4.4樹(shù)型打印模塊的設(shè)計(jì) void PrintTree(Btree bt, int nlayer) /采用先序遍歷的方法，進(jìn)行樹(shù)型打印 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重建二叉樹(shù)模塊的設(shè)計(jì) Btree BSTree_fund() struct int_linklist *lists = NULL;Btree tree = NULL;int n;lists = init();/初始化順序表srand(unsigned)ti

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

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

24、數(shù)去找那個(gè)需要?jiǎng)h除的結(jié)點(diǎn)，另一個(gè)函數(shù)則是對(duì)這已經(jīng)找到的結(jié)點(diǎn)進(jìn)行刪除），沒(méi)有問(wèn)題。而對(duì)于中序遍歷函數(shù)，我先用遞歸做測(cè)試，先把其他功能做完善以后，再用棧來(lái)實(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