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

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

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

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

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

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

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

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

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

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

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

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

13、找了所有結點之后沒有找到關鍵字為key的結點返回false為止。2.5 void Traverse()函數遍歷二叉排序樹根據二叉排序樹的特點：根節點的關鍵字比左子樹的關鍵字大，比右子樹的關鍵字小，其左右子樹又分別是二叉排序樹附錄：#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<<"此關鍵字已存在！"<<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<<"中序遍歷結果："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<<"個數"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 創立二叉排序樹 2 查找關鍵字 3 插入節點 4 刪除節點 5退出"<<endl; cin>>a; while(a<5) if(a=1) B.BSTree(); BSTree B; B.Create(); B.Traverse(); else if(a=2) cout<<"請輸入要查找的關鍵字：" cin>>