《二叉排序樹的實現(xiàn)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計.doc》由會員分享，可在線閱讀，更多相關(guān)《二叉排序樹的實現(xiàn)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計.doc（35頁珍藏版）》請在匯文網(wǎng)上搜索。

1、 二叉排序樹的實現(xiàn)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計1.設(shè)計任務(wù)1） 實現(xiàn)二叉排序樹，包括生成、插入，刪除；2） 對二叉排序樹進(jìn)行先根、中根、和后根非遞歸遍歷；3） 每次對樹的修改操作和遍歷操作的顯示結(jié)果都需要在屏幕上 用樹的形狀表示出來。4） 分別用二叉排序樹和數(shù)組去存儲一個班(50人以上)的成員信 息(至少包括學(xué)號、姓名、成績3項),對比查找效率，并說明 為什么二叉排序樹效率高（或者低）。2. 函數(shù)模塊：2.1.主函數(shù)main模塊功能1.通過bstree CreatTree()操作建立二叉排序樹。 2.在二叉排序樹t中通過操作bstree InsertBST(bstree t,int key,nametyp

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

3、叉排序樹上刪除一個階段相當(dāng)于刪去有序系列中的一個記錄，只要在刪除某個節(jié)點之后依舊保持二叉排序樹的性質(zhì)即可。假設(shè)二叉排序樹上刪除節(jié)點為*p（指向節(jié)點的指針為p），其雙親節(jié)點為*f（節(jié)點指針為f）。若*p節(jié)點為葉子節(jié)點，則即左右均為空樹，由于刪去葉子節(jié)點不破壞整棵樹的結(jié)構(gòu)，則只需修改其雙親節(jié)點的指針即可；若*p節(jié)點只有左子樹或只有右子樹，此時只要令左子樹或右子樹直接成為其雙親節(jié)點*f的左子樹即可；若*p節(jié)點的左子樹和右子樹均不為空，其一可以令*p的左子樹為*f的左子樹，而*p的右子樹為*s的右子樹，其二可以令*p的直接前驅(qū)（或直接后繼）替代*p，然后再從二叉排序樹中刪去它的直接前驅(qū)（或直接后繼）。

4、在二叉排序樹中刪除一個節(jié)點的算法為void DeleteData(bstree &t,keytype key)若二叉排序樹t中存在關(guān)鍵字等于key的數(shù)據(jù)元素，則刪除該數(shù)據(jù)元素節(jié)點，并返回TRUE，否則返回FALSE。2.4插入模塊二叉排序樹是一種動態(tài)樹表，其特點是樹的結(jié)構(gòu)通常不是一次生成的，而是在查找的過程中，當(dāng)樹中不存在關(guān)鍵字等于給定值得節(jié)點時在進(jìn)行插入。新插入的節(jié)點一定是一個新添加的葉子節(jié)點，并且是查找不成功時查找路徑上訪問的最后一個節(jié)點的左孩子或右孩子的節(jié)點。一個無序系列可以通過構(gòu)造一棵二叉排序樹而變成一個有序系列，構(gòu)造樹的過程即為對無序系列進(jìn)行排序的過程， 并且每次插入的節(jié)點都是二叉排

5、序樹上新的葉子節(jié)點，則在進(jìn)行插入操作時，不必移動其他節(jié)點，僅需改變某個節(jié)點的指針由空變?yōu)榉强占纯?。二叉排序樹的插入算法為bstree InsertBST(bstree t,int key,nametype name,double grade) 若二叉排序樹中不存在關(guān)鍵字等于key的數(shù)據(jù)元素時，插入元素并返回TRUE。2.5查找模塊二叉排序樹又稱二叉查找樹，當(dāng)二叉排序樹不為空時，首先將給定的值和根節(jié)點的關(guān)鍵字比較，若相等則查找成功，否則將依據(jù)給定的值和根節(jié)點關(guān)鍵字之間的大小關(guān)系，分別在左子樹或右子樹上繼續(xù)進(jìn)行查找。為此定義一個二叉排序樹的查找算法為bstnode *SearchBST(bstre

6、e t,keytype key) 在根指針t所指向的二叉排序樹中查找關(guān)鍵字等于key的數(shù)據(jù)元素，如成功，返回指向該元素節(jié)點的指針，否則返回空指針。2.6效率比較compare模塊void compare()對數(shù)組和二叉排序樹的查找效率進(jìn)行比較比較。2.7二叉排序樹的遍歷先序遍歷也叫做先根遍歷。首先訪問根結(jié)點然后遍歷左子樹，最后遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹，如果二叉樹為空則返回。其實過程為：先遍歷左子樹root-left-left-left.-null，由于是先序遍歷，因此一遇到節(jié)點，便需要立即訪問；由于一直走到最左邊后，需要逐步返回到父節(jié)點訪

