二叉排序樹的操作

1、內(nèi)蒙古科技大學(xué)課程設(shè)計任務(wù)書課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)計題目二叉排序樹的操作指導(dǎo)教師孫濤時間2011/6/132011/6/23一、教學(xué)要求1. 掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力2. 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等根本方法和技能3. 提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力4. 訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般標(biāo)準(zhǔn)進行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)二、設(shè)計資料及參數(shù)每個學(xué)生在教師提供的課程設(shè)計題目中任意選擇一題，獨立完成，題目選定后不可更換。二叉排序樹的操作以二叉鏈表表示二叉排序樹，在此根底上實現(xiàn)二叉排

2、序樹的操作。要求設(shè)計類或類模板來描述二叉排序樹，包含必要的構(gòu)造函數(shù)和析構(gòu)函數(shù)，以及其他能夠完成如下功能的成員函數(shù)：v 創(chuàng)立二叉排序樹v 輸出二叉排序樹v 在二叉排序樹中查找給定值v 在二叉排序樹中插入新結(jié)點v 在二叉排序樹中刪除給定值 并設(shè)計主函數(shù)測試該類或類模板。三、設(shè)計要求及成果1. 分析課程設(shè)計題目的要求2. 寫出詳細設(shè)計說明3. 編寫程序代碼，調(diào)試程序使其能正確運行4. 設(shè)計完成的軟件要便于操作和使用5. 設(shè)計完成后提交課程設(shè)計報告四、進度安排資料查閱與討論1天系統(tǒng)分析2天系統(tǒng)的開發(fā)與測試5天編寫課程設(shè)計說明書和驗收2天五、評分標(biāo)準(zhǔn)1. 根據(jù)平時上機考勤、表現(xiàn)和進度，教師將每天點名和檢

3、查2. 根據(jù)課程設(shè)計完成情況，必須有可運行的軟件。3. 根據(jù)課程設(shè)計報告的質(zhì)量，如有雷同，那么所有雷同的所有人均判為不及格。4. 根據(jù)辯論的情況，應(yīng)能夠以清晰的思路和準(zhǔn)確、簡練的語言表達自己的設(shè)計和答復(fù)教師的提問六、建議參考資料1?數(shù)據(jù)結(jié)構(gòu) C2?數(shù)據(jù)結(jié)構(gòu)課程設(shè)計案例精編用C/C+描述?，李建學(xué) 等 編著，清華大學(xué)出版社3.?數(shù)據(jù)結(jié)構(gòu):用面向?qū)ο蠓椒ㄅcC+語言描述?，殷人昆 主編， 清華大學(xué)出版社 2007.6內(nèi)蒙古科技大學(xué)本科生課程設(shè)計論文題 目：二叉排序樹的操作學(xué)生姓名：羅芳學(xué) 號：0967111248專 業(yè)：計算機科學(xué)與技術(shù)班 級：09-2班指導(dǎo)教師：孫濤 2011年 6月 2

4、3日二叉排序樹的操作二叉排序樹的特點：假設(shè)它的左子樹不為空，那么它的左子樹上所有結(jié)點的值均小于它的根節(jié)點；假設(shè)它的右子樹不為空，那么它的右子樹上所有結(jié)點的值均小于它的根節(jié)點；它的左右子樹也分別為二叉排序樹； 二叉排序樹的結(jié)構(gòu)不是一次生成的，而是在查找過程中，當(dāng)樹中不存在該關(guān)鍵字時再進行插入。1 各成員函數(shù)的根本功能根據(jù)二叉排序樹的特點，可由如下函數(shù)來實現(xiàn)二叉排序樹的操作： bool SearchBST(int key,BiNode f,BiNode &p)根據(jù)關(guān)鍵字key查找結(jié)點，假設(shè)存在關(guān)鍵字與key相同的結(jié)點，那么函數(shù)的返回值為ture,并使f指向該結(jié)點的雙親結(jié)點，p指向該結(jié)點；假

