第九組數據結構課程設計(二叉排序樹實現)

1、黃滾曇院“數據結構”課程設計報告系（院）： 信息工程學院 _設計題目： 二叉排序樹的實現 _專業(yè)班級： 軟件工程15級 _小組成員：唐二虎、趙夢娟、賈月 _指導教師：汪洋 _二叉排序樹的實現1.設計任務1）實現二叉排序樹，包括生成、插入，刪除；2）對二叉排序樹進行先根、中根、和后根非遞歸遍歷；3）每次對樹的修改操作和遍歷操作的顯示結果都需要在用樹的形狀表示出來。4）分別用二叉排序樹和數組去存儲一個班（50人以上）的成員信息（至少包括學號、姓名、成績3項），對比查找效率，并說明 為什么二叉排序樹效率高（或者低）。2程序設計流程圖（設計思想）詳細設計思想：建立二義排序樹釆用邊查找邊插入的方式。查找

2、函數釆用遞歸的方式進行查找。 如果查找到相等的則插入其左子樹。然后利用插入函數將該元素插入原樹。對二義樹進行中序遍歷釆用遞歸函數的方式。在根結點不為空的惜況下，先訪問 左子樹，再訪問根結點，最后訪問右子樹。刪除結點函數，采用邊查找邊刪除的方式。如果沒有查找到，進行提示；如果查 找到結點則將其左子樹最右邊的節(jié)點的數據傳給它，然后刪除其左子樹最右邊的 節(jié)點。3. 函數模塊：3.3. 1.1.主函數mainmain模塊功能1.通過bstreeCreatTree ()操作建立.義排序樹。2.在二義排序樹 t 中通過操作 bstreelnsertBST(bstreet, intkey, ndmetype

3、name, double grade)扌番入一個節(jié)點。3.從二義排序樹t中通過操作void Delete(bstree&p)刪除任意節(jié)點。4.在:叉排序樹 t 中通過操作 bstnode *SearchBST(bstreet, keytype key)查找節(jié)點。5.在二義排序樹t中通過操作p=SearchBST (t, key)查詢，并修改節(jié)點信息6.非遞歸遍歷二叉排序樹。7.定義函數void compare ()對數組和二義排序樹的查找效率進行比較比較。3.3. 2 2創(chuàng)建二叉排序樹CreatTreeCreatTree模塊從鍵盤中輸入關鍵字及記錄，并同時調用插入函數并不斷進行插入。最后, 返

4、回根節(jié)點T。3.3. 3 3刪除模塊：二義排序樹上刪除一個階段相當于刪去有序系列中的一個記錄，只要在刪 除某個節(jié)點之后依舊保持二義排序樹的性質即可。假設二叉排序樹上刪除節(jié) 點為*P (指向節(jié)點的指針為P),其雙親節(jié)點為水f (節(jié)點指針為f)。若*p節(jié)點 為葉子節(jié)點，則即左右均為空樹，由于刪去葉子節(jié)點不破壞整棵樹的結構， 則只需修改其雙親節(jié)點的指針即可；若叱節(jié)點只有左子樹或只有右子樹，此 時只要令左子樹或右子樹直接成為其雙親節(jié)點粒的左子樹即可；若和節(jié)點的 左子樹和右子樹均不為空，其一可以令切的左子樹為粒的左子樹，而叱的右 子樹為*s的右子樹，其二可以令切的直接前驅(或直接后繼)替代和，然后 再從

5、二義排序樹中刪去它的直接前驅(或直接后繼)。在二義排序樹中刪除一 個節(jié)點的算法為voidDeleteData(bstree&t, keytype key)若二義排序樹t中存在關鍵字等于key的數據元素，則刪除該數據元素節(jié)點, 并返回TRUE,否則返回FALSEo3.3.4 4插入模塊二義排序樹是一種動態(tài)樹表，其特點是樹的結構通常不是一次生成的，而 是在查找的過程中，當樹中不存在關鍵字等于給定值得節(jié)點時在進行插入。 新插入的節(jié)點一定是一個新添加的葉子節(jié)點，并且是查找不成功時查找路徑 上訪問的最后一個節(jié)點的左孩子或右孩子的節(jié)點。一個無序系列可以通過構 造一棵二義排序樹而變成一個有序系列，構造樹的過

