數(shù)據(jù)結(jié)構(gòu)C語言版 平衡二叉樹

《數(shù)據(jù)結(jié)構(gòu)C語言版 平衡二叉樹》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)C語言版 平衡二叉樹（7頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、/*數(shù)據(jù)結(jié)構(gòu)C語言版 平衡二叉樹 P236編譯環(huán)境：Dev-C+ 4.9.9.2日期：2011年2月15日 */#include #include #define LH +1/ 左高 #define EH 0/ 等高 #define RH -1/ 右高 #define N 5/ 數(shù)據(jù)元素個(gè)數(shù) typedef char KeyType; / 設(shè)關(guān)鍵字域?yàn)樽址?typedef structKeyType key;int order;ElemType; / 數(shù)據(jù)元素類型 / 平衡二叉樹的類型 typedef struct BSTNodeElemType data;/ bf結(jié)點(diǎn)的平衡因子,只能夠取0

2、，-1，1，它是左子樹的深度減去/ 右子樹的深度得到的int bf; struct BSTNode *lchild,*rchild; / 左、右孩子指針 BSTNode,*BSTree;/ 構(gòu)造一個(gè)空的動(dòng)態(tài)查找表DTint InitDSTable(BSTree *DT) *DT=NULL;return 1;/ 銷毀動(dòng)態(tài)查找表DT void DestroyDSTable(BSTree *DT) if(*DT) / 非空樹 if(*DT)-lchild) / 有左孩子 DestroyDSTable(&(*DT)-lchild); / 銷毀左孩子子樹 if(*DT)-rchild) / 有右孩子 D

3、estroyDSTable(&(*DT)-rchild); / 銷毀右孩子子樹 free(*DT); / 釋放根結(jié)點(diǎn) *DT=NULL; / 空指針賦0 / 算法9.5(a) / 在根指針T所指二叉排序樹中遞歸地查找某關(guān)鍵字等于key的數(shù)據(jù)元素， / 若查找成功，則返回指向該數(shù)據(jù)元素結(jié)點(diǎn)的指針,否則返回空指針。BSTree SearchBST(BSTree T,KeyType key)if(!T)| (key = T-data.key)return T; / 查找結(jié)束 else if(key data.key) / 在左子樹中繼續(xù)查找 return SearchBST(T-lchild,key

4、);elsereturn SearchBST(T-rchild,key); / 在右子樹中繼續(xù)查找 / 算法9.9 P236/ 對(duì)以*p為根的二叉排序樹作右旋處理，處理之后p指向新的樹根結(jié)點(diǎn)，即旋轉(zhuǎn) / 處理之前的左子樹的根結(jié)點(diǎn)。void R_Rotate(BSTree *p) BSTree lc;lc=(*p)-lchild; / lc指向p的左子樹根結(jié)點(diǎn) (*p)-lchild=lc-rchild; / lc的右子樹掛接為p的左子樹 lc-rchild=*p;*p=lc; / p指向新的根結(jié)點(diǎn) / 算法9.10 P236 / 對(duì)以*p為根的二叉排序樹作左旋處理，處理之后p指向新的樹根結(jié)點(diǎn)，

5、即旋轉(zhuǎn) / 處理之前的右子樹的根結(jié)點(diǎn)。void L_Rotate(BSTree *p)BSTree rc;rc=(*p)-rchild; / rc指向p的右子樹根結(jié)點(diǎn) (*p)-rchild=rc-lchild; / rc的左子樹掛接為p的右子樹 rc-lchild=*p;*p=rc; / p指向新的根結(jié)點(diǎn) / 算法9.12 P238/ 對(duì)以指針T所指結(jié)點(diǎn)為根的二叉樹作左平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)， / 指針T指向新的根結(jié)點(diǎn)。void LeftBalance(BSTree *T)BSTree lc,rd;lc=(*T)-lchild; / lc指向*T的左子樹根結(jié)點(diǎn) switch(lc-bf)

6、 / 檢查*T的左子樹的平衡度，并作相應(yīng)平衡處理 case LH: / 新結(jié)點(diǎn)插入在*T的左孩子的左子樹上，要作單右旋處理 (*T)-bf=lc-bf=EH;R_Rotate(T);break;case RH: / 新結(jié)點(diǎn)插入在*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;rd-bf=EH;L