5、設(shè)不存在，那么函數(shù)返回false。void InSertBST(int e)先調(diào)用bool SearchBST(int key,BiNode f,BiNode &p函數(shù)查找是否已經(jīng)存在關(guān)鍵字為e的結(jié)點，假設(shè)不存在，那么生成一個關(guān)鍵字為e的結(jié)點，假設(shè)存在，那么給出提示。void Create()函數(shù)通過調(diào)用void InSertBST(int e)創(chuàng)立一個個結(jié)點，并使得第一個結(jié)點為根節(jié)點，關(guān)鍵字比第一個結(jié)點的小的結(jié)點在根節(jié)點的左子樹上，關(guān)鍵字比根節(jié)點的大的結(jié)點在根節(jié)點的右子樹上，從而創(chuàng)立一棵二叉排序樹的。void Traverse()函數(shù)利用棧來實現(xiàn)二叉排序樹的中序遍歷，使二叉排序樹的關(guān)

6、鍵字從小到大排列輸出。在調(diào)用void DeleteBST(BiNode &p)前必須調(diào)用bool SearchBST(int key,BiNode f,BiNode &p)函數(shù)確定關(guān)鍵字為key的結(jié)點是否存在，假設(shè)存在，那么刪除，假設(shè)不存在，那么給出相應(yīng)的提示信息。2 各成員函數(shù)的具體實現(xiàn) void Create()生成二叉排序樹二叉排序樹實在查找過程中動態(tài)創(chuàng)立的，所以在Create()函數(shù)中，要根據(jù)輸入的關(guān)鍵字個數(shù)m，動態(tài)分配m*int大小的內(nèi)存空間，在輸入各個關(guān)鍵字各個關(guān)鍵字，以關(guān)鍵字為形參，調(diào)用m次插入函數(shù)void BSTree:InSertBST(int e)，逐個生成

7、二叉樹的結(jié)點，并使得根節(jié)點的左子樹的關(guān)鍵字都小于根節(jié)點右子樹的關(guān)鍵字。以輸入23 13 45 21 65 54為例，生成二叉排序樹的過程如圖1所示。232313452313214523136521452313546521452313圖1 生成二叉排序樹2.2 Void InSertBST(int e)函數(shù)插入一個新的結(jié)點要插入一個新的結(jié)點，首先要確定二叉排序樹中不存在該關(guān)鍵字的結(jié)點，所以先調(diào)用bool SearchBST(BiNode B,int key,BiNode f,BiNode &p)。假設(shè)函數(shù)返回值為false，函數(shù)中p指向與要插入的關(guān)鍵字大小最接近的葉子結(jié)點，生成一個新的結(jié)

8、點s并為其分配內(nèi)存空間，并使得s->data=e，s->lchild=s->rchild=NULL，比擬p中data域的值與要插入的關(guān)鍵字key的大小，假設(shè)key>p->data，那么p->rchild=s，假設(shè)key<p->data，那么p->lchild=s；假設(shè)函數(shù)返回至為true，說明二叉排序樹中已經(jīng)存在關(guān)鍵字為e的結(jié)點，那么給出提示信息“該關(guān)鍵字已存在！。由上述插入過程可知，每個新插入的結(jié)點都是葉子結(jié)點，如圖2所示，在圖1的根底上插入一個關(guān)鍵字為19的結(jié)點。19546521452313546519452113圖2 插入結(jié)點 圖3

9、刪除結(jié)點 2.3 void DeleteBST(BiNode &p)函數(shù)刪除結(jié)點在調(diào)用刪除函數(shù)刪除節(jié)點之前必須要調(diào)用bool SearchBST(BiNode B,int key,BiNode f,BiNode &p)函數(shù)，因為刪除函數(shù)的形參是個BiNode類型的值，而我們是根據(jù)關(guān)鍵字來刪除結(jié)點的，調(diào)用bool SearchBST(BiNode B,int key,BiNode f,BiNode &p)函數(shù)，找到關(guān)鍵字為key的結(jié)點p,再用p做形參，執(zhí)行void DeleteBST(BiNode &p)函數(shù)刪除結(jié)點p。假設(shè)p->lchild不為空，那么執(zhí)行

10、“q=p;p=p->lchild；delete q;語句 ，使p的雙親結(jié)點指向p的左孩子，再刪除pj結(jié)點；假設(shè)p->rchild不為空，那么執(zhí)行“q=p;p=p->rchild；delete q;語句,使p的雙親結(jié)點指向p的右孩子，再刪除節(jié)點p；假設(shè)p->lchild、p->rchild均不為空，使q=p;s=p->lchild;，再執(zhí)行“q=s;s=s->rchild;直到s->rchild為空，這樣就找到了p結(jié)點的直接前驅(qū)s結(jié)點和s的雙親結(jié)點q，將s結(jié)點的值賦值給p結(jié)點，q->rchild賦值給s->lchild，這樣就完成了刪除

11、操作，如圖3所示，在圖2的根底上刪除關(guān)鍵字為23的結(jié)點。2.4 bool BSTree:SearchBST(BiNode B,int key,BiNode f,BiNode &p)函數(shù)查找結(jié)點bool BSTree:SearchBST(BiNode B,int key,BiNode f,BiNode &p)函數(shù)采用遞歸調(diào)用的方式查找結(jié)點。并用bool做函數(shù)類型，使得其它函數(shù)在調(diào)用查找函數(shù)后能夠很簡單的根據(jù)函數(shù)返回值決定下一步操作。函數(shù)參數(shù)中B為要查找的二叉排序樹的根結(jié)點，假設(shè)B=NULL，那么直接返回false。key是要查找的關(guān)鍵字，f指向B結(jié)點的雙親結(jié)點，在第一次調(diào)用查找函

12、數(shù)時，由于B為根節(jié)點，所以f的初值為NULL，p用來返回查找成功后關(guān)鍵字為key的結(jié)點。假設(shè)B->data=key，那么將B賦值給p，返回true；假設(shè)B->data<key，那么返回SearchBST(B->lchild,key,B,p)，即讓f指向B結(jié)點、B指向B的左孩子結(jié)點，再用新f、B的值做參數(shù)調(diào)用查找函數(shù)；假設(shè)B->data>key，那么返回SearchBST(B->rchild,key,B,p)；即讓f指向B結(jié)點、B指向B的右孩子結(jié)點，再用新f、B的值做參數(shù)調(diào)用查找函數(shù)。函數(shù)的遞歸調(diào)用一直要到找到關(guān)鍵字為key的結(jié)點，返回true，或者在查

13、找了所有結(jié)點之后沒有找到關(guān)鍵字為key的結(jié)點返回false為止。2.5 void Traverse()函數(shù)遍歷二叉排序樹根據(jù)二叉排序樹的特點：根節(jié)點的關(guān)鍵字比左子樹的關(guān)鍵字大，比右子樹的關(guān)鍵字小，其左右子樹又分別是二叉排序樹附錄：#include<iostream>#include<stack>using namespace std;typedef struct BiTreeint data;BiTree *lchild;BiTree *rchild;*BiNode,BiTree;class BSTreeprivate:BiNode T;public: BSTree()

14、delete T; BSTree()T=NULL;BiNode Gethead()return T;void Create(); bool SearchBST(BiNode B,int key,BiNode f,BiNode &p);void InSertBST(int e);void DeleteBST(BiNode &p);void Traverse();bool BSTree:SearchBST(BiNode B,int key,BiNode f,BiNode &p)if(!B)p=f; return false;else if(key=B->data)p=

15、B; return true; else if(key<B->data)return SearchBST(B->lchild,key,B,p);else return SearchBST(B->rchild,key,B,p);void BSTree:InSertBST(int e)BiNode p,k=T,f=NULL;if(!SearchBST(k,e,f,p)BiNode s=(BiNode)malloc(sizeof(BiTree); s->data=e;s->lchild=s->rchild=NULL;if(!p)T=s;else if (e&

16、lt;p->data)p->lchild=s;elsep->rchild=s;elsecout<<"此關(guān)鍵字已存在！"<<endl;void BSTree:DeleteBST(BiNode &p)BiNode q,s; if(!p->lchild)q=p; p=p->rchild;delete q;else if(!p->rchild)q=p;p=p->lchild;delete q;elseq=p;s=p->lchild;while(s->rchild)q=s;s=s->rchil

17、d;p->data=s->data; if(q!=p)q->rchild=s->lchild;else q->lchild=s->lchild;delete s;cout<<"刪除后的"void BSTree:Traverse()cout<<"中序遍歷結(jié)果："stack<BiTree*>bi;BiTree *p;p=T;while(p|!bi.empty()if(p)bi.push(p);p=p->lchild;elsep = bi.top();bi.pop();cout<

18、;<p->data<<" "p=p->rchild;cout<<endl;void BSTree:Create()int m; cout<<"請輸入樹的長度:" cin>>m;int *s = (int *)malloc(sizeof(int) * m);cout<<"請輸入"<<m<<"個數(shù)"for(int i=0;i<m;+i)cin>>si; InSertBST(si);int main() BSTree B; BiNode p,k,f=NULL; int m,a; char n; B.Create(); B.Traverse(); cout<<"請選擇：1 創(chuàng)立二叉排序樹 2 查找關(guān)鍵字 3 插入節(jié)點 4 刪除節(jié)點 5退出"<<endl; cin>>a; while(a<5) if(a=1) B.BSTree(); BSTree B; B.Create(); B.Traverse(); else if(a=2) cout<<"請輸入要查找的關(guān)鍵字：" cin>>