1、計算機科學(xué)與技術(shù)系課程設(shè)計說明書二叉平衡排序樹摘要 問題描述：從一棵空樹開始創(chuàng)建，在創(chuàng)建過程中，保證樹的有序性，同排序樹?；疽螅?.創(chuàng)建（插入、調(diào)整、改組）2.輸出開發(fā)工具:windows XP操作系統(tǒng),Microsoft visual c+ 6.0 編譯系統(tǒng);關(guān)鍵詞：C+ ;目的:1.熟悉掌握二叉樹的基本操作2.熟悉二叉樹的創(chuàng)建(插入、調(diào)整、改組),輸出以及把二叉排序樹轉(zhuǎn)換為二叉平衡排序樹3.更進一步掌握有關(guān)二叉排序樹的操作意義:業(yè)研究和項目開發(fā)的寶貴實踐機會，為今后的工作積累經(jīng)驗。第1頁共20計算機科學(xué)與技術(shù)系課程設(shè)計說明書主要算法說明:1.主要數(shù)據(jù)結(jié)構(gòu)定義typedef struct

2、 node node ;Struct nodeNode*parent;Node*left;Node*right;Int balance;/左右子樹高度之差I(lǐng)nt key;2.主要函數(shù)說明Int scarchNode(int key, node* root, node*parent):按key查找結(jié)點Node* minNode(node* root):樹root的最小結(jié)點Node* maxNode(node* root):樹root的最大結(jié)點Node* preNode(node* target):求前驅(qū)結(jié)點Node* nextNode(node* targer):求后繼結(jié)點node* adjus

3、tAVL(node* root, node* parent, node* 的平衡性Node* insertNode(int key, node* root):插入Node* deletevode(int key, node* root):刪除Node*createAVL(int* data, int size):創(chuàng)建新的二叉樹Void interordertraverse (node*root):中序遍歷Void preordertraverse(node* root):先序遍歷3.二叉排序樹的插入和刪除a.二叉排序樹的插入在二叉排序樹插入新結(jié)點,要保證插入后的二叉樹仍符合二叉排序樹的定義插入

4、過程:若二叉排序樹正存在,則返回根結(jié)點;第2頁共20計算機科學(xué)與技術(shù)系課程設(shè)計說明書當結(jié)點不存在時,將待插入到根結(jié)點的關(guān)鍵字key和樹根關(guān)鍵字parent-key 進行比較.若 keykey,則插入到根的左子樹中,否則,插入到根的右子樹中.而子樹中的插入過程和在樹中的插入過程相同,如此進行下去,直到把結(jié)點作為一個新的樹葉插入到二叉排序樹中或者直到發(fā)現(xiàn)樹已有相同關(guān)鍵字的結(jié)點為止,并且注意二叉樹的平衡,時刻調(diào)整.b.二叉排序樹的刪除假設(shè)在二叉排序樹上被刪結(jié)點為*tp,其雙親結(jié)點為*parent,且不失一般性,可設(shè)*parent是*parent-left的左孩子.下面分了3種情況進行討論:(1).若

5、*parent結(jié)點為葉子結(jié)點,即PL和PR均為空樹.由于刪去葉子結(jié)點不破壞整棵樹的結(jié)構(gòu),則只需要修改其雙親,結(jié)構(gòu)點的指針即可.(2).若*parent結(jié)點凡有左子樹PL或者只有右子樹PR,此時只要令PL或PR直接成為其雙親結(jié)點*f的左子樹即可.顯然,作此修改也不破壞二叉排序樹的特性.(3).若*parent結(jié)點的左子樹均不空,并且注意二叉樹的平衡性,時刻調(diào)整.4.中序遍歷和先序遍歷Void interordertraverse(node* root)/中序遍歷If(root 1=NULL)Interordertraverse(root-left);Printf(%d,%dn,root-key,

6、root-balance);Interordertraverse(root-right);Void preordertraverse (node* root)/先序遍歷If (root!=NULL)Printf(%d,%dn,root-key,root-balance);Preorderstraverse(root-left);第3頁共205. 1 計算機科學(xué)與技術(shù)系課程設(shè)計說明書圖34） X A B A B B A B X A B A B B A B X A 以X B 從X X B X X A ( X ) 。 X A 以X B 從X X B X X A ( X ) 。7.調(diào)整叉樹的平衡性No

7、de* adjustAVL(node* root,node* parent, node*child)主要有四種調(diào)整類型根據(jù)平衡因子主要有LR,LL,RL,RR.(1)根據(jù)parent-balance的值為2時,child-balance=-1時是LR型,否則為LL型.(2)Parent-balance的值為-2時,child-balance=1時是RL型,否則為RR型.8.程序代碼設(shè)計：(代碼部分詳見附錄)第5頁共20365計算機科學(xué)與技術(shù)系課程設(shè)計說明書重點: n 樹難點:第9頁共20計算機科學(xué)與技術(shù)系課程設(shè)計說明書本課程設(shè)計的完成，首先感謝母校河北工程大學(xué)的辛勤培育之恩。感謝劉云老師。我的

8、系統(tǒng)得以進一步的完善。在此也向他們表示由衷的感謝。順利完成。 7 第10頁共20計算機科學(xué)與技術(shù)系課程設(shè)計說明書#include #include /cout#include /setw# define LH 1# define EH 0# define RH -1/左高/等高/右高# define TRUE 1# define FALSE 0int taller=0;/taller反映 T 長高與否/二叉排序樹的類型定義typedef struct BSTNodeint data;int bf;/結(jié)點值/結(jié)點的平衡因子struct BSTNode * lchild, * rchild; /分

9、別指向左右孩子的指針BSTNode, *BSTree; /同時聲明一個BSTNode和一個指針類型的*BSTree/樹的中序遍歷的遞歸算法,一并輸出它的平衡因子和左右結(jié)點值void MidOrder(BSTree T)/中序遍歷的特點是：當二叉樹為空，則空操作；否則/1.中序遍歷左子樹；/2.訪問根結(jié)點；/3.中序遍歷右子樹。if(T-lchild) MidOrder(T-lchild);if(T-data) /以適當?shù)男问礁袷交敵龈鱾€結(jié)點及其附加信息可以方便用戶重構(gòu)二叉樹coutsetw(4)datasetw(6)bf;if(T-lchild)coutsetw(8)lchild-data;

