《北郵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)—二叉排序樹(共12頁(yè)).doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《北郵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)—二叉排序樹(共12頁(yè)).doc（12頁(yè)珍藏版）》請(qǐng)?jiān)趨R文網(wǎng)上搜索。

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù) 據(jù) 結(jié) 構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：_二叉排序樹_學(xué)生姓名：_班 級(jí)：_班內(nèi)序號(hào)：_學(xué) 號(hào)：_日 期：_1實(shí)驗(yàn)要求根據(jù)二叉排序樹的抽象數(shù)據(jù)類型的定義，使用二叉鏈表實(shí)現(xiàn)一個(gè)二叉排序樹。二叉排序樹的基本功能：1.二叉排序樹的建立2.二叉排序樹的查找3.二叉排序樹的插入4.二叉排序樹的刪除5.二叉排序樹的銷毀6.其他：自定義操作編寫測(cè)試main()函數(shù)測(cè)試二叉排序樹的正確性2. 程序分析2.1 存儲(chǔ)結(jié)構(gòu) 二叉鏈表Data Lchild Rchild 2.2 程序流程 (或程序結(jié)構(gòu)、或類關(guān)系圖等表明程序構(gòu)成的內(nèi)容，一般為流程圖等) 開始 2.2.1.流程圖 從文件讀取原始數(shù)據(jù) 建

2、立排序二叉樹該元素和根節(jié)點(diǎn)數(shù)據(jù)比較大小大小根節(jié)點(diǎn)移向右孩子是根節(jié)點(diǎn)移向左孩子 當(dāng)前根節(jié)點(diǎn)是否存在判斷下一個(gè)元素否該元素節(jié)點(diǎn)插入到當(dāng)前根節(jié)點(diǎn)位置是 是否還剩余元素用戶輸入操作 判斷操作退出銷毀刪除插入查找 結(jié)束 刪除該節(jié)點(diǎn)執(zhí)行查找操作執(zhí)行查找操作直到為空節(jié)點(diǎn)該元素和當(dāng)前根節(jié)點(diǎn)數(shù)據(jù)比較大小是是否銷毀完刪除最終節(jié)點(diǎn)在該位置插入其節(jié)點(diǎn) 刪除下一節(jié)點(diǎn)小大是否否是否銷毀完根節(jié)點(diǎn)移向左孩子根節(jié)點(diǎn)移向右孩子當(dāng)前根節(jié)點(diǎn)值是否相等是輸出該節(jié)點(diǎn)情況 2.2.2.偽代碼1. 從文件讀取待建樹元素2. 建樹，若待插入元素比根節(jié)點(diǎn)小，向左子樹前進(jìn)并重復(fù)比較左子樹根節(jié)點(diǎn)，若待插入元素比根節(jié)點(diǎn)大，向右子樹前進(jìn)并重復(fù)比較右子樹

3、根節(jié)點(diǎn)，直至找到空節(jié)點(diǎn)則插入該元素，不斷插入直至不剩下元素。3. 用戶選擇操作。4. 若用戶選擇查找，則現(xiàn)由用戶輸入待查找數(shù)值。從根節(jié)點(diǎn)開始比較，若較小則移至左子樹，若較大則移至右子樹，直至關(guān)鍵碼相等，則輸出節(jié)點(diǎn)情況。5. 若用戶選擇插入，則現(xiàn)由用戶輸入待插入數(shù)值。從根節(jié)點(diǎn)開始比較，若較小則移至左子樹，若較大則移至右子樹，直至到空節(jié)點(diǎn)，則插入該元素。6. 若用戶選擇刪除，則現(xiàn)由用戶輸入待刪除數(shù)值。從根節(jié)點(diǎn)開始比較，若較小則移至左子樹，若較大則移至右子樹，直至關(guān)鍵碼相等； 1）.若該節(jié)點(diǎn)為葉子節(jié)點(diǎn)，則直接刪除； 2）.若該節(jié)點(diǎn)無左子樹，則其雙親節(jié)點(diǎn)直接與其右子樹根節(jié)點(diǎn)連接，再刪除該節(jié)點(diǎn)； 3）.

4、若該節(jié)點(diǎn)有左子樹，則其左子樹的最右節(jié)點(diǎn)數(shù)值直接覆蓋該節(jié)點(diǎn)數(shù)值，再刪除最后節(jié)點(diǎn)。7. 若用戶選擇銷毀，則不斷執(zhí)行刪除操作直至不剩余節(jié)點(diǎn)。8. 若用戶選擇退出，則程序結(jié)束。2.3 關(guān)鍵算法分析關(guān)鍵代碼即刪除操作，代碼如下：void Delete(BiNode* &R)BiNode* q=new BiNode;BiNode *s=new BiNode;if(R->lch=NULL)q=R;R=R->rch;delete q;else if(R->rch=NULL)q=R;R=R->lch;delete q;elseq=R; s=R->lch; while(s-&

5、gt;rch!=NULL)q=s;s=s->rch; R->data=s->data;if(q!=R)q->rch=s->lch;elseR->lch=s->lch;delete s;void Deletedata(BiNode* &R, int key)if(R=NULL) return;if(R->data=key) Delete(R);else if(R->data>key) Deletedata(R->lch,key);else Deletedata(R->rch,key);首先先要定位到要?jiǎng)h除的節(jié)點(diǎn)，不斷

