實(shí)用文檔數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱(chēng)：______二叉排序樹(shù)___________學(xué)生：____________________班級(jí)：_______________班序號(hào)：_______________________學(xué)號(hào)：________________日期：________________

1．實(shí)驗(yàn)要求根據(jù)二叉排序樹(shù)的抽象數(shù)據(jù)類(lèi)型的定義，使用二叉鏈表實(shí)現(xiàn)一個(gè)二叉排序樹(shù)。二叉排序樹(shù)的基本功能：1.二叉排序樹(shù)的建立2.二叉排序樹(shù)的查找3.二叉排序樹(shù)的插入4.二叉排序樹(shù)的刪除5.二叉排序樹(shù)的銷(xiāo)毀6.其他：自定義操作編寫(xiě)測(cè)試main()函數(shù)測(cè)試二叉排序樹(shù)的正確性2.程序分析2.1存儲(chǔ)結(jié)構(gòu)二叉鏈表DataLchildRchildDataLchildRchild2.2程序流程(或程序結(jié)構(gòu)、或類(lèi)關(guān)系圖等表明程序構(gòu)成的容，一般為流程圖等)開(kāi)始2.2.1.流程圖開(kāi)始從文件讀取原始數(shù)據(jù)從文件讀取原始數(shù)據(jù)建立排序二叉樹(shù)建立排序二叉樹(shù)該元素和根節(jié)點(diǎn)數(shù)據(jù)比較大小該元素和根節(jié)點(diǎn)數(shù)據(jù)比較大小大小大小根節(jié)點(diǎn)移向右孩子根節(jié)點(diǎn)移向右孩子是根節(jié)點(diǎn)移向左孩子是根節(jié)點(diǎn)移向左孩子當(dāng)前根節(jié)點(diǎn)是否存在當(dāng)前根節(jié)點(diǎn)是否存在判斷下一個(gè)元素判斷下一個(gè)元素否否該元素節(jié)點(diǎn)插入到當(dāng)前根節(jié)點(diǎn)位置該元素節(jié)點(diǎn)插入到當(dāng)前根節(jié)點(diǎn)位置是是否還剩余元素是是否還剩余元素用戶輸入操作用戶輸入操作判斷操作判斷操作退出銷(xiāo)毀刪除插入查找退出銷(xiāo)毀刪除插入查找結(jié)束刪除該節(jié)點(diǎn)執(zhí)行查找操作執(zhí)行查找操作直到為空節(jié)點(diǎn)該元素和當(dāng)前根節(jié)點(diǎn)數(shù)據(jù)比較大小結(jié)束刪除該節(jié)點(diǎn)執(zhí)行查找操作執(zhí)行查找操作直到為空節(jié)點(diǎn)該元素和當(dāng)前根節(jié)點(diǎn)數(shù)據(jù)比較大小是是是否銷(xiāo)毀完刪除最終節(jié)點(diǎn)在該位置插入其節(jié)點(diǎn)是否銷(xiāo)毀完刪除最終節(jié)點(diǎn)在該位置插入其節(jié)點(diǎn)刪除下一節(jié)點(diǎn)小刪除下一節(jié)點(diǎn)小大大是否否是否否是否銷(xiāo)毀完是否銷(xiāo)毀完根節(jié)點(diǎn)移向左孩子根節(jié)點(diǎn)移向右孩子根節(jié)點(diǎn)移向左孩子根節(jié)點(diǎn)移向右孩子當(dāng)前根節(jié)點(diǎn)值是否相等當(dāng)前根節(jié)點(diǎn)值是否相等是是輸出該節(jié)點(diǎn)情況輸出該節(jié)點(diǎn)情況2.2.2.偽代碼從文件讀取待建樹(shù)元素建樹(shù)，若待插入元素比根節(jié)點(diǎn)小，向左子樹(shù)前進(jìn)并重復(fù)比較左子樹(shù)根節(jié)點(diǎn)，若待插入元素比根節(jié)點(diǎn)大，向右子樹(shù)前進(jìn)并重復(fù)比較右子樹(shù)根節(jié)點(diǎn)，直至找到空節(jié)點(diǎn)則插入該元素，不斷插入直至不剩下元素。用戶選擇操作。若用戶選擇查找，則現(xiàn)由用戶輸入待查找數(shù)值。從根節(jié)點(diǎn)開(kāi)始比較，若較小則移至左子樹(shù)，若較大則移至右子樹(shù)，直至關(guān)鍵碼相等，則輸出節(jié)點(diǎn)情況。若用戶選擇插入，則現(xiàn)由用戶輸入待插入數(shù)值。從根節(jié)點(diǎn)開(kāi)始比較，若較小則移至左子樹(shù)，若較大則移至右子樹(shù)，直至到空節(jié)點(diǎn)，則插入該元素。若用戶選擇刪除，則現(xiàn)由用戶輸入待刪除數(shù)值。從根節(jié)點(diǎn)開(kāi)始比較，若較小則移至左子樹(shù)，若較大則移至右子樹(shù)，直至關(guān)鍵碼相等；1）.若該節(jié)點(diǎn)為葉子節(jié)點(diǎn)，則直接刪除；2）.若該節(jié)點(diǎn)無(wú)左子樹(shù)，則其雙親節(jié)點(diǎn)直接與其右子樹(shù)根節(jié)點(diǎn)連接，再刪除該節(jié)點(diǎn)；3）.若該節(jié)點(diǎn)有左子樹(shù)，則其左子樹(shù)的最右節(jié)點(diǎn)數(shù)值直接覆蓋該節(jié)點(diǎn)數(shù)值，再刪除最后節(jié)點(diǎn)。若用戶選擇銷(xiāo)毀，則不斷執(zhí)行刪除操作直至不剩余節(jié)點(diǎn)。若用戶選擇退出，則程序結(jié)束。2.3關(guān)鍵算法分析關(guān)鍵代碼即刪除操作，代碼如下：voidDelete(BiNode*&R){ BiNode*q=newBiNode; BiNode*s=newBiNode; if(R->lch==NULL){ q=R; R=R->rch; deleteq;} elseif(R->rch==NULL){ q=R; R=R->lch; deleteq; } else{ q=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 R->lch=s->lch; deletes;}}voidDeletedata(BiNode*&R,intkey){ if(R==NULL)return; if(R->data==key)Delete(R); elseif(R->data>key)Deletedata(R->lch,key); elseDeletedata(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í)需要分析三種情況。1）.若該節(jié)點(diǎn)為葉子節(jié)點(diǎn)，則直接刪除；2）.若該節(jié)點(diǎn)無(wú)左子樹(shù)，則其雙親節(jié)點(diǎn)直接與其右子樹(shù)根節(jié)點(diǎn)連接，再刪除該節(jié)點(diǎn)；3）.若該節(jié)點(diǎn)有左子樹(shù)，則其左子樹(shù)的最右節(jié)點(diǎn)數(shù)值直接覆蓋該節(jié)點(diǎn)數(shù)值，再刪除最后節(jié)點(diǎn)。算法時(shí)間復(fù)雜度：O（n^2）2.4其他特殊情況處理：若文件里元素為空，不存在任何元素，則無(wú)法完成建樹(shù)，選擇查找操作時(shí)也會(huì)提示無(wú)元素；另外，若查找不存在的元素是，最后查找到空節(jié)點(diǎn)也會(huì)提示無(wú)此元素。程序運(yùn)行結(jié)果分析總結(jié)4.1實(shí)驗(yàn)的難點(diǎn)和關(guān)鍵點(diǎn)本實(shí)驗(yàn)的難點(diǎn)和關(guān)鍵點(diǎn)主要在刪除元素上，為了保持二叉排序樹(shù)的有序性。刪除特定節(jié)點(diǎn)是要分三種情況討論1）.若該節(jié)點(diǎn)為葉子節(jié)點(diǎn)，則直接刪除；2）.若該節(jié)點(diǎn)無(wú)左子樹(shù)，則其雙親節(jié)點(diǎn)直接與其右子樹(shù)根節(jié)點(diǎn)連接，再刪除該節(jié)點(diǎn)；3）.若該節(jié)點(diǎn)有左子樹(shù)，則其左子樹(shù)的最右節(jié)點(diǎn)數(shù)值直接覆蓋該節(jié)點(diǎn)數(shù)值，再刪除最后節(jié)點(diǎn)。4.2心得體會(huì)通過(guò)這次試驗(yàn)讓我進(jìn)一步對(duì)樹(shù)的應(yīng)用有了進(jìn)一步的了解，同時(shí)對(duì)查找這種基本數(shù)據(jù)操作有了較深刻的認(rèn)識(shí).同時(shí)在二叉排序樹(shù)的刪除操作的代碼編寫(xiě)時(shí)，讓我明白了不同情況的不同處理方式。養(yǎng)成了更嚴(yán)謹(jǐn)?shù)木帉?xiě)代碼的思維方式。附：程序代碼#include<iostream>#include<fstream>usingnamespacestd;classBiNode{public: intdata; BiNode*lch; BiNode*rch;BiNode():lch(NULL),rch(NULL){};};BiNode*Search(BiNode*R,intkey){if(R==NULL){cout<<"無(wú)查詢結(jié)果"<<endl;returnNULL;}if(R->data==key)returnR;if(R->data<key)returnSearch(R->rch,key);if(R->data>key)returnSearch(R->lch,key);}voidInsert(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(intdata[],intn){ BiNode*R=newBiNode; R=NULL; for(inti=0;i<n;i++){ BiNode*Q=newBiNode; Q->data=data[i]; Insert(R,Q); } returnR;}voidDelete(BiNode*&R){ BiNode*q=newBiNode; BiNode*s=newBiNode; if(R->lch==NULL){ q=R; R=R->rch; deleteq;} elseif(R->rch==NULL){ q=R; R=R->lch; deleteq; } else{ q=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 R->lch=s->lch; deletes;}}voidDeletedata(BiNode*&R,intkey){ if(R==NULL)return; if(R->data==key)Delete(R); elseif(R->data>key)Deletedata(R->lch,key); elseDeletedata(R->rch,key);}voidDeleteall(BiNode*&R,intdata[],intn){ for(inti=0;i<n;i++){ Deletedata(R,data[i]);} }voidmain(){ intdata[200]; BiNode*Root; Root=NULL; ifstreamifile("D://TEST//data.txt"); inti=0,n=0; cout<<"從文件讀入數(shù)據(jù)如下："<<endl; while(ifile>>data[i]){ cout<<data[i]<<""; i++; n++; }Root=Create(data,n);while(1){cout<<"\n請(qǐng)輸入進(jìn)行的操作：\n1.查找\n2.插入\n3.刪除\n4.銷(xiāo)毀\n5.退出\n";intchoice;cin>>choice;while(choice!=1&&choice!=2&&choice!=3&&choice!=4&&choice!=5){ cout<<"無(wú)該選項(xiàng)，請(qǐng)重新輸入"; cin>>choice;} switch(choice){ case1:{ cout<<"請(qǐng)輸入查找的數(shù)據(jù)"<<endl; intn; inti; cin>>n; BiNode*R; R=Search(Root,n); if(R->lch!=NULL){ cout<<"該數(shù)據(jù)節(jié)點(diǎn)左孩子數(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; } case2:{ cout<<"請(qǐng)輸入插入數(shù)據(jù)"<<endl; intt; cin>>t; BiNode*w=newBiNode; w->data=t; Insert(Root,w); cout<<"插入成功"<<endl; cout<<"目前關(guān)鍵碼為："; for(inti=0;i<n;i++){ cout<<data[i]<<"";} cout<<t<<""<<endl; break; } case3:{ intk; cout<<"請(qǐng)輸入刪除數(shù)據(jù)"<<endl; ints,judge=1; cin>>s; for(k=0;k<n;k++){ if(data[k]==s) break; } if(k==n){