實用文檔數據結構實驗報告實驗名稱：______二叉排序樹___________學生：____________________班級：_______________班序號：_______________________學號：________________日期：________________

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