數(shù)據(jù)結(jié)構(gòu)程序的設(shè)計(jì)報(bào)告(平衡二叉樹)

1、數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)報(bào)告平衡二叉樹學(xué)生姓名 :學(xué)號:班級:指導(dǎo)老師 :報(bào)告日期 :1. 題目與要求1) . 問題的提出編寫已個(gè)平衡二叉樹， 主要是對插入一個(gè)元素導(dǎo)致樹不平衡的情況進(jìn)行平衡化處理以及相關(guān)的處理。2）設(shè)計(jì)的知識點(diǎn)隊(duì)列的插入，刪除，二叉樹的建立于銷毀，平衡樹的平衡化，以及 C語言中基礎(chǔ)應(yīng)用于結(jié)構(gòu)等。3）功能要求(1). 通過不斷插入的方式創(chuàng)建一棵平衡二叉樹，包括輸入結(jié)點(diǎn)的關(guān)鍵字和相關(guān)信息。(2) 按要求輸出創(chuàng)建的平衡二叉樹結(jié)點(diǎn)，包括順序（中序）輸出和按層次輸出。(3) 插入新增的結(jié)點(diǎn)，若結(jié)點(diǎn)不存在則插入平衡二叉樹，并進(jìn)行相關(guān)調(diào)整。(4) 銷毀二叉樹。(5) 退出菜單界

2、面如下：.2. 功能設(shè)計(jì)算法設(shè)計(jì)選擇創(chuàng)建平衡二叉樹后，利用循環(huán)不斷插入結(jié)點(diǎn)，并進(jìn)行調(diào)整，當(dāng)輸入節(jié)點(diǎn)為 0 時(shí)停止進(jìn)入菜單界面。在平橫二叉樹排序樹BSTree上插入一個(gè)新的數(shù)據(jù)元素的遞歸算法可如下描述：（） 若 BSTree為空樹，則插入一個(gè)數(shù)據(jù)元素為e 的新結(jié)點(diǎn)作為BSTree的根結(jié)點(diǎn)，樹的深度增1；（） 若 e 的關(guān)鍵字和 BSTree的根節(jié)點(diǎn)的關(guān)鍵字相等，則不進(jìn)行插入；（） 若 e 的關(guān)鍵字小于 BSTree的根結(jié)點(diǎn)的關(guān)鍵字，而且在其左子樹中不存在和 e 形同的關(guān)鍵字的結(jié)點(diǎn)，則將 e 插入在其左子樹上，并且當(dāng)插入之后的左子樹的深度加 1 時(shí)，分別就下列不同情況處理之：a. BSTree的跟

3、結(jié)點(diǎn)的平衡因子為 -1 （右子樹的深度大于左子樹的深度）：則將跟結(jié)點(diǎn)的平衡因子更改為 0，BBST的深度不變；b. BBST的根結(jié)點(diǎn)的平衡因子為 0（左，右子樹的深度相等） ：則將根結(jié)點(diǎn)的平衡因子更改為 1，BBST的深度增 1；c. BBST的根結(jié)點(diǎn)的平衡 因子為 1（左子樹的深度大于右子樹的深度）：若 BBST的左子樹根結(jié)點(diǎn)的平衡因子為 1，則需進(jìn)行向左旋平衡處理，并且在右旋之后，將根節(jié)點(diǎn)和其右子樹根節(jié)點(diǎn)的平衡因子更改為 0，樹的深度不變；若 BBST的左子樹根結(jié)點(diǎn)的平衡因子為 -1 ，則需進(jìn)行向左，向.右的雙向旋轉(zhuǎn)平衡處理，并且在旋轉(zhuǎn)處理之后，修改根結(jié)點(diǎn)和其左右子樹的平衡因子，數(shù)的深度不

