第一篇：數據結構課程設計二叉樹平衡的判定

數據結構與算法 課程設計報告

課程設計題目： 二叉樹平衡的判定

專業班級： 信息與計算科學1001班 姓 名： 謝煒 學 號：100701114 設計室號： 理學院機房 設計時間： 2011-12-26 批閱時間： 指導教師： 杜洪波 成 績：

一、摘要：

基于我們對C語言和數據結構的學習我們有能力編寫處理一些比較基本而又簡單的問題。在我們此題我們的目標就是任意給出一個二叉樹我們判斷是否為平衡的二叉樹。

我們在學習計算機語言類的知識時當然要注重理論知識的學習，但是我們要明確我們學習的是計算機語言，由于課程的性質就決定了我們必須將我們在課本中學到的知識在計算機上運行并且自己能編寫一些比較簡單的程序，這才是我們學習計算機語言的最終目的而不是滿足于理解一個理論會算一個題。因而我們將要抓住這樣一個鍛煉的機會

所謂平衡二叉樹，它或者是一顆空樹或者是具有下列性質的二叉樹：它的左右子樹都是平衡二叉樹，且左右子樹的深度之差得絕對值不超過1。

在我們這個判定任意給定的二叉樹的題中。我們處理這道題的主要的思路是：首先按先序和中序或者按中序和后序的方式將我們所要判斷的二叉樹輸入進入，目的是要得到一個明確的二叉樹的結構準確的判斷二叉樹是否平衡。在我們判斷二叉樹的平衡中我們將分別考慮二叉樹左右子樹的是不是為平衡二叉樹，依次得到左右子樹的深度，判斷左右子樹的平衡性。

在我們的設計思路中我們將用到不同的樹的遍歷方式。

二、問題重敘：

平衡二叉樹的判斷，設計要求給定一個先序或者后序的遍歷結果，判斷其是否為二叉樹。問題分析：

在處理二叉樹平衡的判斷的問題中。我們需要將分別考慮二叉樹的左右子樹的平衡問題只要左右子樹確定為平衡二叉樹，而且左右子樹的深度的絕對值之差不大于1，那么我們得到的就是一顆平衡的二叉樹。

我們將先通過前序和中序或者中序和后序將所要判斷的二叉樹輸入。建立一個明確的二叉樹在此基礎上判斷二叉樹是否為平衡二叉樹。

我們先建立一個二叉樹并用前序和中序或者中序和后序遍歷的方式將我們輸入的樹的元素輸入得到一個明確的樹的結構。

三、流程圖如下：

四、模塊分析：

1、定義一個結構體存儲各節點的信息，并且用遞歸的方法存儲左右子樹的信息

typedef struct BINTREE { char

chData;struct BINTREE * pbLChild;struct BINTREE * pbRChild;} BinTree, * pBinTree;

2、分別得到樹的深度以及左右子樹的深度

int BT_GetTreeDepth(pBinTree pbTree){ //存儲樹總的深度

int iDepthTotal = 0;//存儲左子樹的深度

int iDepthLeft = 0;//存儲右子樹的深度

int iDepthRight = 0;

if(pbTree == NULL){

iDepthTotal = 0;} else {

// 左孩子的深度

iDepthLeft = BT_GetTreeDepth(pbTree->pbLChild);

// 右孩子的深度

iDepthRight = BT_GetTreeDepth(pbTree->pbRChild);

// 去左右孩子深度的最大值，1代表著根節點

iDepthTotal = 1 +(iDepthLeft > iDepthRight ? iDepthLeft : iDepthRight);} return iDepthTotal;}

3、判斷左右子樹是不是為平衡二叉樹