6、程即為對無序系列進行 排序的過程，并且每次插入的節(jié)點都是二義排序樹上新的葉子節(jié)點，則在進 行插入操作時，不必移動其他節(jié)點，僅需改變某個節(jié)點的指針由空變?yōu)榉强?即可。二叉排序樹的插入算法為bstreelnsertBST(bstreet, intkey, nametypename, double grade)若二義排序樹中不存在關鍵字等于key的數據元素時，插入元素并返回TRUEo3.3. 5 5査找模塊二義排序樹乂稱二義查找樹，當二義排序樹不為空時，首先將給定的值和 根節(jié)點的關鍵字比較，若相等則查找成功，否則將依據給定的值和根節(jié)點關 鍵字之間的大小關系，分別在左子樹或右子樹上繼續(xù)進行查找。為此定

7、義一 個二叉排序樹的查找算法為bstnode *SearchBST(bstreet,keytype key)在根指針t所指向的二義排序樹中查找關鍵字等于key的數據元素，如成功, 返回指向該元素節(jié)點的指針，否則返回空指針。3.3. 6 6二叉排序樹的遍歷先序遍歷也叫做先根遍歷。首先訪問根結點然后遍歷左子樹，最后遍歷 右子樹。在遍歷左、右子樹時，仍然先訪問根結點，然后遍歷左子樹，最后 遍歷右子樹，如果二義樹為空則返回。其實過程為：先遍歷左子樹 root-left-left-left. . . -null,由于是先序遍歷，因此一遇到節(jié)點， 便需要立即訪問；山于一直走到最左邊后，需要逐步返回到父節(jié)點

8、訪問右節(jié) 點，因此必須有一個措施能夠對節(jié)點序列回溯。其一可以用棧記憶在訪問途 中將依次遇到的節(jié)點保存下來。根據棧的先進后出、后進先出的特點特點。 則可以用棧保存。每次都將遇到的節(jié)點壓入棧，當左子樹遍歷完畢后從棧中 彈出最后一個訪問的節(jié)點，然后訪問其右子樹?；舅惴ㄋ枷耄?先訪問根節(jié)點，將根節(jié)點入棧2.重復執(zhí)行兩大步驟：如果該節(jié)點左孩子存在，則訪問該左孩子節(jié)點，并將 其指針入棧。重復以上操作，直到節(jié)點的左孩子不存在。將棧頂的元素， 即其指針出棧，回到父節(jié)點，如果該指針節(jié)點的右孩子存在，則將該指針 指向的右孩子節(jié)點重復執(zhí)行以上步驟，直到棧為空為止。操作函數為 void x_print (Tree

9、T)中序遍歷：中序遍歷和先序遍歷訪問的順序不同。中序遍歷訪問順序為中 序遍歷左子數，在訪問根節(jié)點，最后中序遍歷右子樹。先序遍歷是先訪問， 再入棧；而中序遍歷則是先入棧，彈棧后再訪問。將二義樹的根節(jié)點入棧， 如果該節(jié)點有左孩子，將左孩子直接入棧，重復該操作，直到該節(jié)點無左孩 子；在將棧頂元素出棧，并訪問該節(jié)點指向的節(jié)點，如果該指針指向的右孩 子存在，則將當前指針指向右孩子節(jié)點。重復執(zhí)行步驟直到棧為空為止。 操作函數為 void z_print (Tree T )。后序遍歷：先后序遍歷左子樹，在后序遍歷右子樹，最后訪問根節(jié)點。先 將根節(jié)點入棧，如果該節(jié)點左孩子節(jié)點存在，將該節(jié)點左孩子節(jié)點入棧。重

