第一篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告二叉樹的應(yīng)用操作

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告

題目名稱： 二叉樹的應(yīng)用問題 專業(yè)班級： 計算機(jī)科學(xué)與技術(shù)

學(xué)生姓名：

學(xué)生學(xué)號：

指導(dǎo)教師：

目錄

一、題目要求..............................................二、需求分析..............................................三、概要設(shè)計..............................................四、詳細(xì)設(shè)計..............................................五、調(diào)試分析.............................................六、心得體會.............................................一、題目要求

實現(xiàn)二叉樹，求解若干二叉樹應(yīng)用問題

? 實現(xiàn)二叉鏈表表示的二叉樹，包括下列運算：

? 建立一棵二叉樹；

? 按先序、中序和后序遍歷二叉樹； ? 按層次遍歷；

? 求一棵二叉樹的高度；

? 交換一棵二叉樹的左右子樹；

? 設(shè)計一個菜單驅(qū)動程序，測試上述算法

二、需求分析

建立一棵二叉樹：

int CreateBiTree(BiTree &T)按先序遍歷二叉樹：

void PreOrder(BiTree &T)按中序遍歷二叉樹：

void InOrder(BiTree &T)按后序遍歷二叉樹：

void PostOrder(BiTree &T)按層次遍歷：

void LevelOrder(BiTree &T)求一棵二叉樹的高度：

int Depth(BiTree &T)交換一棵二叉樹的左右子樹：int PreOrderTraverse(BiTree T)菜單驅(qū)動程序：

void menu()

三、概要設(shè)計

定義二叉樹的存儲結(jié)構(gòu)，每個結(jié)點中設(shè)置三個域，即值域、左指針域、右指針域。要建立二叉樹T的鏈?zhǔn)酱鎯Y(jié)構(gòu)，即建立二叉鏈表。根據(jù)輸入二叉樹結(jié)點的形式不同，建立的方法也不同，本系統(tǒng)采用先序序列遞歸建立二叉樹。

先序遍歷二叉樹的操作定義為：若二叉樹為空，則空操作；否則：（1）訪問根結(jié)點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。

中序遍歷二叉樹的操作定義為：若二叉樹為空，則空操作；否則：（1）中序遍歷左子樹；（2）訪問根結(jié)點；

（3）中序遍歷右子樹。

后序遍歷二叉樹的操作定義為：若二叉樹為空，則空操作；否則：（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點。

層次遍歷二叉樹的操作選用隊列的存儲結(jié)構(gòu)。先建立一個長度為1的隊列，利用while循環(huán)，將根結(jié)點放入隊首，再將隊列長度加一。然后依次遍歷左子樹和右子樹，每遍歷一次，2、先序遍歷二叉樹：

void PreOrder(BiTree &T){ if(!T)

return;cout<data<<“ ”;PreOrder(T->left_child);PreOrder(T->right_child);}

3、中序遍歷二叉樹：

void InOrder(BiTree &T){ if(!T)return;InOrder(T->left_child);cout<data<<“ ”;InOrder(T->right_child);}

4、后序遍歷二叉樹：

void PostOrder(BiTree &T){ if(!T)return;PostOrder(T->left_child);PostOrder(T->right_child);cout<data<<“ ”;}

5、按層次遍歷：