bool BT_IsBalanceTree(pBinTree pbTree){ //如果樹不是空的if(pbTree!= NULL){

//存儲左孩子的深度

int iLeftDepth = 0;

//存儲右孩子的深度

int iRightDepth = 0;

//得到左孩子的深度

iLeftDepth = BT_GetTreeDepth(pbTree->pbLChild);

//得到右孩子的深度

iRightDepth = BT_GetTreeDepth(pbTree->pbRChild);

//判斷樹是不是平衡二叉樹

平衡二叉樹的左右孩子的深度絕對值只差不大于

if((iLeftDepthiRightDepth <= 1))

{

// 判斷左子樹是不是平衡的

BT_IsBalanceTree(pbTree->pbLChild);

//判斷右子樹是不是平衡的

BT_IsBalanceTree(pbTree->pbRChild);

}

else

{

return false;

} } else {

return false;}

return true;}

4、輸入各節點元素

bool BT_PreInToTree(pBinTree & pbTree, char * szInOrder, char * szPreOrder, int iInLeft, int iInRight, int iPreLeft, int iPreRight)

BT_PreInToTree(pbTree->pbLChild, szInOrder, szPreOrder, iInLeft, iCurPosiRightDepth >=-1)&&(iLeftDepthiInLeft;// If current position is greater than left, generate left child if(iCurPos > iInLeft){ BT_PreInToTree(pbTree->pbLChild, szInOrder, szPreOrder, iInLeft, iCurPosiInLeft;// If the current position is greater than the left border, generate the left child if(iCurPos > iInLeft){

BT_InPostToTree(pbTree->pbLChild, szInOrder, szPostOrder, iInLeft, iCurPos1);}

// If the current position is less than the right border, generate the right child if(iCurPos < iInRight){