10、復執(zhí)行此操作，直到節(jié)點左孩子節(jié)點為空。取棧頂元素，并賦值給P,如果P 的右孩子為空或P的右孩子等于q(即如果P的右孩子已訪問，則訪問根節(jié)點, 即P指向的節(jié)點，并用q來記錄剛剛訪問的節(jié)點的指針)，若P有右孩子，且 右孩子沒有別訪問過，則p=p-rchildo操作函數為 void h_print (Tree T)4. 源代碼include /* run this program using the console pauser or add your own getch, system (pause) or input loop /#include#include #include #includ

11、e include using namespace std;typedef stringnametype;typedef unsigned long keytype;typedefstruct node/結點的結構體keytype key;nametype name;int grade;struct node *lchild, *rchild;Jbstnode;typedefbstnode *bstree;/棧的總義/typedefstructbstree *base;bstree *top; intstacksize;Sqstack;intlnitStack (Sqstack&s)/sbas

12、e=(bstree*)malloc(1000 * sizeof(int);s top=s base; return 1;int Push(Sqstack&s , node *e)*s top=e;s.top=s top+1;return 1;int Pop(Sqstack&s, bstree&e)if(stop二二s.base)return 0;elses top=s top-1;e=*s top;return 1;/非遞歸歷遍并輸出結點信息/* -先序非遞 歸遍歷 -*/voidx_print(node *t)Sqstack s;InitStack(s);bstnode *p;P=t;whi

13、le(p ! (s top=s base)if (p)Push(s, p);coutp-key/x tsetw (20); coutp-name，/t/setw(20);coutp-gradelchild;elsePop(s, p); p=p-rchild;/*-中序非遞歸遍歷-*/voidz_print(node *t)Sqstack s;InitStack(s);bstnode *p;P=t;while(p !(s. top=s base)if (p)Push(s, p); p=p-lchild;elsePop(s, p)； coutp-key/x tsetw (20); coutp-na

14、me，/t/setw(20); coutp-graderchild;voidh_print(node *t)Sqstack s; InitStack(s);node *p, *q;p=t;q=NULL;while(p ! (s top=s.base) if (p) Push(s, p);p=p-lchild;非遞歸后序遍歷*/ elsep=*(s top-1);if(p-rchild=q)Pop(s, q) : p=NULL;coutq-key/zt/name/，t?/grade/，tyendl; elsep=p-rchild;q=NULL;遞歸査找二叉樹/*_歸査找，若找到就返回指向該結點的

15、指針，否則返回空一-*/bstnode *SearchBST(bstreet, keytype key) if(t=NULL key二二t-key)return t;if(keykey)returnSearchBST(t-lchild , key);elsereturnSearchBST(t-rchild , key);/ -給定學生信息插入到二叉樹中 -/bstreelnsertBST (bstreet, intkey, nametypename, double grade)bstreep, q;if(t=NULL)t=new bstnode0; t-key=key;t-name=name;

16、t-grade=grade;t-lch訂d二t-rchild二NULL;elsep=t;while (p)q 二P；if (p-keykey)p二q-lchild;else if (p-keyrchild;elsecoutendl;cout/z樹中已有該節(jié)點:/keyendl;coutendl;return t;p=new bstnode 0;p-key=key;p-name=name;p-grade=grade;p-lchild=p-rchild=NULL;if(q-keykey)q-lchild=p;elseq-rchild=p;return t;/ -二叉樹排序樹的構建 -/bstree

17、CreatTree 0bstree t=NULL;keytype key;nametype name;double grade;printf (，?n*本系統(tǒng)由二胡科技所有成員公同組建！ *nnnz/); printf (w請輸入-學號 -姓名 -成績 -(輸入0時結束)：n);cinkey;if(key=0)return t;cinname;cingrade;while(key)t=InsertBST(t, key, name, grade);printfC請輸入一-學號-一姓名一-成績-一(輸入0時結朿)：n); cinkey;if(key=O)break;cinname;cingrade

18、;return t;/ -刪除樹中的結點-/void Delete(bstree&p)bstreeq,s;if(!p-rchild)Q=P；p二q-lchild ;delete q;else if(!p-lchild)Q=P；p=p-rchild;delete q;elseQ=P；s=p-lchild;while(s-rchild)q二 s;s=s-rchild;p-name=s-name; 辻(q!=p)q-rchild=s-lchiId; elseq-lch訂d二s-lchild; delete s; voidDeleteData(bstree&t, keytype key)if (! t

19、) printfC沒有該信息，請重新輸入！ n); cinkey;DeleteData(t, key);elseif (t-key=key)Delete (t);printf (w刪除成功！ n);else if(t-keykey) DeleteData(t-lchild, key); elseDeleteData(t-rchild, key);/二叉樹的深度intTreeDepth (bstree t)intleft, right, max;if(t!二NULL) left=TreeDepth(t-lchild); right=TreeDepth(t-rchild); max=leftrig

20、ht?left:right;return max+1;elsereturn 0;/樹狀輸出二叉樹 voidPrintTree (bstreet,int layer) int k; if(t=NULL) return ;PrintTree(t-rchild, layer+1); for(k=0:layer:k+)cout/z ”；coutt-ke5r，z n/z;PrintTree(t-lchild, layer+1);/-主函數測試-/int mainOint d;/system(cls);system(，zColor 2f;keytype key;bstree t=NULL;t=CreatT

21、ree();d=TreeDepth(t);printf C二叉排序樹的樹形表示如下n);PrintTree (t, d);char choose;nametype name;bstree p;double grade;printf(” n);printf (- -請輸入你要選擇的操作-)；printfC-)printfC)printfCIIa插入信息llnz/)printfCIIb刪除信息llnz0printfCIIc查詢信息llnz0printfCIId修改信息H)printfCII0退出lln，z)printfCIIe對二叉排序樹進行非遞歸遍歷lln，z)printfC-IIW)print