4、變；（） 若 e 的關(guān)鍵字大于 BBST的根結(jié)點(diǎn)的關(guān)鍵字，而且在 BBST的右子樹中不存在和 e 有相同的關(guān)鍵字的的節(jié)點(diǎn)，則將 e 插入在BBST的右子樹上，并且當(dāng)插入之后的右子樹深度增加（+1）時(shí)，分別就不同情況處理之。3. 詳細(xì)設(shè)計(jì)1）結(jié)點(diǎn)類型定義：typedef struct ElemTypeKeyType Key; / 鍵值類型 char info20;ElemType;Typedef struct BSTNodeElemType data；int bf ;/結(jié)點(diǎn)的平衡因子struct BSTNode *lchild，*rchild；/ 左右孩子指針BSTNode，*BSTree；2）

5、調(diào)平二叉樹 ( 左右調(diào)平方式大體雷同，之具體寫出其中一種調(diào)平方式)if ( 插入元素與當(dāng)前根元素相等)printf( 已存在相同關(guān)鍵字的結(jié)點(diǎn)n );if ( 插入元素小于當(dāng)前根元素)if ( 插入新結(jié)點(diǎn)不成功)return0;if ( 插入成功 )switch ( 查看根的平衡因子)case +1:進(jìn)行左平衡處理;檢查 *T的左子樹的平衡度，并作相應(yīng)平衡處理.case +1:令根及其左孩子的平衡因子為0;做右平衡處理;BTree lc;lc 指向的結(jié)點(diǎn)左子樹根結(jié)點(diǎn);rc 的右子樹掛接為結(jié)點(diǎn)的左子樹;lc 的右孩子為原結(jié)點(diǎn);原結(jié)點(diǎn)指向新的結(jié)點(diǎn)lc;break ;case -1:rd 指向 *T