BT_InPostToTree(pbTree->pbRChild, szInOrder, szPostOrder, iCurPos + 1, iInRight, iPostLeft + iLengthLeft, iPostRight-1);} return true;} void BT_PreOrder(pBinTree pbTree){ if(pbTree!= NULL){

// The preorder traversal is, root, left child, right child

printf(“%c ”, pbTree->chData);

BT_PreOrder(pbTree->pbLChild);

BT_PreOrder(pbTree->pbRChild);} } void BT_PostOrder(pBinTree pbTree){

if(pbTree!= NULL){

// The postorder traversal is, left child, right child, root

BT_PostOrder(pbTree->pbLChild);

BT_PostOrder(pbTree->pbRChild);

printf(“%c ”, pbTree->chData);} } void main(){ char szPre [100] = “";char szMid [100] = ”“;char szPost [100] = ”“;pBinTree pbPreInTree;pBinTree pbPostInTree;int

iMode = 0;printf(”請選擇生成二叉樹規則：前序和中序(0)，后序和中序(1)n“);scanf(”%d“,&iMode);switch(iMode){ case 0:

{

printf(”請輸入前序序列:n“);

scanf(”%s“,&szPre);printf(”請輸入中序序列:n“);

scanf(”%s“,&szMid);bool bCorrect = BT_PreInToTree(pbPreInTree, szMid, szPre, 0, strlen(szMid)-1, 0, strlen(szPre)-1);

if(bCorrect)

{printf(”該樹的后序序列為：n“);

BT_PostOrder(pbPreInTree);

if(BT_IsBalanceTree(pbPreInTree))

{printf(”該樹是平衡二叉樹“);

}

else

{printf(”這個不是平衡二叉樹“);

}

}

else

{printf(”不要亂輸，前序與中序不匹配“);} }

break;case 1:

{printf(”請輸入中序序列:n“);scanf(”%s“,&szMid);printf(”請輸入后序序列:n“);scanf(”%s“,&szPost);bool bCorrect = BT_InPostToTree(pbPostInTree, szMid, szPost, 0, strlen(szMid)-1, 0, strlen(szPost)-1);

if(bCorrect)

{printf(”該樹的前序序列為：n“);BT_PreOrder(pbPostInTree);

if(BT_IsBalanceTree(pbPostInTree))

{printf(”該樹是平衡二叉樹“);

}

else

{printf(”這個不是平衡二叉樹“);

}

}

else

{printf(”不要亂輸，中序與后序不匹配“);

} }

break;default:

{printf(”不要亂選，不支持其他模式");

} } }

第二篇：數據結構課程設計-_平衡二叉樹操作 - 副本

課 程 設 計 報 告

一． 需求分析

1、建立平衡二叉樹并進行創建、增加、刪除、調平等操作。

2、設計一個實現平衡二叉樹的程序，可進行創建、增加、刪除、調平等操作，實現動態的輸入數據，實時的輸出該樹結構。

3、測試數據：自選數據

二． 概要設計

平衡二叉樹是在構造二叉排序樹的過程中，每當插入一個新結點時，首先檢查是否因插入新結點而破壞了二叉排序樹的平衡性，若是，則找出其中的最小不平衡子樹，在保持二叉排序樹特性的前提下，調整最小不平衡子樹中各結點之間的鏈接關系，進行相應的旋轉，使之成為新的平衡子樹。具體步驟如下：

⑴ 每當插入一個新結點，從該結點開始向上計算各結點的平衡因子，即計算該結點的祖先結點的平衡因子，若該結點的祖先結點的平衡因子的絕對值均不超過1，則平衡二叉樹沒有失去平衡，繼續插入結點；

⑵ 若插入結點的某祖先結點的平衡因子的絕對值大于1，則找出其中最小不平衡子樹的根結點；

⑶ 判斷新插入的結點與最小不平衡子樹的根結點的關系，確定是哪種類型的調整；

⑷ 如果是LL型或RR型，只需應用扁擔原理旋轉一次，在旋轉過程中，如果出現沖突，應用旋轉優先原則調整沖突；如果是LR型或RL型，則需應用扁擔原理旋轉兩次，第一次最小不平衡子樹的根結點先不動，調整插入結點所在子樹，第二次再調整最小不平衡子樹，在旋轉過程中，如果出現沖突，應用旋轉優先原則調整沖突；

⑸ 計算調整后的平衡二叉樹中各結點的平衡因子，檢驗是否因為旋轉而破壞其他結點的平衡因子，以及調整后的平衡二叉樹中是否存在平衡因子大于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型的轉換，使得在調試時經常沒有更改內部變量的值，導致編譯出錯。

對于在空樹情況下刪除結點的考慮，是在后期的調試檢驗過程中發現的。在沒有更改代碼前，如果按此操作，程序就會崩潰。原因就是在刪除函數中雖然考慮到了空樹的情況，但是在輸出樹的函數中沒有加入空樹的考慮而只是在創建樹函數中加入了if…else…的判斷。經過反復的檢查，發現可以直接在輸出函數中加入判斷而不必再其他位置判斷，并且調試成功。

五．使用說明和測試結果

測試數據：

創建二叉樹

增加二叉樹

直接創建平衡二叉樹

— 4 —平衡二叉樹加入新節點并調平

刪除結點

六．心得體會

了解了建立樹的方法；

學會了利用二分法建立樹結構。、； 學習到了二叉樹的調平方法；

學會了向一個已知樹插入或刪除結點的方法。

— 6 —

第三篇：數據結構課程設計-平衡二叉樹操作

課 程 設 計 報 告

課程名稱 數據結構課程設計 題 目平衡二叉樹操作 指導教師 設計起止日 2010-5-16 學 院 計算機學院 專 業

軟件工程 學生姓名

班級/學號------------成 績 _________________

一． 需求分析

1、建立平衡二叉樹并進行創建、增加、刪除、調平等操作。

2、設計一個實現平衡二叉樹的程序，可進行創建、增加、刪除、調平等操作，實現動態的輸入數據，實時的輸出該樹結構。

3、測試數據：自選數據

二． 概要設計

平衡二叉樹是在構造二叉排序樹的過程中，每當插入一個新結點時，首先檢查是否因插入新結點而破壞了二叉排序樹的平衡性，若是，則找出其中的最小不平衡子樹，在保持二叉排序樹特性的前提下，調整最小不平衡子樹中各結點之間的鏈接關系，進行相應的旋轉，使之成為新的平衡子樹。具體步驟如下：

⑴ 每當插入一個新結點，從該結點開始向上計算各結點的平衡因子，即計算該結點的祖先結點的平衡因子，若該結點的祖先結點的平衡因子的絕對值均不超過1，則平衡二叉樹沒有失去平衡，繼續插入結點；

⑵ 若插入結點的某祖先結點的平衡因子的絕對值大于1，則找出其中最小不平衡子樹的根結點；

⑶ 判斷新插入的結點與最小不平衡子樹的根結點的關系，確定是哪種類型的調整；

⑷ 如果是LL型或RR型，只需應用扁擔原理旋轉一次，在旋轉過程中，如果出現沖突，應用旋轉優先原則調整沖突；如果是LR型或RL型，則需應用扁擔原理旋轉兩次，第一次最小不平衡子樹的根結點先不動，調整插入結點所在子樹，第二次再調整最小不平衡子樹，在旋轉過程中，如果出現沖突，應用旋轉優先原則調整沖突；

⑸ 計算調整后的平衡二叉樹中各結點的平衡因子，檢驗是否因為旋轉而破壞其他結點的平衡因子，以及調整后的平衡二叉樹中是否存在平衡因子大于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型的轉換，使得在調試時經常沒有更改內部變量的值，導致編譯出錯。

對于在空樹情況下刪除結點的考慮，是在后期的調試檢驗過程中發現的。在沒有更改代碼前，如果按此操作，程序就會崩潰。原因就是在刪除函數中雖然考慮到了空樹的情況，但是在輸出樹的函數中沒有加入空樹的考慮而只是在創建樹函數中加入了if…else…的判斷。經過反復的檢查，發現可以直接在輸出函數中加入判斷而不必再其他位置判斷，并且調試成功。

五．使用說明和測試結果

測試數據：

創建二叉樹

— 4 —

增加二叉樹

直接創建平衡二叉樹

平衡二叉樹加入新節點并調平

刪除結點

— 6 —

六．心得體會

了解了建立樹的方法；

學會了利用二分法建立樹結構。、； 學習到了二叉樹的調平方法；

學會了向一個已知樹插入或刪除結點的方法。七．附錄 源代碼

#include “stdafx.h” #include #include #define EQ(a,b)((a)==(b))#define LT(a,b)((a)<(b))#define LQ(a,b)((a)>(b))#define LH +1 //左高 #define EH 0 //等高 #define RH-1 //右高 typedef struct BTNode { int data;int bf;//平衡因子 struct BTNode *lchild,*rchild;//左、右孩子

}BTNode,*BTree;