10、elseelsecoutsetw(8)rchild)coutsetw(8)rchild-data;coutsetw(8)-;coutrchild) MidOrder(T-rchild);第頁共20計算機科學(xué)與技術(shù)系課程設(shè)計說明書/對以 p 為根的樹作右旋處理，處理之 p 指向新的樹根結(jié)點即旋轉(zhuǎn)處理之前的左子樹根結(jié)點BSTree R_Rotate(BSTree p)BSTNode *lc;lc=p-lchild;/聲明 BSTNode* 臨時變量/lc 指向的*p 的左子樹根結(jié)點p-lchild=lc-rchild; /lc 的右子樹掛接為*p 的左子樹lc-rchild=p;p=lc;retu

11、rn p;/p 指向新的根結(jié)點/返回新的根結(jié)點/對以 p 為根的樹作左旋處理，處理之 p 指向新的樹根結(jié)點即旋轉(zhuǎn)處理之前的右子樹根結(jié)點BSTree L_Rotate(BSTree p)BSTNode *rc;rc=p-rchild;/聲明 BSTNode* 臨時變量/rc指向的*p 的右子樹根結(jié)點p-rchild=rc-lchild; /rc的左子樹掛接為*p 的右子樹rc-lchild=p;p=rc;return p;/p 指向新的根結(jié)點/返回新的根結(jié)點/對以指針 T 所指結(jié)點為根的二叉樹作左平衡旋轉(zhuǎn)處理，本算法結(jié)束時指針T指向新的根結(jié)點BSTree LeftBalance(BSTree T

12、)BSTNode *lc,*rd;lc=T-lchild;switch(lc-bf)/lc 指向*T 的左子樹根結(jié)點/檢查*T 的左子樹平衡度，并做相應(yīng)的平衡處理case LH:/新結(jié)點插入在*T 的左孩子的左子樹上，要做單右旋處理T-bf=lc-bf=EH;T=R_Rotate(T);break;case RH:/新結(jié)點插入在*T 的左孩子的右子樹上，要做雙旋處理rd=lc-rchild;switch(rd-bf)/rd 指向*T 的左孩子的右子樹根/修改*T 及其左孩子的平衡因子case LH:第12頁共20計算機科學(xué)與技術(shù)系課程設(shè)計說明書T-bf=RH;lc-bf=EH;break;ca

13、se EH:T-bf=lc-bf=EH;break;case RH:T-bf=EH;lc-bf=LH;break;rd-bf=EH;T-lchild=L_Rotate(T-lchild); /對*T 的左孩子做左旋平衡處理T=R_Rotate(T);/對*T 做右旋處理return T;/對以指針 T 所指結(jié)點為根的二叉樹作右平衡旋轉(zhuǎn)處理，本算法結(jié)束時指針T指向新的根結(jié)點BSTree RightBalance(BSTree T)BSTree rc,ld;rc=T-rchild;switch(rc-bf)處理/rc指向*T 的右子樹根結(jié)點/檢查*T 的右子樹平衡度，并做相應(yīng)的平衡case RH:

