北郵大數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)—二叉排序樹

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱： 二叉排序樹 學(xué)生： 班 級(jí)： 班序號(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)成的容,221.流程圖開始從文件讀取原始數(shù)據(jù)建立排序二叉樹當(dāng)前根節(jié)點(diǎn)是否存在判斷下一個(gè)元素否該元素節(jié)點(diǎn)插入到當(dāng)

2、前根節(jié)點(diǎn)位置用戶輸入操作判斷操作否A/ / 執(zhí)行查找操作直到為 空節(jié)點(diǎn)執(zhí)行查找操作該元素和當(dāng)前根節(jié)點(diǎn)耳r數(shù)據(jù)比在該位置插入其節(jié)點(diǎn)刪除最終節(jié)點(diǎn)較大小刪除該節(jié)點(diǎn)是否銷毀完結(jié)束小刪除下一節(jié)點(diǎn)根節(jié)點(diǎn)移向根節(jié)點(diǎn)移向右孩子左孩子是否銷毀完當(dāng)前根節(jié) 點(diǎn)值是否 相等是輸出該節(jié)點(diǎn)情況偽代碼1.從文件讀取待建樹元素2. 建樹，若待插入元素比根節(jié)點(diǎn)小，向左子樹前進(jìn)并重復(fù)比較左子樹根節(jié)點(diǎn)，若待插入元素 比根節(jié)點(diǎn)大， 向右子樹前進(jìn)并重復(fù)比較右子樹根節(jié)點(diǎn)， 直至找到空節(jié)點(diǎn)則插入該元素， 不斷 插入直至不剩下元素。3. 用戶選擇操作。4. 若用戶選擇查找， 則現(xiàn)由用戶輸入待查找數(shù)值。 從根節(jié)點(diǎn)開始比較， 若較小則移至左子樹

3、， 若較大則移至右子樹，直至關(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) .若該節(jié)點(diǎn)有左子樹，則其左子樹的最右節(jié)點(diǎn)數(shù)值直接覆蓋該節(jié)點(diǎn)數(shù)值，再刪除最后 節(jié)點(diǎn)。7. 若用戶選擇銷毀，則不斷執(zhí)行刪除操作直至不剩余節(jié)點(diǎn)。8. 若用

4、戶選擇退出，則程序結(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->rch!=NULL)q=s;s=s->rch;R->data=s->data;if(q!=R)q->rch=s-&

5、gt;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)，不斷遞歸調(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í)需要分析三種

6、情況。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ù)雜度： 0( 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)鍵點(diǎn)主要在刪除元素上，為了保持二叉排序樹的有序性。刪除特定節(jié)點(diǎn)是要分三種情況討論 1) 若該節(jié)點(diǎn)為葉子節(jié)點(diǎn)，則直

7、接刪除；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> using namespace std; class BiNode public: int data

8、; 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>key) return Search(R->lch,key);void Insert

9、(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=datai;Insert(R,Q);return R;void Delete(BiNode*

10、 &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;elseR->lch=s->lch;delete s;void Deleted

11、ata(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()int data200;BiNode *Root;Root=NULL;ifstre

12、am 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 choice;cin>>choice; while(choice

13、!=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)cout<<" 該數(shù)據(jù)節(jié)點(diǎn)左

14、孩子數(shù)據(jù)為 "<<R->lch->data<<endl; if(R->rch!=NULL)cout<<" 該數(shù)據(jù)節(jié)點(diǎn)右孩子數(shù)據(jù)為 "<<R->rch->data<<endl; if(R->lch=NULL&&R->rch=NULL)cout<<" 該數(shù)據(jù)節(jié)點(diǎn)為葉子節(jié)點(diǎn) " break;case 2:cout<<" 請(qǐng)輸入插入數(shù)據(jù) "<<endl;int t;cin>&

15、gt;t;BiNode* w=new BiNode; w->data=t;Insert(Root,w); cout<<" 插入成功 "<<endl; cout<<" 目前關(guān)鍵碼為： "for(int i=0;i<n;i+) cout<<datai<<" " cout<<t<<" "<<endl;break;case 3:int k;cout<<" 請(qǐng)輸入刪除數(shù)據(jù) "<<endl;int s,judge=1;cin>>s;for(k=0;k<n;k+) if(datak=s) break;if(k=n)cout<<" 該數(shù)據(jù)不存在 "<<endl; e