/*需要的函數聲明*/ 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);/*主函數*/ 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.創建二叉樹2.增加新結點3.直接創建平衡二叉樹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(“按任意鍵繼續.”);

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相同關鍵字的結點，則插入一個數據元素為i的新結點，并返回１，否則返回０*/ bool InsertAVL(BTree &T,int i,bool &taller){

if(!T)//插入新結點，樹“長高”，置taller為true {

} else {

if(EQ(i,T->data))//樹中已存在和有相同關鍵字的結點 {

} if(LT(i,T->data))//應繼續在*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 //應繼續在*T的右子樹中進行搜索 { if(!InsertAVL(T->rchild,i,taller))return 0;

— 11 — } } return 1;} /*按樹狀打印輸出二叉樹的元素,m表示結點所在層次*/ void PrintBT(BTree T,int m){

} /*創建二叉樹，以輸入-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(“您創建的二叉樹為：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(“平衡二叉樹創建結束.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))//應繼續在*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: //原本左子樹、右子等高，現因左子樹增高而使樹增高

case RH: //原本右子樹比左子樹高，現左、右子樹等高

else //應繼續在*T的右子樹中進行搜索 {

} return 1;if(!SetAVL(T->rchild,i,taller))

{

} case LH: //原本左子樹比右子樹高，現左、右子樹等高

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: //原本左子樹、右子等高，現因右子樹增高而使樹增高

case RH: //原本右子樹比左子樹高，需要作右平衡處理

— 18 —

第四篇：數據結構平衡二叉樹的操作演示

平衡二叉樹操作的演示

1.需求分析

本程序是利用平衡二叉樹，實現動態查找表的基本功能：創建表，查找、插入、刪除。具體功能：

（1）初始，平衡二叉樹為空樹，操作界面給出創建、查找、插入、刪除、合并、分裂六種操作供選擇。每種操作均提示輸入關鍵字。每次插入或刪除一個結點后，更新平衡二叉樹的顯示。

（2）平衡二叉樹的顯示采用凹入表現形式。（3）合并兩棵平衡二叉樹。

（4）把一棵二叉樹分裂為兩棵平衡二叉樹，使得在一棵樹中的所有關鍵字都小于或等于x，另一棵樹中的任一關鍵字都大于x。

如下圖：

2．概要設計

平衡二叉樹是在構造二叉排序樹的過程中，每當插入一個新結點時，首先檢查是否因插入新結點而破壞了二叉排序樹的平衡性，若是則找出其中的最小不平衡子樹，在保持二叉排序樹特性的前提下，調整最小不平衡子樹中各結點之間的鏈接關系，進行相應的旋轉，使之成為新的平衡子樹。具體步驟：

（1）每當插入一個新結點，從該結點開始向上計算各結點的平衡因子，即計算該結點的祖先結點的平衡因子，若該結點的祖先結點的平衡因子的絕對值不超過1，則平衡二叉樹沒有失去平衡，繼續插入結點；

（2）若插入結點的某祖先結點的平衡因子的絕對值大于1，則找出其中最小不平衡子樹的根結點；

（3）判斷新插入的結點與最小不平衡子樹的根結點個關系，確定是那種類型的調整；（4）如果是LL型或RR型，只需應用扁擔原理旋轉一次，在旋轉過程中，如果出現沖突，應用旋轉優先原則調整沖突；如果是LR型或RL型，則需應用扁擔原理旋轉兩次，第一次最小不平衡子樹的根結點先不動，調整插入結點所在子樹，第二次再調整最小不平衡子樹，在旋轉過程中，如果出現沖突，應用旋轉優先原則調整沖突；

（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 #include //#define TRUE 1 //#define FALSE 0 //#define OK 1 //#define ERROR 0 #define LH +1 #define EH 0 #define RH-1 //二叉類型樹的類型定義 typedefint Status;typedefintElemType;typedefstructBSTNode{ ElemType data;int bf;//結點的平衡因子

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(“輸入結點個數:”);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 data);if(T->lchild)PrintBSTree(T->lchild,lev+1);} void Start(BSTree&T1,BSTree &T2){

intcho,taller,e,k;taller = 0;k = 0;while(1){ system(“cls”);printf(“平衡二叉樹操作的演示 nn”);printf(“********************************n”);printf(“平衡二叉樹顯示區 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.創建 2.插入 3.查找 4.刪除 10.分裂n”);printf(“T2操作：5.創建 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(“刪除失敗！n”);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);}

第五篇：數據結構作業——二叉樹

數據結構實驗報告二

題目：

用先序遞歸過程監理二叉樹（存儲結構：二叉鏈表）

輸入數據按先序遍歷輸入，當某節點左子樹或者右子樹為空時，輸入‘*’號，如輸入abc**d**e**時，得到的二叉樹為：

并用如下實力測試：

算法思路：

顯然，建立一個二叉鏈表存儲的二叉樹，如果不考慮效率要求，考慮到程序的簡介性，遞歸建立和遞歸遍歷是一種很好的辦法。

利用C++的類模板的方法實現建立，遍歷，輸出等二叉樹操作。首先利用構造函數實現先序遍歷建立二叉樹，然后調用類模板中已經聲明好的四種遍歷函數，將遍歷結果輸出，檢驗建立好的二叉樹是否為要求的二叉樹。

初始化：利用構造函數建立二叉樹。采用先序遞歸的調用方法，構造函數主體如下：

template BiTree::BiTree(){ this->root = Creat();//利用this指針調用creat函數 }

template BiNode* BiTree::Creat()//定義構造函數 { BiNode* root;T aa;cout<<“請按前序序列方式輸入節點數據，每次輸入一個”<>aa;if(aa==“*”)root = NULL;else{

root = new BiNode;

//生成一個結點 root->data=aa;

root->lchild = Creat();

//遞歸建立左子樹

root->rchild = Creat();

//遞歸建立右子樹

} return root;} 構造這樣的函數，可以在輸入時，按先序遍歷順序每次輸入一個節點的數據，可以實現任意二叉樹的構造。

為了檢驗構造的二叉樹是否為預先設想的二叉樹，需要遍歷二叉樹并進行輸出。考慮到單一的輸出并不能確定唯一的二叉樹，因此對遍歷二叉樹的四種常用發方法，即先序遍歷，中序遍歷，后續遍歷，層次遍歷分別實現，通過遍歷結果檢驗構造的二叉樹是否為預先設計好的二叉樹。

先序遍歷：采用遞歸的方法建立。template voidBiTree::xianxu(BiNode *root){ if(root==NULL)return;//如果節點為空，則返回空 else{ cout<data<<“ ”;//訪問根節點

xianxu(root->lchild);//先序遍歷樹的左子樹 xianxu(root->rchild);//先序遍歷樹的右子樹

} 中序遍歷：遞歸方法建立： template voidBiTree::zhongxu(BiNode *root){

if(root==NULL)return;

//如果節點為空，則返回空 else{ zhongxu(root->lchild);

//中序遞歸遍歷root的左子樹 cout<data<<“ ”;

//訪問根結點

zhongxu(root->rchild);

//中序遞歸遍歷root的右子樹

}

} 后序遍歷：遞歸方法建立： template voidBiTree::houxu(BiNode *root){

if(root==NULL)

return;

//如果節點為空，返回空 else{ houxu(root->lchild);

//后序遞歸遍歷root的左子樹 houxu(root->rchild);

//后序遞歸遍歷root的右子樹 cout<data<<“ ”;

//訪問根節點

} } 層序遍歷：采用非遞歸方法。利用隊列的方法層序遍歷二叉樹。建立一個隊列，在訪問一個節點的時候，把它的左孩子和右孩子入隊，并且將這個節點出隊。當隊列為空時，就完成了對二叉樹的層序遍歷。

template voidBiTree::cengxu(BiNode *root){ constintMaxSize = 100;int front = 0;int rear = 0;//利用隊列的方法對樹進行層序遍歷 BiNode* Q[MaxSize];BiNode* q;if(root==NULL)return;// 如果節點為空，返回空 else{

Q[rear++] = root;// 若節點不為空，則該節點入隊 while(front!= rear)

{

q = Q[front++];//只要隊列不為空，則節點依次出隊 cout<data<<“ ”;

if(q->lchild!= NULL)

Q[rear++] = q->lchild;

if(q->rchild!= NULL)

Q[rear++] = q->rchild;// 同時，該節點的雙子入隊

} } } 函數主體部分：聲明一個類中的對象，調用構造函數，建立二叉樹，并輸出四種遍歷結果，檢驗輸出結果。

int main(){

BiTreeshu;//聲明類中一個對象，在構造了一顆樹

BiNode* root = shu.Getroot();//獲取指向根結點的指針

cout<<“前序遍歷序列為 ”<

程序結構：

主函數建立一個類模板定義構造函數，析構函數，以及成員函數聲明類中的一個對象調用構造函數，構造一顆二叉樹層序遍歷二叉樹后序遍歷二叉樹中序遍歷二叉樹前序遍歷二叉樹獲取該二叉樹的根節點將結果輸出，人工檢驗 源代碼：

#include using namespace std;

template struct BiNode

{

T data;

BiNode *lchild, *rchild;};

template class BiTree

{ public: BiTree();

//構造函數，初始化一棵二叉樹 ~BiTree(void);

//析構函數，釋放二叉鏈表中各結點的存儲空間

BiNode* Getroot();

//獲得指向根結點的指針

void xianxu(BiNode *root);

//前序遍歷二叉樹

void zhongxu(BiNode *root);

//中序遍歷二叉樹

void houxu(BiNode *root);

//后序遍歷二叉樹

void cengxu(BiNode *root);

//層序遍歷二叉樹 private:

BiNode *root;

BiNode *Creat();

void Release(BiNode *root);

};template BiTree::BiTree(){ this->root = Creat();//利用this指針調用creat函數 }

template BiNode* BiTree::Creat()//定義構造函數 { BiNode* root;T aa;cout<<“請按前序序列方式輸入節點數據，每次輸入一個”<>aa;

if(aa==“*”)root = NULL;

else{

root = new BiNode;

//生成一個結點

root->data=aa;

root->lchild = Creat();

//遞歸建立左子樹

root->rchild = Creat();

//遞歸建立右子樹

}

return root;}

template BiTree::~BiTree(void){ Release(root);//析構函數，釋放存儲指針所需要的空間 }

template BiNode* BiTree::Getroot()//獲取根節點所在指針的位置 { return root;}

template void BiTree::xianxu(BiNode *root){ if(root==NULL)return;//如果節點為空，則返回空

else{

cout<data<<“ ”;//訪問根節點

xianxu(root->lchild);//先序遍歷樹的左子樹

xianxu(root->rchild);//先序遍歷樹的右子樹

} }

template void BiTree::zhongxu(BiNode *root){

if(root==NULL)return;

//如果節點為空，則返回空

else{

zhongxu(root->lchild);

//中序遞歸遍歷root的左子樹

cout<data<<“ ”;

//訪問根結點

zhongxu(root->rchild);

//中序遞歸遍歷root的右子樹

} }

template void BiTree::houxu(BiNode *root){

if(root==NULL)

return;

//如果節點為空，返回空

else{

houxu(root->lchild);

//后序遞歸遍歷root的左子樹

houxu(root->rchild);

//后序遞歸遍歷root的右子樹

cout<data<<“ ”;

//訪問根節點

} }

template void BiTree::cengxu(BiNode *root){

const int MaxSize = 100;int front = 0;int rear = 0;//利用隊列的方法對樹進行層序遍歷

BiNode* Q[MaxSize];

BiNode* q;if(root==NULL)return;// 如果節點為空，返回空

else{

Q[rear++] = root;// 若節點不為空，則該節點入隊

while(front!= rear)

{

q = Q[front++];//只要隊列不為空，則節點依次出隊

cout<data<<“ ”;

if(q->lchild!= NULL)

Q[rear++] = q->lchild;

if(q->rchild!= NULL)

Q[rear++] = q->rchild;// 同時，該節點的雙子入隊

} } }

template void BiTree::Release(BiNode* root)//析構函數，釋放存儲空間 {

if(root!= NULL){

Release(root->lchild);

//釋放左子樹

Release(root->rchild);

//釋放右子樹

delete root;

}

}

int main(){

BiTree shu;//聲明類中一個對象，在構造了一顆樹

BiNode* root = shu.Getroot();//獲取指向根結點的指針

cout<<“前序遍歷序列為 ”<

cout<<“層序遍歷序列為”<

通過對結果的分析，發現輸出結果與建立二叉樹時的輸入完全符合，說明程序的運行結果是正確的。

心得體會：

1)函數遞歸的方法可以在相當程度上使程序簡潔，避免代碼的冗長復雜。2)構造函數如果帶參數，在聲明對象的時候應該將實參指出來。但是本題中構造函數位遞歸調用，初始的根節點的數據值由鍵盤輸入，因此無法在聲明對象時引入實參。所以最后選擇了無參但是引用了this指針的構造函數。可見，對于構造函數的含參調用應該小心謹慎。

3)編程時，要不停得檢驗自己的輸入與輸出，必要的時候需要人工進行計算，以保證程序的運行按照預先的設想。