void LevelOrder(BiTree &T){ BiTree queue[100];int front,rear;if(T==NULL)return;front=-1;rear=0;queue[rear]=T;while(front!=rear){ front++;cout<data<<“ ”;if(queue[front]->left_child!=NULL){ rear++;queue[rear]=queue[front]->left_child;

cin>>a;if(a>=0||a<=7){ switch(a){ case 0:

{

cout<<“建立后的二叉樹為：n”;

Output(T);

cout<

}

system(“pause”);

break;case 1:

cout<<“該樹的樹深為: ”<

system(“pause”);

break;case 2:

{

cout<<“該樹以先序遍歷輸出為：n”;

PreOrder(T);

cout<

}

system(“pause”);

break;case 3:

{

cout<<“該樹以中序遍歷輸出為:n”;

InOrder(T);

cout<

}

system(“pause”);

break;case 4:

{

cout<<“該樹以后序遍歷輸出為：n”;

PostOrder(T);

cout<

}

system(“pause”);

break;case 5:

{

cout<<“該樹的層次遍歷：n”;

LevelOrder(T);

cout<

（二）詳細(xì)程序代碼：{ if(!T){

cout<<“空樹!n”;

return;} cout<data<<“ ”;if(T->left_child)Output(T->left_child);if(T->right_child)Output(T->right_child);}

int Depth(BiTree &T){ int i,j;if(!T)return 0;i=Depth(T->left_child);j=Depth(T->right_child);return(i>j?i:j)+1;}

void PreOrder(BiTree &T){ if(!T)

return;cout<data<<“ ”;PreOrder(T->left_child);PreOrder(T->right_child);}

void InOrder(BiTree &T){ if(!T)return;InOrder(T->left_child);cout<data<<“ ”;InOrder(T->right_child);}

void PostOrder(BiTree &T){ if(!T)return;PostOrder(T->left_child);PostOrder(T->right_child);cout<data<<“ ”;}

void LevelOrder(BiTree &T)

cout<<“<<

1.二叉樹樹深

>>”<

cout<<“<<

2.二叉樹的先序遍歷

>>”<

cout<<“<<

3.二叉樹的中序遍歷

>>”<

cout<<“<<

4.二叉樹的后序遍歷

>>”<

cout<<“<<

5.二叉樹的層次遍歷

>>”<

cout<<“<<

6.左右孩子交換

>>”<

cout<<“<<

7.退出

>>”<

cout<<“*******************************************************************”<

void main(){

int br,a;BiTree T;br=CreateBiTree(T);

while(1){

menu();

cout<<“請輸入選擇的命令-->”;

cin>>a;

if(a>=0||a<=7)

{

switch(a)

{

case 0:

{

cout<<“建立后的二叉樹為：n”;

Output(T);

cout<

}

system(“pause”);

break;

case 1:

cout<<“該樹的樹深為: ”<

system(“pause”);

break;

case 2:

{

cout<<“該樹以先序遍歷輸出為：n”;

PreOrder(T);

cout<

}

system(“pause”);

break;

case 3:

{

cout<<“該樹以中序遍歷輸出為:n”;

（一）先序輸入二叉樹：

（二）建立一棵二叉樹：

1后序遍歷：

（四）按層次遍歷：

3中序遍歷交換后的二叉樹：

六、心得體會

這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計我選擇的題目是二叉樹的應(yīng)用操作，題目要求中最難的部分是二叉樹的層次遍歷。在實現(xiàn)這個要求的時候我想了很久，最后通過在CSDN上找到了解決思路，就是用隊列的方式。雖然是二叉樹的題目，但是和其他知識點都有很多內(nèi)在的聯(lián)系。經(jīng)過這次的實驗，我不僅在二叉樹的應(yīng)用操作層面上更加熟悉，對二叉樹的理解更加深刻，更重要的是我認(rèn)識到知識要融會貫通才是它的價值所在。我的C語言基礎(chǔ)不是很扎實，所以在寫代碼的時候也遇到很大的困難。像很基礎(chǔ)的“j?i:j”也是通過翻閱以前的書籍才找到答案。還有在編程過程中的習(xí)慣也不是很好，函數(shù)及變量的命名等細(xì)節(jié)問題，如果不加以注意的話，會對后面的編譯調(diào)試造成很多不必要的麻煩。我應(yīng)該在以后的學(xué)習(xí)中加強(qiáng)實踐，這樣才能更扎實地掌握所學(xué)知識點，更有效地將書本上的知識變成解決實際問題的經(jīng)驗。

第二篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-_平衡二叉樹操作 - 副本

課 程 設(shè) 計 報 告

一． 需求分析

1、建立平衡二叉樹并進(jìn)行創(chuàng)建、增加、刪除、調(diào)平等操作。

2、設(shè)計一個實現(xiàn)平衡二叉樹的程序，可進(jìn)行創(chuàng)建、增加、刪除、調(diào)平等操作，實現(xiàn)動態(tài)的輸入數(shù)據(jù)，實時的輸出該樹結(jié)構(gòu)。

3、測試數(shù)據(jù)：自選數(shù)據(jù)

二． 概要設(shè)計

平衡二叉樹是在構(gòu)造二叉排序樹的過程中，每當(dāng)插入一個新結(jié)點時，首先檢查是否因插入新結(jié)點而破壞了二叉排序樹的平衡性，若是，則找出其中的最小不平衡子樹，在保持二叉排序樹特性的前提下，調(diào)整最小不平衡子樹中各結(jié)點之間的鏈接關(guān)系，進(jìn)行相應(yīng)的旋轉(zhuǎn)，使之成為新的平衡子樹。具體步驟如下：

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

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

⑶ 判斷新插入的結(jié)點與最小不平衡子樹的根結(jié)點的關(guān)系，確定是哪種類型的調(diào)整；

⑷ 如果是LL型或RR型，只需應(yīng)用扁擔(dān)原理旋轉(zhuǎn)一次，在旋轉(zhuǎn)過程中，如果出現(xiàn)沖突，應(yīng)用旋轉(zhuǎn)優(yōu)先原則調(diào)整沖突；如果是LR型或RL型，則需應(yīng)用扁擔(dān)原理旋轉(zhuǎn)兩次，第一次最小不平衡子樹的根結(jié)點先不動，調(diào)整插入結(jié)點所在子樹，第二次再調(diào)整最小不平衡子樹，在旋轉(zhuǎn)過程中，如果出現(xiàn)沖突，應(yīng)用旋轉(zhuǎn)優(yōu)先原則調(diào)整沖突；

⑸ 計算調(diào)整后的平衡二叉樹中各結(jié)點的平衡因子，檢驗是否因為旋轉(zhuǎn)而破壞其他結(jié)點的平衡因子，以及調(diào)整后的平衡二叉樹中是否存在平衡因子大于1的結(jié)點。

三． 詳細(xì)設(shè)計

樹的內(nèi)部變量

— 1 — typedef struct BTNode {

int data;int bf;//平衡因子 struct BTNode *lchild,*rchild;//左、右孩子

}BTNode,*BTree;調(diào)平二叉樹(左右調(diào)平方式大體雷同，之具體寫出其中一種調(diào)平方式)if(插入元素與當(dāng)前根元素相等){ printf(“已存在相同關(guān)鍵字的結(jié)點n”);} if(插入元素小于當(dāng)前根元素)){ if(插入新結(jié)點不成功)

return 0;if(插入成功)

switch(查看根的平衡因子)

{

case +1:

進(jìn)行左平衡處理;

{

檢查*T的左子樹的平衡度，并作相應(yīng)平衡處理

{

case +1:

令根及其左孩子的平衡因子為0;

做右平衡處理;

{

BTree lc;

lc指向的結(jié)點左子樹根結(jié)點;

rc的右子樹掛接為結(jié)點的左子樹;

lc的右孩子為原結(jié)點;

原結(jié)點指向新的結(jié)點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:

四．調(diào)試分析

在進(jìn)行對插入新結(jié)點并調(diào)平時由于利用的是普通的插入方法進(jìn)行LL、LR、RL、RR型的轉(zhuǎn)換，使得在調(diào)試時經(jīng)常沒有更改內(nèi)部變量的值，導(dǎo)致編譯出錯。

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

五．使用說明和測試結(jié)果

測試數(shù)據(jù)：

創(chuàng)建二叉樹

增加二叉樹

直接創(chuàng)建平衡二叉樹

— 4 —平衡二叉樹加入新節(jié)點并調(diào)平

刪除結(jié)點

六．心得體會

了解了建立樹的方法；

學(xué)會了利用二分法建立樹結(jié)構(gòu)。、； 學(xué)習(xí)到了二叉樹的調(diào)平方法；

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

— 6 —

第三篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-平衡二叉樹操作

課 程 設(shè) 計 報 告

課程名稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 題 目平衡二叉樹操作 指導(dǎo)教師 設(shè)計起止日 2010-5-16 學(xué) 院 計算機(jī)學(xué)院 專 業(yè)

軟件工程 學(xué)生姓名

班級/學(xué)號------------成 績 _________________

一． 需求分析

1、建立平衡二叉樹并進(jìn)行創(chuàng)建、增加、刪除、調(diào)平等操作。

2、設(shè)計一個實現(xiàn)平衡二叉樹的程序，可進(jìn)行創(chuàng)建、增加、刪除、調(diào)平等操作，實現(xiàn)動態(tài)的輸入數(shù)據(jù)，實時的輸出該樹結(jié)構(gòu)。

3、測試數(shù)據(jù)：自選數(shù)據(jù)

二． 概要設(shè)計

平衡二叉樹是在構(gòu)造二叉排序樹的過程中，每當(dāng)插入一個新結(jié)點時，首先檢查是否因插入新結(jié)點而破壞了二叉排序樹的平衡性，若是，則找出其中的最小不平衡子樹，在保持二叉排序樹特性的前提下，調(diào)整最小不平衡子樹中各結(jié)點之間的鏈接關(guān)系，進(jìn)行相應(yīng)的旋轉(zhuǎn)，使之成為新的平衡子樹。具體步驟如下：

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

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

⑶ 判斷新插入的結(jié)點與最小不平衡子樹的根結(jié)點的關(guān)系，確定是哪種類型的調(diào)整；

⑷ 如果是LL型或RR型，只需應(yīng)用扁擔(dān)原理旋轉(zhuǎn)一次，在旋轉(zhuǎn)過程中，如果出現(xiàn)沖突，應(yīng)用旋轉(zhuǎn)優(yōu)先原則調(diào)整沖突；如果是LR型或RL型，則需應(yīng)用扁擔(dān)原理旋轉(zhuǎn)兩次，第一次最小不平衡子樹的根結(jié)點先不動，調(diào)整插入結(jié)點所在子樹，第二次再調(diào)整最小不平衡子樹，在旋轉(zhuǎn)過程中，如果出現(xiàn)沖突，應(yīng)用旋轉(zhuǎn)優(yōu)先原則調(diào)整沖突；

⑸ 計算調(diào)整后的平衡二叉樹中各結(jié)點的平衡因子，檢驗是否因為旋轉(zhuǎn)而破壞其他結(jié)點的平衡因子，以及調(diào)整后的平衡二叉樹中是否存在平衡因子大于1的結(jié)點。

三． 詳細(xì)設(shè)計

樹的內(nèi)部變量

typedef struct BTNode { — 2 —

int data;int bf;//平衡因子 struct BTNode *lchild,*rchild;//左、右孩子

}BTNode,*BTree;調(diào)平二叉樹(左右調(diào)平方式大體雷同，之具體寫出其中一種調(diào)平方式)if(插入元素與當(dāng)前根元素相等){ printf(“已存在相同關(guān)鍵字的結(jié)點n”);} if(插入元素小于當(dāng)前根元素)){ if(插入新結(jié)點不成功)

return 0;if(插入成功)

switch(查看根的平衡因子)

{

case +1:

進(jìn)行左平衡處理;

{

檢查*T的左子樹的平衡度，并作相應(yīng)平衡處理

{

case +1:

令根及其左孩子的平衡因子為0;

做右平衡處理;

{

BTree lc;

lc指向的結(jié)點左子樹根結(jié)點;

rc的右子樹掛接為結(jié)點的左子樹;

lc的右孩子為原結(jié)點;

原結(jié)點指向新的結(jié)點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:

四．調(diào)試分析

在進(jìn)行對插入新結(jié)點并調(diào)平時由于利用的是普通的插入方法進(jìn)行LL、LR、RL、RR型的轉(zhuǎn)換，使得在調(diào)試時經(jīng)常沒有更改內(nèi)部變量的值，導(dǎo)致編譯出錯。

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

五．使用說明和測試結(jié)果

測試數(shù)據(jù)：

創(chuàng)建二叉樹

— 4 —

增加二叉樹

直接創(chuàng)建平衡二叉樹

平衡二叉樹加入新節(jié)點并調(diào)平

刪除結(jié)點

— 6 —

六．心得體會

了解了建立樹的方法；

學(xué)會了利用二分法建立樹結(jié)構(gòu)。、； 學(xué)習(xí)到了二叉樹的調(diào)平方法；

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

#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;

/*需要的函數(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.增加新結(jié)點3.直接創(chuàng)建平衡二叉樹4.在平衡二叉樹上增加新結(jié)點并調(diào)平衡5.scanf(”%d“,&input);getchar();switch(input){ case 1:

CreatBT(T);break;printf(”請輸入你要增加的關(guān)鍵字“);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(“請輸入你要增加的關(guān)鍵字”);

scanf(“%d”,&search);

getchar();

SetAVL(T,search,taller);

m = 0;

PrintBT(T,m);

break;

case 5:

printf(“請輸入你要刪除的關(guān)鍵字”);

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左子樹根結(jié)點

p->lchild = lc->rchild;//rc的右子樹掛接為*p的左子樹 lc->rchild = p;p = lc;//p指向新的結(jié)點

} /*對以*p為根的二叉排序樹作左旋處理*/ void Left_Balance(BTree &p){ BTree rc;rc = p->rchild;//指向的*p右子樹根結(jié)點

p->rchild = rc->lchild;//rc左子樹掛接到*p的右子樹

rc->lchild = p;p = rc;//p指向新的結(jié)點

— 9 — } /*對以指針T所指結(jié)點為根的二叉樹作左平衡旋轉(zhuǎn)處理*/ void Left_Root_Balance(BTree &T){

} /*對以指針T所指結(jié)點為根的二叉樹作右平衡旋轉(zhuǎn)處理*/ void Right_Root_Balance(BTree &T){

BTree rc,ld;rc = T->rchild;//指向*T的左子樹根結(jié)點

switch(rc->bf)//檢查*T的右子樹的平衡度，并作相應(yīng)平衡處理 { case RH: //新結(jié)點插入在*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的左子樹根結(jié)點

switch(lc->bf)//檢查*T的左子樹的平衡度，并作相應(yīng)平衡處理 { case LH: //新結(jié)點插入在*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: //新結(jié)點插入在*T的左孩子的右子樹上，要作雙旋處理

case EH: case RH: case LH: //新結(jié)點插入在*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: /*插入結(jié)點i,若T中存在和i相同關(guān)鍵字的結(jié)點，則插入一個數(shù)據(jù)元素為i的新結(jié)點，并返回１，否則返回０*/ bool InsertAVL(BTree &T,int i,bool &taller){

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

} else {

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

} if(LT(i,T->data))//應(yīng)繼續(xù)在*T的左子樹中進(jìn)行搜索 taller = false;printf(“已存在相同關(guān)鍵字的結(jié)點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 //應(yīng)繼續(xù)在*T的右子樹中進(jìn)行搜索 { if(!InsertAVL(T->rchild,i,taller))return 0;

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

} /*創(chuàng)建二叉樹，以輸入-32767為建立的結(jié)束*/ void CreatBT(BTree &T){

} int m;int i;bool taller=false;T = NULL;printf(“n請輸入關(guān)鍵字(以-32767結(jié)束建立二叉樹):”);scanf(“%i”,&i);getchar();while(i!=-32767){

} m=0;printf(“您創(chuàng)建的二叉樹為：n”);PrintBT(T,m);InsertAVL(T,i,taller);printf(“n請輸入關(guān)鍵字(以-32767結(jié)束建立二叉樹):”);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 — /*刪除結(jié)點時左平衡旋轉(zhuǎn)處理*/ void Left_Root_Balance_det(BTree &p,int &shorter){

BTree p1,p2;if(p->bf==1)//p結(jié)點的左子樹高，刪除結(jié)點后p的bf減,樹變矮 {

} else if(p->bf==0)//p結(jié)點左、右子樹等高，刪除結(jié)點后p的bf減,樹高不變 {

} else //p結(jié)點的右子樹高 {

p1=p->rchild;//p1指向p的右子樹

if(p1->bf==0)//p1結(jié)點左、右子樹等高,刪除結(jié)點后p的bf為-2,進(jìn)行左旋處理，樹高不變 {

} else if(p1->bf==-1)//p1的右子樹高，左旋處理后，樹變矮 {

} else //p1的左子樹高,進(jìn)行雙旋處理(先右旋后左旋)，樹變矮 {

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;/*刪除結(jié)點時右平衡旋轉(zhuǎn)處理*/ 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;

} } } /*刪除結(jié)點*/ 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的左子樹中進(jìn)行刪除 {

} else if(x>p->data)//在p的右子樹中進(jìn)行刪除 {

} 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(“不存在要刪除的關(guān)鍵字！n”);return 0;— 16 — /*二叉樹調(diào)平操作*/ void Adj_balance(BTree &T){ int m;int i;bool taller=false;T = NULL;printf(“n請輸入關(guān)鍵字(以-32767結(jié)束建立平衡二叉樹):”);scanf(“%d”,&i);getchar();while(i!=-32767){

SetAVL(T,i,taller);

printf(“n請輸入關(guān)鍵字(以-32767結(jié)束建立平衡二叉樹):”);

scanf(“%d”,&i);

getchar();

taller=false;} m=0;printf(“平衡二叉樹創(chuàng)建結(jié)束.n”);if(T)

PrintBT(T,m);else

printf(“這是一棵空樹.n”);} /*調(diào)平二叉樹具體方法*/ bool SetAVL(BTree &T,int i,bool &taller){ if(!T)//插入新結(jié)點，樹“長高”，置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))//樹中已存在和有相同關(guān)鍵字的結(jié)點

{

taller = false;

printf(“已存在相同關(guān)鍵字的結(jié)點n”);

return 0;

}

if(LT(i,T->data))//應(yīng)繼續(xù)在*T的左子樹中進(jìn)行搜索 {

}

}

} 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 //應(yīng)繼續(xù)在*T的右子樹中進(jìn)行搜索 {

} 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ù)結(jié)構(gòu)二叉樹操作驗證實驗報告

班級：計算機(jī)11-2 學(xué)號：40 姓名：朱報龍

成績：_________

實驗七 二叉樹操作驗證

一、實驗?zāi)康?/p>

⑴ 掌握二叉樹的邏輯結(jié)構(gòu)；

⑵ 掌握二叉樹的二叉鏈表存儲結(jié)構(gòu)；

⑶ 掌握基于二叉鏈表存儲的二叉樹的遍歷操作的實現(xiàn)。

二、實驗內(nèi)容

⑴ 建立一棵含有n個結(jié)點的二叉樹，采用二叉鏈表存儲；

⑵ 前序（或中序、后序）遍歷該二叉樹。

三、設(shè)計與編碼

#include using namespace std;template class BTree;template //***********************二叉樹結(jié)點類定義********************** class BTreeNode { friend class BTree ;T data;BTreeNode *lchild,*rchild;public: BTreeNode():lchild(NULL),rchild(NULL){} BTreeNode(T d,BTreeNode *r=NULL):data(d),lchild(l),rchild(r){}

*l=NULL,BTreeNode T getdata(){return data;} BTreeNode * getleft(){return lchild;} BTreeNode * getright(){return rchild;} };//***********************END******************************** //***********************二叉樹模板類定義******************* template class BTree { public: BTree(T a[],int n);void preorder(void visit(BTreeNode *p));static void preorder(BTreeNode * p,void visit(BTreeNode *p));//遞歸前序遍歷

void inorder(void visit(BTreeNode *p));static void inorder(BTreeNode * p,void visit(BTreeNode *p));//遞歸中序遍歷

void postorder(void visit(BTreeNode *p));static void postorder(BTreeNode * p,void visit(BTreeNode * p));//遞歸后序遍歷

static void fun(BTreeNode *p){cout <

data;}//訪問結(jié)點 protected: BTreeNode * root;private: T* a;int n;BTreeNode * build0(int i);};

//***********************建樹******************************* template BTreeNode * BTree ::build0(int i)//遞歸建樹 { BTreeNode *p;int l,r;if((i <=n)&&(a[i-1]!=' ')){ p=new BTreeNode ;p->data=a[i-1];l=2*i;r=2*i+1;p->lchild=build0(l);p->rchild=build0(r);return(p);} else return(NULL);}

template BTree ::BTree(T a[],int n){ this->a=a;this->n=n;root=build0(1);cout <<“遞歸建樹成功!”<

//***********************遍歷******************************* template void BTree ::preorder(void visit(BTreeNode *p))//遞歸前序遍歷 { preorder(root,visit);cout < void BTree ::preorder(BTreeNode * p,void visit(BTreeNode *p)){ if(p!=NULL){ visit(p);preorder(p->lchild,visit);preorder(p->rchild,visit);} } template void BTree ::inorder(void visit(BTreeNode *p)){ inorder(root,visit);cout < void BTree ::inorder(BTreeNode * p,void visit(BTreeNode *p)){ if(p!=NULL){ inorder(p->lchild,visit);visit(p);inorder(p->rchild,visit);} } template void BTree ::postorder(void visit(BTreeNode *p))//遞歸后序遍歷 { postorder(root,visit);cout < void BTree ::postorder(BTreeNode * p,void visit(BTreeNode *p)){ if(p!=NULL){ postorder(p->lchild,visit);postorder(p->rchild,visit);visit(p);} } void main(){ char *str=“abcd e”;cout<s(str,6);cout <>choice;cout <

{cout <<“遞歸先序遍歷二叉樹：”;s.preorder(s.fun);cout <

答：經(jīng)常忘記對頭結(jié)點的定義，以至于程序出錯，經(jīng)定義頭結(jié)點，使程序正常運行。

b)程序運行的結(jié)果如何？

四、實驗小結(jié) 多練習(xí)，多上機(jī)，耐心調(diào)試程序，找出錯誤，多總結(jié)。

第五篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計二叉樹平衡的判定

數(shù)據(jù)結(jié)構(gòu)與算法 課程設(shè)計報告

課程設(shè)計題目： 二叉樹平衡的判定

專業(yè)班級： 信息與計算科學(xué)1001班 姓 名： 謝煒 學(xué) 號：100701114 設(shè)計室號： 理學(xué)院機(jī)房 設(shè)計時間： 2011-12-26 批閱時間： 指導(dǎo)教師： 杜洪波 成 績：

一、摘要：

基于我們對C語言和數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)我們有能力編寫處理一些比較基本而又簡單的問題。在我們此題我們的目標(biāo)就是任意給出一個二叉樹我們判斷是否為平衡的二叉樹。

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

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

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

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

二、問題重敘：

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

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

我們將先通過前序和中序或者中序和后序?qū)⑺袛嗟亩鏄漭斎?。建立一個明確的二叉樹在此基礎(chǔ)上判斷二叉樹是否為平衡二叉樹。

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

三、流程圖如下：

四、模塊分析：

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

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代表著根節(jié)點

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、輸入各節(jié)點元素

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(”請選擇生成二叉樹規(guī)則：前序和中序(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(”不要亂選，不支持其他模式");

} } }