6、的左孩子的右子樹根switch ( 查看右孩子平衡因子)case +1:根的平衡因子為-1;根左孩子的平衡因子為0;break ;case 0:令根和根左孩子的平衡因子為0;break ;case -1:根平衡因子為0;根左孩子平衡因子為1;break ;根右孩子的平衡因子為0;對 *T 的左子樹作左旋平衡處理 ; 對 *T 作右旋平衡處理 ;break ;case 0:令根的平衡因子為+1;break ;case -1:令根的平衡因子為-1;break ;運(yùn)行情況：.3）輸出：(1) 中序輸出采用遞歸算法對二叉樹進(jìn)行遍歷。if （結(jié)點(diǎn)不為空）If(遍歷左孩子成功）If（遍歷結(jié)點(diǎn)成功）If（遍

7、歷右孩子成功）返回真返回假else （結(jié)點(diǎn)為空）返回假(2) 按層次輸出根據(jù)隊(duì)列先進(jìn)先出的特點(diǎn)，先將第一層結(jié)點(diǎn)進(jìn)隊(duì)a，對其出出隊(duì)并輸出，同時(shí)將其不為空的孩子指針入另一隊(duì)列b，當(dāng) a 為空時(shí)，隊(duì) b 進(jìn)行出對并輸出處理，將結(jié)點(diǎn)的不為空的左右孩子入隊(duì)a，直到 b 為空 .如此直到兩隊(duì)均為空。根節(jié)點(diǎn)入隊(duì)；While （ a，b 不同時(shí)為空）If（i 為奇數(shù)）.While（ a 隊(duì)不空）a中結(jié)點(diǎn)出隊(duì)并輸出；If（左孩子不空）左孩子入隊(duì)b；If(有孩子不空）右孩子入隊(duì)b；If（i 為偶數(shù)）While（ b 隊(duì)不空）b中結(jié)點(diǎn)出隊(duì)并輸出；If（左孩子不空）左孩子入隊(duì)a；If(有孩子不空）右孩子入隊(duì)a；I+;

8、/同時(shí)記錄樹的深度具體的運(yùn)行情況如下.4）銷毀二叉樹銷毀二叉樹的算法根據(jù)遞歸遍歷而來，算法大體相識。If(根節(jié)點(diǎn)不空）If（左子樹不空）銷毀左子樹；If（右子樹不空）銷毀右子樹；銷毀相對根節(jié)點(diǎn)；根節(jié)點(diǎn)賦空；/ 留下來以便再次創(chuàng)建二叉樹時(shí)使用注意：必須先銷毀左右子樹，否則先銷毀根節(jié)點(diǎn)后，無法找到左右孩子指針。5）退出退出時(shí)詢問是否確認(rèn)退出，確認(rèn)則退出，否則返回到主菜單4. 程序代碼設(shè)計(jì)(1) 函數(shù)原形： void CreatBalanceTree(BSTree &T);功能 : 調(diào)用插入函數(shù)，利用循環(huán)來進(jìn)行平衡二叉樹的創(chuàng)建。當(dāng)輸入的鍵值為0時(shí)停止輸入。說明：在輸入相關(guān)信息時(shí)，需要清空緩存區(qū)的回車

9、鍵值。(2) 函數(shù)原形： int InsertAVL(BSTree &T,ElemType e);功能：插入一個(gè)結(jié)點(diǎn)，如果待插入的結(jié)點(diǎn)鍵值已存在與樹中，則返回。否則找到插入位置， 插入。若因插入結(jié)點(diǎn)后使二叉樹失去平衡。則插入后根據(jù)平衡因子調(diào)用相關(guān)的函數(shù)進(jìn)行平衡化處理。說明：這是一個(gè)遞歸的過程。(3). 函數(shù)原形： void R_Rotate(BSTree &p);.功能：對以 *p 為根的二叉樹進(jìn)行右旋處理，處理后的p 指向根節(jié)點(diǎn)。(4). 函數(shù)原形： void L_Rotate(BSTree &p);功能：對以 *p 為根的二叉樹進(jìn)行左旋處理，處理后的p 指向根節(jié)點(diǎn)。(5). 函數(shù)原形： v

10、oid LeftBalance(BSTree &T);功能：對以指針 T 所指結(jié)點(diǎn)的二叉樹進(jìn)行左平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)。 T指向新的根節(jié)點(diǎn)。調(diào)用了左旋和右旋函數(shù)。(6). 函數(shù)原形： void RightBalance(BSTree &T);功能：對以指針 T 所指結(jié)點(diǎn)的二叉樹進(jìn)行右平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)。 T指向新的根節(jié)點(diǎn)。調(diào)用了左旋和右旋函數(shù)。(7). 函數(shù)原形： int Print_Mid(BSTree T);功能：采用遞歸的方式對二叉樹進(jìn)行中序輸出。(8). 函數(shù)原形： void Destory(BSTree &T);功能：此算法和遞歸遍歷十分相識。采用遞歸進(jìn)行銷毀。說明：銷毀

11、的過程中，必須先銷毀左右子樹，再銷毀根結(jié)點(diǎn)，否則先銷毀根結(jié)點(diǎn)后，左右孩子指針無法找到。銷毀后T 賦空，預(yù)留下來進(jìn)行下一次的創(chuàng)建。(9). 函數(shù)原形： int Visit(BSTree T);功能：輸出結(jié)點(diǎn)的關(guān)鍵值。成功則返回真。(10). 函數(shù)原形： int WideTraverse(BSTree T);功能 ; 進(jìn)行平衡二叉樹的層次輸出，同時(shí)可以計(jì)算出數(shù)的深度。5. 課程設(shè)計(jì)總結(jié)(1) 調(diào)試情況：由于指針處理不當(dāng)，調(diào)試過程中經(jīng)常出現(xiàn)指針出錯的情況，導(dǎo)致程序終止，經(jīng)過仔細(xì)修改后才得以改正。在程序整體設(shè)計(jì)過程中，由于忽視&的作用而導(dǎo)致程序無法正常運(yùn)行。(2). 感想：通過此次課程設(shè)計(jì)，讓我對數(shù)據(jù)

12、結(jié)構(gòu)的重要學(xué)習(xí)內(nèi)容有了更加深刻的了解，同時(shí)也意識到自己還存在很大的不足，還有很多的知識需要完善。在編程的過程中錯誤時(shí)在所難免的，處了要修改錯誤外還有了解錯誤的原因。而不是僅僅修改而已。.6. 參考文獻(xiàn)1 數(shù)據(jù)結(jié)構(gòu)（ C語言版） 嚴(yán)蔚寬 吳偉民 編著2 C 語程序設(shè)計(jì) 白燕 尹業(yè)安 編著7. 附錄：程序清單#include#include#define ERROR 0#define TRUE 1#define OK 1#define FALSE 0#define LH 1#define RH -1#define EH 0#define EQ(a,b) (a)=(b)#define LT(a,b)

13、 (a)(b)#define LQ(a,b) (a)lchild)if(Visit(T)if(Print_Mid(T-rchild)return OK;return ERROR;else return OK;int Visit(BSTree T)printf(%d ,T-data.Key);return OK;int InitQueue(LinkQueue &Q)Q.front=Q.rear=(QNodeP)malloc(sizeof(QNode);if(!Q.front)return ERROR;Q.front-next=NULL;return OK;int QueueEmpty(LinkQ

14、ueue Q)if(Q.front=Q.rear)return TRUE;else return FALSE;int EnQueue(LinkQueue &Q,BSTree p)QNodeP q=NULL;q=(QNodeP)malloc(sizeof(QNode);if(!q)return ERROR;q-e=p;q-next=NULL;.Q.rear-next=q;Q.rear=q;return OK;int DeQueue(LinkQueue &Q,BSTree &p)QNodeP q=NULL;if(Q.front=Q.rear)return ERROR;q=Q.front-next;

15、p=q-e;Q.front-next=q-next;if(!q-next)Q.rear=Q.front;free(q);return OK;int WideTraverse(BSTree T)LinkQueue Q1,Q2;BSTree p=NULL;int i=1;InitQueue(Q1);InitQueue(Q2);printf(n按層輸出： n);if(T)EnQueue(Q1,T);while(!QueueEmpty(Q1)|(!QueueEmpty(Q2)printf(第%d層 :,i);if(i%2)while(!QueueEmpty(Q1)DeQueue(Q1,p);Visit

16、(p);if(p-lchild)EnQueue(Q2,p-lchild);if(p-rchild)EnQueue(Q2,p-rchild);elsewhile(!QueueEmpty(Q2)DeQueue(Q2,p);.Visit(p);if(p-lchild)EnQueue(Q1,p-lchild);if(p-rchild)EnQueue(Q1,p-rchild);printf(n);i+;printf(該樹共有 %d層 n,i-1);return OK;int InsertAVL(BSTree &T,ElemType e)if(!T)T=(BSTree)malloc(sizeof(BSTN

17、ode);if(!T)exit(ERROR);T-data=e;T-lchild=T-rchild=NULL;T-bf=EH;taller=TRUE;elseif(EQ(e.Key,T-data.Key)taller=FALSE;printf(樹中存在此關(guān)鍵字n);return ERROR;if(LT(e.Key,T-data.Key)if(!InsertAVL(T-lchild,e)return ERROR;if(taller)switch(T-bf)case LH:LeftBalance(T);taller=FALSE;break;.case EH:T-bf=LH;taller=TRUE;

18、break;case RH:T-bf=EH;taller=FALSE;break;elseif(!InsertAVL(T-rchild,e)return ERROR;if(taller)switch(T-bf)case LH:T-bf=EH;taller=FALSE;break;case EH:T-bf=RH;taller=TRUE;break;case RH:RightBalance(T);taller=FALSE;break;return OK;void LeftBalance(BSTree &T)BSTree lc=NULL,rd=NULL;lc=T-lchild;switch(lc-bf)case LH:.T-bf=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;b