6、遞歸調(diào)用deletedata這個(gè)函數(shù)，找到數(shù)值與需要?jiǎng)h除節(jié)點(diǎn)的數(shù)值相等的節(jié)點(diǎn)時(shí)，調(diào)用delete這個(gè)函數(shù)。刪除節(jié)點(diǎn)時(shí)需要分析三種情況。1）.若該節(jié)點(diǎn)為葉子節(jié)點(diǎn)，則直接刪除；2）.若該節(jié)點(diǎn)無左子樹，則其雙親節(jié)點(diǎn)直接與其右子樹根節(jié)點(diǎn)連接，再刪除該節(jié)點(diǎn)；3）.若該節(jié)點(diǎn)有左子樹，則其左子樹的最右節(jié)點(diǎn)數(shù)值直接覆蓋該節(jié)點(diǎn)數(shù)值，再刪除最后節(jié)點(diǎn)。算法時(shí)間復(fù)雜度：O（n2）2.4 其他特殊情況處理：若文件里元素為空，不存在任何元素，則無法完成建樹，選擇查找操作時(shí)也會(huì)提示無元素；另外，若查找不存在的元素是，最后查找到空節(jié)點(diǎn)也會(huì)提示無此元素。3. 程序運(yùn)行結(jié)果分析4. 總結(jié)4.1實(shí)驗(yàn)的難點(diǎn)和關(guān)鍵點(diǎn) 本實(shí)驗(yàn)的難點(diǎn)和關(guān)

7、鍵點(diǎn)主要在刪除元素上，為了保持二叉排序樹的有序性。刪除特定節(jié)點(diǎn)是要分三種情況討論 1）.若該節(jié)點(diǎn)為葉子節(jié)點(diǎn)，則直接刪除；2）.若該節(jié)點(diǎn)無左子樹，則其雙親節(jié)點(diǎn)直接與其右子樹根節(jié)點(diǎn)連接，再刪除該節(jié)點(diǎn)；3）.若該節(jié)點(diǎn)有左子樹，則其左子樹的最右節(jié)點(diǎn)數(shù)值直接覆蓋該節(jié)點(diǎn)數(shù)值，再刪除最后節(jié)點(diǎn)。4.2心得體會(huì) 通過這次試驗(yàn)讓我進(jìn)一步對(duì)樹的應(yīng)用有了進(jìn)一步的了解，同時(shí)對(duì)查找這種基本數(shù)據(jù)操作有了較深刻的認(rèn)識(shí).同時(shí)在二叉排序樹的刪除操作的代碼編寫時(shí)，讓我明白了不同情況的不同處理方式。養(yǎng)成了更嚴(yán)謹(jǐn)?shù)木帉懘a的思維方式。附：程序代碼#include<iostream>#include<fstream&g

8、t;using namespace std;class BiNodepublic:int data;BiNode* lch;BiNode* rch; BiNode():lch(NULL),rch(NULL);BiNode* Search(BiNode* R,int key) if(R=NULL) cout<<"無查詢結(jié)果"<<endl;return NULL; if(R->data=key) return R; if(R->data<key) return Search(R->rch,key); if(R->data&g

9、t;key) return Search(R->lch,key);void Insert(BiNode* &R,BiNode* S)if(R=NULL) R=S;if(R->data<S->data) Insert(R->rch,S);if(R->data>S->data) Insert(R->lch,S);BiNode* Create(int data,int n)BiNode* R=new BiNode;R=NULL;for(int i=0;i<n;i+)BiNode* Q=new BiNode;Q->data=da

10、tai;Insert(R,Q);return R;void Delete(BiNode* &R)BiNode* q=new BiNode;BiNode *s=new BiNode;if(R->lch=NULL)q=R;R=R->rch;delete q;else if(R->rch=NULL)q=R;R=R->lch;delete q;elseq=R; s=R->lch; while(s->rch!=NULL)q=s;s=s->rch; R->data=s->data;if(q!=R)q->rch=s->lch;else

11、R->lch=s->lch;delete s;void Deletedata(BiNode* &R, int key)if(R=NULL) return;if(R->data=key) Delete(R);else if(R->data>key) Deletedata(R->lch,key);else Deletedata(R->rch,key);void Deleteall(BiNode* &R,int data,int n)for(int i=0;i<n;i+)Deletedata(R,datai);void main()in

12、t data200;BiNode *Root;Root=NULL;ifstream ifile("D:/TEST/data.txt");int i=0,n=0;cout<<"從文件讀入數(shù)據(jù)如下："<<endl;while(ifile>>datai)cout<<datai<<" "i+;n+;Root=Create(data,n);while(1)cout<<"n請(qǐng)輸入進(jìn)行的操作：n1.查找n2.插入n3.刪除n4.銷毀n5.退出n"int ch

13、oice;cin>>choice; while(choice!=1&&choice!=2&&choice!=3&&choice!=4&&choice!=5) cout<<"無該選項(xiàng)，請(qǐng)重新輸入" cin>>choice;switch(choice)case 1: cout<<"請(qǐng)輸入查找的數(shù)據(jù)"<<endl;int n;int i;cin>>n;BiNode* R;R=Search(Root,n);if(R->lch!=NULL)