第一篇：數(shù)據(jù)結構二叉樹操作驗證實驗報告
班級：計算機11-2 學號：40 姓名：朱報龍
成績：_________
實驗七 二叉樹操作驗證
一、實驗目的
⑴ 掌握二叉樹的邏輯結構；
⑵ 掌握二叉樹的二叉鏈表存儲結構；
⑶ 掌握基于二叉鏈表存儲的二叉樹的遍歷操作的實現(xiàn)。
二、實驗內容
⑴ 建立一棵含有n個結點的二叉樹，采用二叉鏈表存儲；
⑵ 前序（或中序、后序）遍歷該二叉樹。
三、設計與編碼
#include
void inorder(void visit(BTreeNode
void postorder(void visit(BTreeNode
static void fun(BTreeNode data;}//訪問結點 protected: BTreeNode //***********************建樹******************************* template template //***********************遍歷******************************* template {cout <<“遞歸先序遍歷二叉樹：”;s.preorder(s.fun);cout < 答：經(jīng)常忘記對頭結點的定義，以至于程序出錯，經(jīng)定義頭結點，使程序正常運行。 b)程序運行的結果如何？ 四、實驗小結 多練習，多上機，耐心調試程序，找出錯誤，多總結。 課 程 設 計 報 告 課程名稱 數(shù)據(jù)結構課程設計 題 目平衡二叉樹操作 指導教師 設計起止日 2010-5-16 學 院 計算機學院 專 業(yè) 軟件工程 學生姓名 班級/學號------------成 績 _________________ 一． 需求分析 1、建立平衡二叉樹并進行創(chuàng)建、增加、刪除、調平等操作。 2、設計一個實現(xiàn)平衡二叉樹的程序，可進行創(chuàng)建、增加、刪除、調平等操作，實現(xiàn)動態(tài)的輸入數(shù)據(jù)，實時的輸出該樹結構。 3、測試數(shù)據(jù)：自選數(shù)據(jù) 二． 概要設計 平衡二叉樹是在構造二叉排序樹的過程中，每當插入一個新結點時，首先檢查是否因插入新結點而破壞了二叉排序樹的平衡性，若是，則找出其中的最小不平衡子樹，在保持二叉排序樹特性的前提下，調整最小不平衡子樹中各結點之間的鏈接關系，進行相應的旋轉，使之成為新的平衡子樹。具體步驟如下： ⑴ 每當插入一個新結點，從該結點開始向上計算各結點的平衡因子，即計算該結點的祖先結點的平衡因子，若該結點的祖先結點的平衡因子的絕對值均不超過1，則平衡二叉樹沒有失去平衡，繼續(xù)插入結點； ⑵ 若插入結點的某祖先結點的平衡因子的絕對值大于1，則找出其中最小不平衡子樹的根結點； ⑶ 判斷新插入的結點與最小不平衡子樹的根結點的關系，確定是哪種類型的調整； ⑷ 如果是LL型或RR型，只需應用扁擔原理旋轉一次，在旋轉過程中，如果出現(xiàn)沖突，應用旋轉優(yōu)先原則調整沖突；如果是LR型或RL型，則需應用扁擔原理旋轉兩次，第一次最小不平衡子樹的根結點先不動，調整插入結點所在子樹，第二次再調整最小不平衡子樹，在旋轉過程中，如果出現(xiàn)沖突，應用旋轉優(yōu)先原則調整沖突； ⑸ 計算調整后的平衡二叉樹中各結點的平衡因子，檢驗是否因為旋轉而破壞其他結點的平衡因子，以及調整后的平衡二叉樹中是否存在平衡因子大于1的結點。 三． 詳細設計 樹的內部變量 typedef struct BTNode { — 2 — int data;int bf;//平衡因子 struct BTNode *lchild,*rchild;//左、右孩子 }BTNode,*BTree;調平二叉樹(左右調平方式大體雷同，之具體寫出其中一種調平方式)if(插入元素與當前根元素相等){ printf(“已存在相同關鍵字的結點n”);} if(插入元素小于當前根元素)){ if(插入新結點不成功) return 0;if(插入成功) switch(查看根的平衡因子) { case +1: 進行左平衡處理; { 檢查*T的左子樹的平衡度，并作相應平衡處理 { case +1: 令根及其左孩子的平衡因子為0; 做右平衡處理; { BTree lc; lc指向的結點左子樹根結點; rc的右子樹掛接為結點的左子樹; lc的右孩子為原結點; 原結點指向新的結點lc; } break; case-1: rd指向*T的左孩子的右子樹根 switch(查看右孩子平衡因子) { case +1: 根的平衡因子為-1; 根左孩子的平衡因子為0; break; case 0: 令根和根左孩子的平衡因子為0; break; case-1: } } } } 根平衡因子為0;根左孩子平衡因子為1;break; 根右孩子的平衡因子為0;對*T的左子樹作左旋平衡處理;對*T作右旋平衡處理;break;令根的平衡因子為+1;break;令根的平衡因子為-1;break;case 0: case-1: 四．調試分析 在進行對插入新結點并調平時由于利用的是普通的插入方法進行LL、LR、RL、RR型的轉換，使得在調試時經(jīng)常沒有更改內部變量的值，導致編譯出錯。 對于在空樹情況下刪除結點的考慮，是在后期的調試檢驗過程中發(fā)現(xiàn)的。在沒有更改代碼前，如果按此操作，程序就會崩潰。原因就是在刪除函數(shù)中雖然考慮到了空樹的情況，但是在輸出樹的函數(shù)中沒有加入空樹的考慮而只是在創(chuàng)建樹函數(shù)中加入了if…else…的判斷。經(jīng)過反復的檢查，發(fā)現(xiàn)可以直接在輸出函數(shù)中加入判斷而不必再其他位置判斷，并且調試成功。 五．使用說明和測試結果 測試數(shù)據(jù)： 創(chuàng)建二叉樹 — 4 — 增加二叉樹 直接創(chuàng)建平衡二叉樹 平衡二叉樹加入新節(jié)點并調平 刪除結點 — 6 — 六．心得體會 了解了建立樹的方法； 學會了利用二分法建立樹結構。、； 學習到了二叉樹的調平方法； 學會了向一個已知樹插入或刪除結點的方法。七．附錄 源代碼 #include “stdafx.h” #include }BTNode,*BTree; /*需要的函數(shù)聲明*/ void Right_Balance(BTree &p);void Left_Balance(BTree &p);void Left_Root_Balance(BTree &T);void Right_Root_Balance(BTree &T);bool InsertAVL(BTree &T,int i,bool &taller);void PrintBT(BTree T,int m);void CreatBT(BTree &T);void Left_Root_Balance_det(BTree &p,int &shorter);void Right_Root_Balance_det(BTree &p,int &shorter);void Delete(BTree q,BTree &r,int &shorter);int DeleteAVL(BTree &p,int x,int &shorter);void Adj_balance(BTree &T);bool SetAVL(BTree &T,int i,bool &taller);bool Insert_Balance_AVL(BTree &T,int i,bool &taller);/*主函數(shù)*/ void main(){ int input,search,m;bool taller=false;int shorter=0;BTree T;T=(BTree)malloc(sizeof(BTNode));T=NULL;while(1){ printf(“n請選擇需要的二叉樹操作n”);printf(“1.創(chuàng)建二叉樹2.增加新結點3.直接創(chuàng)建平衡二叉樹4.在平衡二叉樹上增加新結點并調平衡5.scanf(”%d“,&input);getchar();switch(input){ case 1: CreatBT(T);break;printf(”請輸入你要增加的關鍵字“);scanf(”%d“,&search);getchar();InsertAVL(T,search,taller);m = 0;PrintBT(T,m);break;Adj_balance(T);刪除0.退出n”);case 2: case 3: — 8 — break; case 4: printf(“請輸入你要增加的關鍵字”); scanf(“%d”,&search); getchar(); SetAVL(T,search,taller); m = 0; PrintBT(T,m); break; case 5: printf(“請輸入你要刪除的關鍵字”); scanf(“%d”,&search); getchar(); DeleteAVL(T,search,shorter); m=0; PrintBT(T,m); break; case 0: break; default: printf(“輸入錯誤，請重新選擇?！?; break; } if(input == 0) break; printf(“按任意鍵繼續(xù).”); getchar();} } /*對以*p為根的二叉排序樹作右旋處理*/ void Right_Balance(BTree &p){ BTree lc;lc = p->lchild;//lc指向的*p左子樹根結點 p->lchild = lc->rchild;//rc的右子樹掛接為*p的左子樹 lc->rchild = p;p = lc;//p指向新的結點 } /*對以*p為根的二叉排序樹作左旋處理*/ void Left_Balance(BTree &p){ BTree rc;rc = p->rchild;//指向的*p右子樹根結點 p->rchild = rc->lchild;//rc左子樹掛接到*p的右子樹 rc->lchild = p;p = rc;//p指向新的結點 — 9 — } /*對以指針T所指結點為根的二叉樹作左平衡旋轉處理*/ void Left_Root_Balance(BTree &T){ } /*對以指針T所指結點為根的二叉樹作右平衡旋轉處理*/ void Right_Root_Balance(BTree &T){ BTree rc,ld;rc = T->rchild;//指向*T的左子樹根結點 switch(rc->bf)//檢查*T的右子樹的平衡度，并作相應平衡處理 { case RH: //新結點插入在*T的右孩子的右子樹上，要作單左旋處理 T->bf = rc->bf =EH;Left_Balance(T);break;ld = rc->lchild;//ld指向*T的右孩子的左子樹根 switch(ld->bf)//修改*T及其右孩子的平衡因子 BTree lc,rd;lc = T->lchild;//指向*T的左子樹根結點 switch(lc->bf)//檢查*T的左子樹的平衡度，并作相應平衡處理 { case LH: //新結點插入在*T的左孩子的左子樹上，要作單右旋處理 } T->bf = lc->bf = EH;Right_Balance(T);break;rd = lc->rchild;//rd指向*T的左孩子的右子樹根 switch(rd->bf)//修改*T及其左孩子的平衡因子 { case LH: } rd->bf = EH;Left_Balance(T->lchild);//對*T的左子樹作左旋平衡處理 Right_Balance(T);//對*T作右旋平衡處理 T->bf = RH;lc->bf = EH;break;T->bf = lc->bf = EH;break;T->bf = EH;lc->bf = LH;break;case RH: //新結點插入在*T的左孩子的右子樹上，要作雙旋處理 case EH: case RH: case LH: //新結點插入在*T的右孩子的左子樹上，要作雙旋處理 — 10 — } } { case LH: } ld->bf = EH;Right_Balance(T->rchild);//對*T的右子樹作左旋平衡處理 Left_Balance(T);//對*T作左旋平衡處理 T->bf = EH;rc->bf = RH;break;T->bf = rc->bf =EH;break;T->bf = LH;rc->bf = EH;break;case EH: case RH: /*插入結點i,若T中存在和i相同關鍵字的結點，則插入一個數(shù)據(jù)元素為i的新結點，并返回１，否則返回０*/ bool InsertAVL(BTree &T,int i,bool &taller){ if(!T)//插入新結點，樹“長高”，置taller為true { } else { if(EQ(i,T->data))//樹中已存在和有相同關鍵字的結點 { } if(LT(i,T->data))//應繼續(xù)在*T的左子樹中進行搜索 taller = false;printf(“已存在相同關鍵字的結點n”);return 0;T =(BTree)malloc(sizeof(BTNode));T->data = i;T->lchild = T->rchild =NULL;T->bf = EH;taller = true;{ if(!InsertAVL(T->lchild,i,taller))return 0;} else //應繼續(xù)在*T的右子樹中進行搜索 { if(!InsertAVL(T->rchild,i,taller))return 0; — 11 — } } return 1;} /*按樹狀打印輸出二叉樹的元素,m表示結點所在層次*/ void PrintBT(BTree T,int m){ } /*創(chuàng)建二叉樹，以輸入-32767為建立的結束*/ void CreatBT(BTree &T){ } int m;int i;bool taller=false;T = NULL;printf(“n請輸入關鍵字(以-32767結束建立二叉樹):”);scanf(“%i”,&i);getchar();while(i!=-32767){ } m=0;printf(“您創(chuàng)建的二叉樹為：n”);PrintBT(T,m);InsertAVL(T,i,taller);printf(“n請輸入關鍵字(以-32767結束建立二叉樹):”);scanf(“%i”,&i);getchar();taller=false;if(T){ } else { } printf(“這是一棵空樹！n”);getchar();int i;if(T->rchild)PrintBT(T->rchild,m+1);printf(“ ”);//打印i 個空格以表示出層次 for(i = 1;i<=m;i++)printf(“%dn”,T->data);//打印T 元素,換行 if(T->lchild)PrintBT(T->lchild,m+1);— 12 — /*刪除結點時左平衡旋轉處理*/ void Left_Root_Balance_det(BTree &p,int &shorter){ BTree p1,p2;if(p->bf==1)//p結點的左子樹高，刪除結點后p的bf減,樹變矮 { } else if(p->bf==0)//p結點左、右子樹等高，刪除結點后p的bf減,樹高不變 { } else //p結點的右子樹高 { p1=p->rchild;//p1指向p的右子樹 if(p1->bf==0)//p1結點左、右子樹等高,刪除結點后p的bf為-2,進行左旋處理，樹高不變 { } else if(p1->bf==-1)//p1的右子樹高，左旋處理后，樹變矮 { } else //p1的左子樹高,進行雙旋處理(先右旋后左旋)，樹變矮 { p2=p1->lchild;p1->lchild=p2->rchild;p2->rchild=p1;p->rchild=p2->lchild;p2->lchild=p;if(p2->bf==0){ } else if(p2->bf==-1){ p->bf=1;p1->bf=0;p->bf=0;p1->bf=0;Left_Balance(p);p1->bf=p->bf=0;shorter=1;Left_Balance(p);p1->bf=1;p->bf=-1;shorter=0;p->bf=-1;shorter=0;p->bf=0;shorter=1; } } } } else { } p2->bf=0;p=p2;shorter=1;p->bf=0;p1->bf=-1;/*刪除結點時右平衡旋轉處理*/ void Right_Root_Balance_det(BTree &p,int &shorter){ BTree p1,p2;if(p->bf==-1){ } else if(p->bf==0){ } else { p1=p->lchild;if(p1->bf==0){ } else if(p1->bf==1){ } else { p2=p1->rchild;Right_Balance(p);p1->bf=p->bf=0;shorter=1;Right_Balance(p);p1->bf=-1;p->bf=1;shorter=0;p->bf=1;shorter=0;p->bf=0;shorter=1;— 14 — p1->rchild=p2->lchild; p2->lchild=p1; p->lchild=p2->rchild; p2->rchild=p; if(p2->bf==0) { p->bf=0; p1->bf=0; } else if(p2->bf==1) { p->bf=-1; p1->bf=0; } else { p->bf=0; p1->bf=1; } p2->bf=0; p=p2; shorter=1; } } } /*刪除結點*/ void Delete(BTree q,BTree &r,int &shorter){ if(r->rchild==NULL){ q->data=r->data; q=r; r=r->lchild; free(q); shorter=1;} else { Delete(q,r->rchild,shorter); if(shorter==1) Right_Root_Balance_det(r,shorter);} } /*二叉樹的刪除操作*/ int DeleteAVL(BTree &p,int x,int &shorter){ } int k;BTree q;if(p==NULL){ } else if(x data)//在p的左子樹中進行刪除 { } else if(x>p->data)//在p的右子樹中進行刪除 { } else { } q=p;if(p->rchild==NULL)//右子樹空則只需重接它的左子樹 { } else if(p->lchild==NULL)//左子樹空則只需重接它的右子樹 { } else//左右子樹均不空 { } return 1;Delete(q,q->lchild,shorter);if(shorter==1)Left_Root_Balance_det(p,shorter);p=q;p=p->rchild;free(q);shorter=1;p=p->lchild;free(q);shorter=1;k=DeleteAVL(p->rchild,x,shorter);if(shorter==1)Right_Root_Balance_det(p,shorter);return k;k=DeleteAVL(p->lchild,x,shorter);if(shorter==1)Left_Root_Balance_det(p,shorter);return k;printf(“不存在要刪除的關鍵字！n”);return 0;— 16 — /*二叉樹調平操作*/ void Adj_balance(BTree &T){ int m;int i;bool taller=false;T = NULL;printf(“n請輸入關鍵字(以-32767結束建立平衡二叉樹):”);scanf(“%d”,&i);getchar();while(i!=-32767){ SetAVL(T,i,taller); printf(“n請輸入關鍵字(以-32767結束建立平衡二叉樹):”); scanf(“%d”,&i); getchar(); taller=false;} m=0;printf(“平衡二叉樹創(chuàng)建結束.n”);if(T) PrintBT(T,m);else printf(“這是一棵空樹.n”);} /*調平二叉樹具體方法*/ bool SetAVL(BTree &T,int i,bool &taller){ if(!T)//插入新結點，樹“長高”，置taller為true { T =(BTree)malloc(sizeof(BTNode)); T->data = i; T->lchild = T->rchild =NULL; T->bf = EH; taller = true;} else { if(EQ(i,T->data))//樹中已存在和有相同關鍵字的結點 { taller = false; printf(“已存在相同關鍵字的結點n”); return 0; } if(LT(i,T->data))//應繼續(xù)在*T的左子樹中進行搜索 { } } } if(!SetAVL(T->lchild,i,taller)) { } case LH: //原本左子樹比右子樹高，需要作左平衡處理 Left_Root_Balance(T);taller = false;break;T->bf = LH;taller = true;break;T->bf = EH;taller = false;break;return 0;switch(T->bf)//檢查*T的平衡度 if(taller)//已插入到*T的左子樹中且左子樹“長高” case EH: //原本左子樹、右子等高，現(xiàn)因左子樹增高而使樹增高 case RH: //原本右子樹比左子樹高，現(xiàn)左、右子樹等高 else //應繼續(xù)在*T的右子樹中進行搜索 { } return 1;if(!SetAVL(T->rchild,i,taller)) { } case LH: //原本左子樹比右子樹高，現(xiàn)左、右子樹等高 T->bf = EH;taller = false;break;T->bf = RH;taller = true;break;Right_Root_Balance(T);taller = false;break;return 0;switch(T->bf)//檢查*T的平衡度 if(taller)//已插入到*T的右子樹中且右子樹“長高” case EH: //原本左子樹、右子等高，現(xiàn)因右子樹增高而使樹增高 case RH: //原本右子樹比左子樹高，需要作右平衡處理 — 18 — 實驗報告 課程名：數(shù)據(jù)結構（C語言版）實驗名：二叉樹的遍歷 姓名： 班級： 學號： 時間：2014.11.03 一 實驗目的與要求 1.掌握二叉樹的存儲方法 2.掌握二叉樹的三種遍歷方法 3.實現(xiàn)二叉樹的三種遍歷方法中的一種 二 實驗內容 ? 接受用戶輸入一株二叉樹 ? 輸出這株二叉樹的前根, 中根, 后根遍歷中任意一種的順序 三 實驗結果與分析 //*********************************************************** //頭文件 #include #define OK 1 #define ERROR 0 #define OVERFLOW 0 //*********************************************************** typedef struct BiTNode { //二叉樹二叉鏈表存儲結構 char data;struct BiTNode *lChild,*rChild;}BiTNode,*BiTree;//*********************************************************** int CreateBiTree(BiTree &T){ //按先序次序輸入二叉中樹結點的值，空格表示空樹 //構造二叉鏈表表示的二叉樹T char ch;fflush(stdin);scanf(“%c”,&ch);if(ch==' ')T=NULL;else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))return(OVERFLOW);T->data=ch;CreateBiTree(T->lChild);CreateBiTree(T->rChild);} return(OK);} //********************************************************* void PreOrderTraverse(BiTree T){ //采用二叉鏈表存儲結構，先序遍歷二叉樹的遞歸算法 if(T){ printf(“%c”,T->data);PreOrderTraverse(T->lChild);PreOrderTraverse(T->rChild);} } /***********************************************************/ void InOrderTraverse(BiTree T){ //采用二叉鏈表存儲結構，中序遍歷二叉樹的遞歸算法 if(T){ InOrderTraverse(T->lChild);printf(“%c”,T->data);InOrderTraverse(T->rChild);} } //*********************************************************** void PostOrderTraverse(BiTree T){ //采用二叉鏈表存儲結構，后序遍歷二叉樹的遞歸算法 if(T){ PostOrderTraverse(T->lChild);PostOrderTraverse(T->rChild);printf(“%c”,T->data);} } //*********************************************************** void main(){ //主函數(shù)分別實現(xiàn)建立并輸出先、中、后序遍歷二叉樹 printf(“please input your tree follow the PreOrder:n”);BiTNode *Tree;CreateBiTree(Tree);printf(“n先序遍歷二叉樹:”);PreOrderTraverse(Tree);printf(“n中序遍歷二叉樹:”);InOrderTraverse(Tree);printf(“n后序遍歷二叉樹:”);PostOrderTraverse(Tree);} 圖1:二叉樹的遍歷運行結果 課 程 設 計 報 告 一． 需求分析 1、建立平衡二叉樹并進行創(chuàng)建、增加、刪除、調平等操作。 2、設計一個實現(xiàn)平衡二叉樹的程序，可進行創(chuàng)建、增加、刪除、調平等操作，實現(xiàn)動態(tài)的輸入數(shù)據(jù)，實時的輸出該樹結構。 3、測試數(shù)據(jù)：自選數(shù)據(jù) 二． 概要設計 平衡二叉樹是在構造二叉排序樹的過程中，每當插入一個新結點時，首先檢查是否因插入新結點而破壞了二叉排序樹的平衡性，若是，則找出其中的最小不平衡子樹，在保持二叉排序樹特性的前提下，調整最小不平衡子樹中各結點之間的鏈接關系，進行相應的旋轉，使之成為新的平衡子樹。具體步驟如下： ⑴ 每當插入一個新結點，從該結點開始向上計算各結點的平衡因子，即計算該結點的祖先結點的平衡因子，若該結點的祖先結點的平衡因子的絕對值均不超過1，則平衡二叉樹沒有失去平衡，繼續(xù)插入結點； ⑵ 若插入結點的某祖先結點的平衡因子的絕對值大于1，則找出其中最小不平衡子樹的根結點； ⑶ 判斷新插入的結點與最小不平衡子樹的根結點的關系，確定是哪種類型的調整； ⑷ 如果是LL型或RR型，只需應用扁擔原理旋轉一次，在旋轉過程中，如果出現(xiàn)沖突，應用旋轉優(yōu)先原則調整沖突；如果是LR型或RL型，則需應用扁擔原理旋轉兩次，第一次最小不平衡子樹的根結點先不動，調整插入結點所在子樹，第二次再調整最小不平衡子樹，在旋轉過程中，如果出現(xiàn)沖突，應用旋轉優(yōu)先原則調整沖突； ⑸ 計算調整后的平衡二叉樹中各結點的平衡因子，檢驗是否因為旋轉而破壞其他結點的平衡因子，以及調整后的平衡二叉樹中是否存在平衡因子大于1的結點。 三． 詳細設計 樹的內部變量 — 1 — typedef struct BTNode { int data;int bf;//平衡因子 struct BTNode *lchild,*rchild;//左、右孩子 }BTNode,*BTree;調平二叉樹(左右調平方式大體雷同，之具體寫出其中一種調平方式)if(插入元素與當前根元素相等){ printf(“已存在相同關鍵字的結點n”);} if(插入元素小于當前根元素)){ if(插入新結點不成功) return 0;if(插入成功) switch(查看根的平衡因子) { case +1: 進行左平衡處理; { 檢查*T的左子樹的平衡度，并作相應平衡處理 { case +1: 令根及其左孩子的平衡因子為0; 做右平衡處理; { BTree lc; lc指向的結點左子樹根結點; rc的右子樹掛接為結點的左子樹; lc的右孩子為原結點; 原結點指向新的結點lc; } break; case-1: rd指向*T的左孩子的右子樹根 switch(查看右孩子平衡因子) { case +1: 根的平衡因子為-1; 根左孩子的平衡因子為0; break; case 0: 令根和根左孩子的平衡因子為0;— 2 — } } } } break;根平衡因子為0;根左孩子平衡因子為1;break; case-1: 根右孩子的平衡因子為0;對*T的左子樹作左旋平衡處理;對*T作右旋平衡處理;break;令根的平衡因子為+1;break;令根的平衡因子為-1;break;case 0: case-1: 四．調試分析 在進行對插入新結點并調平時由于利用的是普通的插入方法進行LL、LR、RL、RR型的轉換，使得在調試時經(jīng)常沒有更改內部變量的值，導致編譯出錯。 對于在空樹情況下刪除結點的考慮，是在后期的調試檢驗過程中發(fā)現(xiàn)的。在沒有更改代碼前，如果按此操作，程序就會崩潰。原因就是在刪除函數(shù)中雖然考慮到了空樹的情況，但是在輸出樹的函數(shù)中沒有加入空樹的考慮而只是在創(chuàng)建樹函數(shù)中加入了if…else…的判斷。經(jīng)過反復的檢查，發(fā)現(xiàn)可以直接在輸出函數(shù)中加入判斷而不必再其他位置判斷，并且調試成功。 五．使用說明和測試結果 測試數(shù)據(jù)： 創(chuàng)建二叉樹 增加二叉樹 直接創(chuàng)建平衡二叉樹 — 4 —平衡二叉樹加入新節(jié)點并調平 刪除結點 六．心得體會 了解了建立樹的方法； 學會了利用二分法建立樹結構。、； 學習到了二叉樹的調平方法； 學會了向一個已知樹插入或刪除結點的方法。 — 6 — 平衡二叉樹操作的演示 1.需求分析 本程序是利用平衡二叉樹，實現(xiàn)動態(tài)查找表的基本功能：創(chuàng)建表，查找、插入、刪除。具體功能： （1）初始，平衡二叉樹為空樹，操作界面給出創(chuàng)建、查找、插入、刪除、合并、分裂六種操作供選擇。每種操作均提示輸入關鍵字。每次插入或刪除一個結點后，更新平衡二叉樹的顯示。 （2）平衡二叉樹的顯示采用凹入表現(xiàn)形式。（3）合并兩棵平衡二叉樹。 （4）把一棵二叉樹分裂為兩棵平衡二叉樹，使得在一棵樹中的所有關鍵字都小于或等于x，另一棵樹中的任一關鍵字都大于x。 如下圖： 2．概要設計 平衡二叉樹是在構造二叉排序樹的過程中，每當插入一個新結點時，首先檢查是否因插入新結點而破壞了二叉排序樹的平衡性，若是則找出其中的最小不平衡子樹，在保持二叉排序樹特性的前提下，調整最小不平衡子樹中各結點之間的鏈接關系，進行相應的旋轉，使之成為新的平衡子樹。具體步驟： （1）每當插入一個新結點，從該結點開始向上計算各結點的平衡因子，即計算該結點的祖先結點的平衡因子，若該結點的祖先結點的平衡因子的絕對值不超過1，則平衡二叉樹沒有失去平衡，繼續(xù)插入結點； （2）若插入結點的某祖先結點的平衡因子的絕對值大于1，則找出其中最小不平衡子樹的根結點； （3）判斷新插入的結點與最小不平衡子樹的根結點個關系，確定是那種類型的調整；（4）如果是LL型或RR型，只需應用扁擔原理旋轉一次，在旋轉過程中，如果出現(xiàn)沖突，應用旋轉優(yōu)先原則調整沖突；如果是LR型或RL型，則需應用扁擔原理旋轉兩次，第一次最小不平衡子樹的根結點先不動，調整插入結點所在子樹，第二次再調整最小不平衡子樹，在旋轉過程中，如果出現(xiàn)沖突，應用旋轉優(yōu)先原則調整沖突； （5）計算調整后的平衡二叉樹中各結點的平衡因子，檢驗是否因為旋轉而破壞其他結點的平衡因子，以及調整后平衡二叉樹中是否存在平衡因子大于1的結點。流程圖 3.詳細設計 二叉樹類型定義： typedefint Status;typedefintElemType;typedefstructBSTNode{ ElemType data; int bf; structBSTNode *lchild ,*rchild;} BSTNode,* BSTree; Status SearchBST(BSTreeT,ElemType e)//查找 void R_Rotate(BSTree&p)//右旋 void L_Rotate(BSTree&p)//左旋 void LeftBalance(BSTree&T)//插入平衡調整 void RightBalance(BSTree&T)//插入平衡調整 Status InsertAVL(BSTree&T,ElemTypee,int&taller)//插入 void DELeftBalance(BSTree&T)//刪除平衡調整 void DERightBalance(BSTree&T)//刪除平衡調整 Status Delete(BSTree&T,int&shorter)//刪除操作 Status DeleteAVL(BSTree&T,ElemTypee,int&shorter)//刪除操作 void merge(BSTree&T1,BSTree &T2)//合并操作 void splitBSTree(BSTreeT,ElemTypee,BSTree&T1,BSTree &T2)//分裂操作 void PrintBSTree(BSTree&T,intlev)//凹入表顯示 附錄 源代碼： #include structBSTNode *lchild ,*rchild;//左、右孩子指針 } BSTNode,* BSTree;/* 查找算法 */ Status SearchBST(BSTreeT,ElemType e){ if(!T){ return 0;//查找失敗 } else if(e == T->data){ return 1;//查找成功 } else if(e < T->data){ returnSearchBST(T->lchild,e);} else{ returnSearchBST(T->rchild,e);} } //右旋 voidR_Rotate(BSTree&p){ BSTreelc;//處理之前的左子樹根結點 lc = p->lchild;//lc指向的*p的左子樹根結點 p->lchild = lc->rchild;//lc的右子樹掛接為*P的左子樹 lc->rchild = p;p = lc;//p指向新的根結點 } //左旋 voidL_Rotate(BSTree&p){ BSTreerc;rc = p->rchild;//rc指向的*p的右子樹根結點 p->rchild = rc->lchild;//rc的左子樹掛接為*p的右子樹 rc->lchild = p;p = rc;//p指向新的根結點 } //對以指針T所指結點為根結點的二叉樹作左平衡旋轉處理，//本算法結束時指針T指向新的根結點 voidLeftBalance(BSTree&T){ BSTreelc,rd;lc=T->lchild;//lc指向*T的左子樹根結點 switch(lc->bf){ //檢查*T的左子樹的平衡度，并做相應的平衡處理 case LH: //新結點插入在*T的左孩子的左子樹，要做單右旋處理 T->bf = lc->bf=EH;R_Rotate(T);break;case RH: //新結點插入在*T的左孩子的右子樹上，做雙旋處理 rd=lc->rchild;//rd指向*T的左孩子的右子樹根 switch(rd->bf){ //修改*T及其左孩子的平衡因子 case LH: T->bf=RH;lc->bf=EH;break;case EH: T->bf=lc->bf=EH;break;case RH: T->bf=EH;lc->bf=LH;break;} rd->bf=EH;L_Rotate(T->lchild);//對*T的左子樹作左旋平衡處理 R_Rotate(T);//對*T作右旋平衡處理 } } //右平衡旋轉處理 voidRightBalance(BSTree&T){ BSTreerc,ld;rc=T->rchild;switch(rc->bf){ case RH: T->bf= rc->bf=EH;L_Rotate(T);break;case LH: ld=rc->lchild;switch(ld->bf){ case LH: T->bf=RH;rc->bf=EH;break;case EH: T->bf=rc->bf=EH;break;case RH: T->bf = EH;rc->bf=LH;break;} ld->bf=EH;R_Rotate(T->rchild);L_Rotate(T);} } //插入結點 Status InsertAVL(BSTree&T,ElemTypee,int&taller){//taller反應T長高與否 if(!T){//插入新結點，樹長高，置taller為true T=(BSTree)malloc(sizeof(BSTNode));T->data = e;T->lchild = T->rchild = NULL;T->bf = EH;taller = 1;} else{ if(e == T->data){ taller = 0;return 0;} if(e < T->data){ if(!InsertAVL(T->lchild,e,taller))//未插入 return 0;if(taller)//已插入到*T的左子樹中且左子樹長高 switch(T->bf){//檢查*T的平衡度，作相應的平衡處理 case LH: LeftBalance(T);taller = 0;break;case EH: T->bf = LH;taller = 1;break;case RH: T->bf = EH;taller = 0;break;} } else{ if(!InsertAVL(T->rchild,e,taller)){ return 0;} if(taller)//插入到*T的右子樹且右子樹增高 switch(T->bf){//檢查*T的平衡度 case LH: T->bf = EH;taller = 0;break;case EH: T->bf = RH;taller = 1;break;case RH: RightBalance(T);taller = 0;break;} } } return 1;} void DELeftBalance(BSTree&T){//刪除平衡調整 BSTreelc,rd;lc=T->lchild;switch(lc->bf){ case LH: T->bf = EH;//lc->bf= EH;R_Rotate(T);break;case EH: T->bf = EH;lc->bf= EH;R_Rotate(T);break;case RH: rd=lc->rchild;switch(rd->bf){ case LH: T->bf=RH;lc->bf=EH;break;case EH: T->bf=lc->bf=EH;break;case RH: T->bf=EH;lc->bf=LH;break;} rd->bf=EH;L_Rotate(T->lchild);R_Rotate(T);} } void DERightBalance(BSTree&T)//刪除平衡調整 { BSTreerc,ld;rc=T->rchild;switch(rc->bf){ case RH: T->bf= EH;//rc->bf= EH;L_Rotate(T);break;case EH: T->bf= EH;//rc->bf= EH;L_Rotate(T);break;case LH: ld=rc->lchild;switch(ld->bf){ case LH: T->bf=RH;rc->bf=EH;break;case EH: T->bf=rc->bf=EH;break;case RH: T->bf = EH;rc->bf=LH;break;} ld->bf=EH;R_Rotate(T->rchild);L_Rotate(T);} } voidSDelete(BSTree&T,BSTree&q,BSTree&s,int&shorter){ if(s->rchild){ SDelete(T,s,s->rchild,shorter);if(shorter)switch(s->bf){ case EH: s->bf = LH;shorter = 0;break;case RH: s->bf = EH;shorter = 1;break;case LH: DELeftBalance(s);shorter = 0;break;} return;} T->data = s->data;if(q!= T)q->rchild = s->lchild;else q->lchild = s->lchild;shorter = 1;} //刪除結點 Status Delete(BSTree&T,int&shorter){ BSTree q;if(!T->rchild){ q = T;T = T->lchild;free(q);shorter = 1;} else if(!T->lchild){ q = T;T= T->rchild;free(q);shorter = 1;} else{ SDelete(T,T,T->lchild,shorter);if(shorter)switch(T->bf){ case EH: T->bf = RH;shorter = 0;break;case LH: T->bf = EH;shorter = 1;break;case RH: DERightBalance(T);shorter = 0;break;} } return 1;} Status DeleteAVL(BSTree&T,ElemTypee,int&shorter){ int sign = 0;if(!T){ return sign;} else{ if(e == T->data){ sign = Delete(T,shorter);return sign;} else if(e < T->data){ sign = DeleteAVL(T->lchild,e,shorter);if(shorter)switch(T->bf){ case EH: T->bf = RH;shorter = 0;break;case LH: T->bf = EH;shorter = 1;break;case RH: DERightBalance(T);shorter = 0;break;} return sign;} else{ sign = DeleteAVL(T->rchild,e,shorter);if(shorter)switch(T->bf){ case EH: T->bf = LH;shorter = 0;break;case RH: T->bf = EH;break;case LH: DELeftBalance(T);shorter = 0;break;} return sign;} } } //合并 void merge(BSTree&T1,BSTree &T2){ int taller = 0;if(!T2)return;merge(T1,T2->lchild);InsertAVL(T1,T2->data,taller);merge(T1,T2->rchild);} //分裂 void split(BSTreeT,ElemTypee,BSTree&T1,BSTree &T2){ int taller = 0;if(!T)return;split(T->lchild,e,T1,T2);if(T->data > e)InsertAVL(T2,T->data,taller);else InsertAVL(T1,T->data,taller);split(T->rchild,e,T1,T2);} //分裂 voidsplitBSTree(BSTreeT,ElemTypee,BSTree&T1,BSTree &T2){ BSTree t1 = NULL,t2 = NULL;split(T,e,t1,t2);T1 = t1;T2 = t2;return;} //構建 voidCreatBSTree(BSTree&T){ intnum,i,e,taller = 0;printf(“輸入結點個數(shù):”);scanf(“%d”,&num);printf(“請順序輸入結點值n”);for(i = 0;i voidPrintBSTree(BSTree&T,intlev){ int i;if(T->rchild)PrintBSTree(T->rchild,lev+1);for(i = 0;i intcho,taller,e,k;taller = 0;k = 0;while(1){ system(“cls”);printf(“平衡二叉樹操作的演示 nn”);printf(“********************************n”);printf(“平衡二叉樹顯示區(qū) n”);printf(“T1樹n”);if(!T1)printf(“n 當前為空樹n”);else{ PrintBSTree(T1,1);} printf(“T2樹n”);if(!T2)printf(“n 當前為空樹n”);else PrintBSTree(T2,1);printf(“n******************************************************************************n”);printf(“T1操作：1.創(chuàng)建 2.插入 3.查找 4.刪除 10.分裂n”);printf(“T2操作：5.創(chuàng)建 6.插入 7.查找 8.刪除 11.分裂n”);printf(“ 9.合并 T1,T2 0.退出n”);printf(“******************************************************************************n”);printf(“輸入你要進行的操作：”);scanf(“%d”,&cho);switch(cho){ case 1: CreatBSTree(T1);break;case 2: printf(“請輸入要插入關鍵字的值”);scanf(“%d”,&e);InsertAVL(T1,e,taller);break;case 3: printf(“請輸入要查找關鍵字的值”);scanf(“%d”,&e); if(SearchBST(T1,e))printf(“查找成功！n”);else printf(“查找失??！n”);printf(“按任意鍵返回87”);getchar();getchar();break;case 4: printf(“請輸入要刪除關鍵字的值”);scanf(“%d”,&e);if(DeleteAVL(T1,e,k))printf(“刪除成功！n”);else printf(“刪除失??！n”);printf(“按任意鍵返回”);getchar();getchar();break;case 5: CreatBSTree(T2);break;case 6: printf(“請輸入要插入關鍵字的值”);scanf(“%d”,&e);InsertAVL(T2,e,taller);break;case 7: printf(“請輸入要查找關鍵字的值”);scanf(“%d”,&e); if(SearchBST(T2,e))printf(“查找成功！n”);else printf(“查找失??！n”);printf(“按任意鍵返回”);getchar();getchar();break;case 8: printf(“請輸入要刪除關鍵字的值”);scanf(“%d”,&e);if(DeleteAVL(T2,e,k))printf(“刪除成功！n”);else printf(“刪除失?。”);printf(“按任意鍵返回”);getchar();getchar();break;case 9: merge(T1,T2);T2 = NULL;printf(“合并成功，按任意鍵返回”);getchar();getchar();break;case 10: printf(“請輸入要中間值字的值”);scanf(“%d”,&e);splitBSTree(T1,e,T1,T2);printf(“分裂成功，按任意鍵返回”);getchar();getchar();break;case 11: printf(“請輸入要中間值字的值”);scanf(“%d”,&e);splitBSTree(T2,e,T1,T2);printf(“分裂成功，按任意鍵返回”);getchar();getchar();break;case 0: system(“cls”);exit(0);} } } main(){ BSTree T1 = NULL;BSTree T2 = NULL;Start(T1,T2);}第二篇：數(shù)據(jù)結構課程設計-平衡二叉樹操作
第三篇：數(shù)據(jù)結構-二叉樹的遍歷實驗報告
第四篇：數(shù)據(jù)結構課程設計-_平衡二叉樹操作 - 副本
第五篇：數(shù)據(jù)結構平衡二叉樹的操作演示
點擊咨詢 