7、問右節(jié)點，因此必須有一個措施能夠?qū)?jié)點序列回溯。其一可以用棧記憶在訪問途中將依次遇到的節(jié)點保存下來。根據(jù)棧的先進(jìn)后出、后進(jìn)先出的特點特點。則可以用棧保存。每次都將遇到的節(jié)點壓入棧，當(dāng)左子樹遍歷完畢后從棧中彈出最后一個訪問的節(jié)點，然后訪問其右子樹。基本算法思想：1.先訪問根節(jié)點，將根節(jié)點入棧2.重復(fù)執(zhí)行兩大步驟：如果該節(jié)點左孩子存在，則訪問該左孩子節(jié)點，并將其指針入棧。重復(fù)以上操作，直到節(jié)點的左孩子不存在。將棧頂?shù)脑?，即其指針出棧，回到父?jié)點，如果該指針節(jié)點的右孩子存在，則將該指針指向的右孩子節(jié)點重復(fù)執(zhí)行以上步驟，直到桟為空為止。操作函數(shù)為void x_print(Tree T)中序遍歷：中序

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

9、取棧頂元素，并賦值給P，如果P的右孩子為空或P的右孩子等于q（即如果p的右孩子已訪問，則訪問根節(jié)點，即p指向的節(jié)點，并用q來記錄剛剛訪問的節(jié)點的指針），若p有右孩子，且右孩子沒有別訪問過，則p=p-rchild。操作函數(shù)為void h_print(Tree T)3.源代碼#include#include#include#include#include using namespace std;typedef string nametype;typedef unsigned long keytype;typedef struct node /結(jié)點的結(jié)構(gòu)體keytype key; nametype

10、name; int grade;struct node *lchild,*rchild;bstnode;typedef bstnode *bstree;/棧的定義/typedef struct /棧結(jié)構(gòu)bstree *base;bstree *top;int stacksize;Sqstack;int InitStack (Sqstack &s) /建立一個空棧s.base=(bstree*)malloc(1000 * sizeof(int);s.top=s.base;return 1;int Push(Sqstack &s ,node *e)/在棧頂插入元素（進(jìn)棧）*s.top=e;s.to

11、p=s.top+1;return 1;int Pop(Sqstack &s, bstree &e)/出棧if(s.top=s.base)return 0;else s.top=s.top-1;e=*s.top;return 1;/非遞歸歷遍并輸出結(jié)點信息/*-先序非遞歸遍歷-*/void x_print(node *t)Sqstack s;InitStack(s);bstnode *p;p=t;while(p|!(s.top=s.base)if(p) Push(s,p);coutkeytsetw(20);coutnametsetw(20);coutgradetlchild;else Pop(s

12、,p);p=p-rchild;/*-中序非遞歸遍歷-*/void z_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;else Pop(s,p);coutkeytsetw(20);coutnametsetw(20);coutgradetrchild;/*-非遞歸后序遍歷-*/void h_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; else p=*(s.top-1); if(p-rchild=q) Pop(s,q);p=NULL; coutkeytsetw(20);coutnametsetw(20);coutgradetrchild;q=NULL; /遞歸查找二叉樹/ /*-歸查找，若找到就返回指向該結(jié)點的指針，否則返回空-*/bstnode *SearchBST(bstree t,keytype key) if(t=NULL|key=t-key)return t;if(keykey)return SearchBST(t-lch