14、/新結(jié)點插入在*T 的右孩子的右子樹上，要做單右旋處理T-bf=rc-bf=EH;T=L_Rotate(T);break;case LH:/新結(jié)點插入在*T 的右孩子的左子樹上，要做雙旋處理ld=rc-lchild;switch(ld-bf)/ld 指向*T的右孩子的左子樹根/修改*T 及其右孩子的平衡因子case LH:T-bf=LH;rc-bf=EH;break;case EH:T-bf=rc-bf=EH;第13頁共20計算機科學(xué)與技術(shù)系課程設(shè)計說明書break;case RH:T-bf=EH;rc-bf=RH;break;ld-bf=EH;T-rchild=R_Rotate(T-rchi

15、ld); /對*T 的右孩子做右旋平衡處理T=L_Rotate(T);/對*T 做左旋處理return T;/若在平衡的二叉排序樹 T 中不存在和 e有相同關(guān)鍵字的結(jié)點,則插入一個數(shù)據(jù)元素為 e的新結(jié)點,并返回插入后所建成的平衡二叉排序樹,否則返回 NULL.若因插入而使二叉數(shù)失去平衡,則作平衡旋轉(zhuǎn)處理,布爾變量 taller反映 T 長高與否BSTree T, int e)BSTree p;/插入新結(jié)點，樹長高置 taller為 TRUEif(!T)T=(BSTree)malloc(sizeof(BSTNode);T-data=e;T-lchild=T-rchild=NULL;T-bf=EH

16、;taller=TRUE;else/樹中存在和 e有相同關(guān)鍵字的結(jié)點則不再插入if(e=T-data)taller=FALSE;return NULL;/值小于則繼續(xù)在樹的左子樹中搜索if(e data)/插入到左子樹且左子樹長高if(p)T-lchild=p;第14頁共20計算機科學(xué)與技術(shù)系課程設(shè)計說明書if(taller)switch(T-bf)/檢查*T 的平衡度case LH:/原本左子樹比右子樹高，需要做左平衡處理T=LeftBalance(T);taller=FALSE;break;case EH:/原本左、右子樹同高，現(xiàn)/原本右子樹比左子樹高，因左子樹爭高而使樹增高現(xiàn)在左右子樹等

17、高T-bf=LH;taller=TRUE;break;case RH:T-bf=EH;taller=FALSE;break;/繼續(xù)在*T 的右子樹中搜索else/插入到右子樹且使右子樹長高if (p)T-rchild=p;if(taller)switch(T-bf)/檢查*T 的平衡度case LH:/原本左子樹比右子樹高，現(xiàn)在左右子樹等高T-bf=EH;taller=FALSE;break;case EH:/原本左、右子樹同高，現(xiàn)因右子樹增高而使樹增高T-bf=RH;taller=TRUE;第15頁共20計算機科學(xué)與技術(shù)系課程設(shè)計說明書break;case RH:/原本右子樹比左子樹高，需要

18、做右平衡處理T=RightBalance(T);taller=FALSE;break;return T;/建立新結(jié)點BSTree CreatNode(int nodeValue)BSTree node;node = (BSTree)malloc(sizeof(BSTree);node-data = nodeValue;node-bf = 0;node-lchild = NULL;node-rchild = NULL;return node;/在屏幕打印菜單函數(shù)int PrintMenu()int userChose;cout - endl;cout 1. 創(chuàng)建一棵二叉排序樹 endl;cout

19、 2. 向排序樹插入新結(jié)點轉(zhuǎn)化成平衡樹 endl;cout 3. 中序遍歷輸出平衡樹 endl;cout n. 選擇其它將退出程序 endl;cout - endl;cout userChose;return userChose;/新建二叉樹函數(shù)BSTree BuildTree(BSTree r)第16頁共20計算機科學(xué)與技術(shù)系課程設(shè)計說明書/如果傳入根結(jié)點不為空，則樹已構(gòu)建過，退出函數(shù)if (r != NULL)cout 二叉平衡樹已經(jīng)創(chuàng)建!;return NULL;/根結(jié)點為空則開始構(gòu)建cout 請輸入結(jié)點值，輸入零則結(jié)束 nodeValue;while (nodeValue) /插入任何不為 0 的整數(shù)值BSTree