22、fC-AnOprintf (，zn/z);printf（z/需要選擇的操作為：“）;cinchoose;coutendl;while(choose)switch(choose)case a :printf (”輸入需要插入的學生信息信息(學號為0時結束).n); printfC請輸入-一學號-一姓名一-成績-一(輸入0時結束)：n); cinkey;辻(key=0) PrintTree(t, d);printf(z，n*插入信息結束！ ”)； break;cinname;cingrade;while(key)t=InsertBST(t, key, name, grade);printf (諳輸

23、入-學號-一姓名一-成績一-(輸入0時結朿)：n); cinkey;if(key=0)printf (插入信息結束!);break;cinname;cingrade;break;case b :printf (請輸入要刪除信息學生的學號：n)； cinkey;DeleteData(t, key); d=TreeDepth(t);printf (刪除結點后二叉樹的樹形顯示如下n);PrintTreeU, d);break;case c :cout請輸入要查詢學生的學號：endl; cinkey;p=SearchBST(t, key);辻(p=NULL)cout?，無査詢的關鍵字：keyendl;

24、elsecout成績tsetw(20)姓名tsetw(20)key，zt，zsetw(20);coutp-nameztgradeendl;break;case d，:printf(”請輸入要修改學生的學號：n);cinkey;p=SearchBST(t, key);if(p=NULL)cout無你所要修改的關鍵字：name;printf (n諳輸入修改的成績：)；cingrade;p-name=name;p-grade=grade;printf (”n 修改成功! n);break;case e :printf(”沒有任何信息，請先輸入信息！ ”)；elsecout學號tsetw(20) 姓名tsetw(20)成績endl;printf (-非遞歸先序遍歷 -n);printf Cn9;x_print(t);printf (”-非遞歸中序遍歷 -n);printf(n);z_print(t);printf (，?-非遞歸后序遍歷 -n);printf(n);h_print(t);bre