7、_Rotate(&(*T)-lchild); / 對(duì)*T的左子樹作左旋平衡處理 R_Rotate(T); / 對(duì)*T作右旋平衡處理 / 對(duì)以指針T所指結(jié)點(diǎn)為根的二叉樹作右平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)， / 指針T指向新的根結(jié)點(diǎn)void RightBalance(BSTree *T)BSTree rc,rd;rc=(*T)-rchild; / rc指向*T的右子樹根結(jié)點(diǎn) switch(rc-bf) / 檢查*T的右子樹的平衡度，并作相應(yīng)平衡處理 case RH: / 新結(jié)點(diǎn)插入在*T的右孩子的右子樹上，要作單左旋處理 (*T)-bf=rc-bf=EH;L_Rotate(T);break;case

8、LH: / 新結(jié)點(diǎn)插入在*T的右孩子的左子樹上，要作雙旋處理 rd=rc-lchild; / rd指向*T的右孩子的左子樹根 switch(rd-bf) / 修改*T及其右孩子的平衡因子 case RH: (*T)-bf=LH;rc-bf=EH;break;case EH: (*T)-bf=rc-bf=EH;break;case LH: (*T)-bf=EH;rc-bf=RH;rd-bf=EH;R_Rotate(&(*T)-rchild); / 對(duì)*T的右子樹作右旋平衡處理 L_Rotate(T); / 對(duì)*T作左旋平衡處理 / 算法9.11 / 若在平衡的二叉排序樹T中不存在和e有相同關(guān)鍵字

9、的結(jié)點(diǎn)，則插入一個(gè) / 數(shù)據(jù)元素為e的新結(jié)點(diǎn)，并返回1，否則返回0。若因插入而使二叉排序樹 / 失去平衡，則作平衡旋轉(zhuǎn)處理，布爾變量taller反映T長(zhǎng)高與否。 int InsertAVL(BSTree *T,ElemType e,int *taller)if(!*T) / 插入新結(jié)點(diǎn)，樹“長(zhǎng)高”，置taller為1 *T=(BSTree)malloc(sizeof(BSTNode);(*T)-data=e;(*T)-lchild=(*T)-rchild=NULL;(*T)-bf=EH;*taller=1;elseif(e.key = (*T)-data.key) / 樹中已存在和e有相同關(guān)鍵

10、字的結(jié)點(diǎn)則不再插入 *taller=0;return 0;if(e.key data.key) / 應(yīng)繼續(xù)在*T的左子樹中進(jìn)行搜索 if(!InsertAVL(&(*T)-lchild,e,taller) / 未插入 return 0;if(*taller)/ 已插入到*T的左子樹中且左子樹“長(zhǎng)高” switch(*T)-bf) / 檢查*T的平衡度 case LH:/ 原本左子樹比右子樹高，需要作左平衡處理 LeftBalance(T);*taller=0;/標(biāo)志沒長(zhǎng)高break;case EH:/ 原本左、右子樹等高，現(xiàn)因左子樹增高而使樹增高 (*T)-bf=LH;*taller=1;/標(biāo)

11、志長(zhǎng)高break;case RH:/ 原本右子樹比左子樹高，現(xiàn)左、右子樹等高(*T)-bf=EH; *taller=0;/標(biāo)志沒長(zhǎng)高else/ 應(yīng)繼續(xù)在*T的右子樹中進(jìn)行搜索 if(!InsertAVL(&(*T)-rchild,e,taller) / 未插入 return 0;if(*taller) / 已插入到T的右子樹且右子樹“長(zhǎng)高” switch(*T)-bf) / 檢查T的平衡度 case LH: (*T)-bf=EH; / 原本左子樹比右子樹高，現(xiàn)左、右子樹等高 *taller=0; break; case EH: / 原本左、右子樹等高，現(xiàn)因右子樹增高而使樹增高 (*T)-bf=

12、RH; *taller=1; break; case RH: / 原本右子樹比左子樹高，需要作右平衡處理 RightBalance(T); *taller=0;return 1;/ 按關(guān)鍵字的順序?qū)T的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit()一次void TraverseDSTable(BSTree DT,void(*Visit)(ElemType) if(DT)TraverseDSTable(DT-lchild,Visit); / 先中序遍歷左子樹 Visit(DT-data); / 再訪問根結(jié)點(diǎn) TraverseDSTable(DT-rchild,Visit); / 最后中序遍歷右子樹 void

13、print(ElemType c)printf(%d,%d),c.key,c.order);int main()BSTree dt,p;int k;int i;KeyType j;ElemType rN=13,1,24,2,37,3,90,4,53,5; / (以教科書P234圖9.12為例) InitDSTable(&dt);/ 初始化空樹 for(i=0;idata);elseprintf(表中不存在此值);printf(n);DestroyDSTable(&dt);system(pause);return 0;/*輸出效果：(13,1)(24,2)(37,3)(53,5)(90,4)請(qǐng)輸入待查找的關(guān)鍵字: 53(53,5)請(qǐng)按任意鍵繼續(xù). . . */