寫在前面：博主是一位普普通通的19屆雙非軟工在讀生，平時最大的愛好就是聽聽歌，逛逛B站。博主很喜歡的一句話花開堪折直須折，莫待無花空折枝：博主的理解是頭一次為人，就應(yīng)該做自己想做的事，做自己不后悔的事，做自己以后不會留有遺憾的事，做自己覺得有意義的事，不浪費這大好的青春年華。博主寫博客目的是記錄所學(xué)到的知識并方便自己復(fù)習(xí)，在記錄知識的同時獲得部分瀏覽量，得到更多人的認(rèn)可，滿足小小的成就感，同時在寫博客的途中結(jié)交更多志同道合的朋友，讓自己在技術(shù)的路上并不孤單。

目錄:
1.平衡二叉樹簡介
2.二叉排序樹轉(zhuǎn)換平衡為平衡二叉樹
3.不平衡因子的四種情況
4.構(gòu)建平衡二叉樹的代碼實現(xiàn)

1.平衡二叉樹簡介

平衡二叉樹，又稱為 AVL 樹。實際上就是遵循以下兩個特點的二叉樹：

• 每棵子樹中的左子樹和右子樹的深度差不能超過 1；
• 二叉樹中每棵子樹都要求是平衡二叉樹；

其實就是在二叉樹的基礎(chǔ)上，若樹中每棵子樹都滿足其左子樹和右子樹的深度差都不超過 1，則這棵二叉樹就是平衡二叉樹。

如下圖所示，其中 （a） 的兩棵二叉樹中由于各個結(jié)點的平衡因子數(shù)的絕對值都不超過 1，所以 （a） 中兩棵二叉樹都是平衡二叉樹；而 （b） 的兩棵二叉樹中有結(jié)點的平衡因子數(shù)的絕對值超過 1，所以都不是平衡二叉樹。

平衡因子：每個結(jié)點都有其各自的平衡因子，表示的就是其左子樹深度同右子樹深度的差。平衡二叉樹中各結(jié)點平衡因子的取值只可能是：0、1 和 -1。

2.二叉排序樹轉(zhuǎn)換平衡為平衡二叉樹

為了排除動態(tài)查找表中不同的數(shù)據(jù)排列方式對算法性能的影響，需要考慮在不會破壞二叉排序樹本身結(jié)構(gòu)的前提下，將二叉排序樹轉(zhuǎn)化為平衡二叉樹。

例如，使用上一節(jié)的算法在對查找表{13，24，37，90，53}構(gòu)建二叉排序樹時，當(dāng)插入 13 和 24 時，二叉排序樹此時還是平衡二叉樹：

當(dāng)繼續(xù)插入 37 時，生成的二叉排序樹如下圖 （a），平衡二叉樹的結(jié)構(gòu)被破壞，此時只需要對二叉排序樹做“旋轉(zhuǎn)”操作（如下圖 （b）），即整棵樹以結(jié)點 24 為根結(jié)點，二叉排序樹的結(jié)構(gòu)沒有破壞，同時將該樹轉(zhuǎn)化為了平衡二叉樹：

當(dāng)二叉排序樹的平衡性被打破時，就如同扁擔(dān)的兩頭出現(xiàn)了一頭重一頭輕的現(xiàn)象，如下圖（a）所示，此時只需要改變扁擔(dān)的支撐點（樹的樹根），就能使其重新歸為平衡。實際上圖b中的 （b） 是對（a） 的二叉樹做了一個向左逆時針旋轉(zhuǎn)的操作。

繼續(xù)插入 90 和 53 后，二叉排序樹如下圖（a）所示，導(dǎo)致二叉樹中結(jié)點 24 和 37 的平衡因子的絕對值大于 1 ，整棵樹的平衡被打破。此時，需要做兩步操作：

如下圖（b） 所示，將結(jié)點 53 和 90 整體向右順時針旋轉(zhuǎn)，使本該以 90 為根結(jié)點的子樹改為以結(jié)點 53 為根結(jié)點；

如下圖 （c） 所示，將以結(jié)點 37 為根結(jié)點的子樹向左逆時針旋轉(zhuǎn)，使本該以 37 為根結(jié)點的子樹，改為以結(jié)點 53 為根結(jié)點；

做完以上操作，即完成了由不平衡的二叉排序樹轉(zhuǎn)變?yōu)槠胶舛鏄洹?/p>

3.不平衡因子的四種情況

1.單向右旋平衡處理：若由于結(jié)點 a 的左子樹為根結(jié)點的左子樹上插入結(jié)點，導(dǎo)致結(jié)點 a 的平衡因子由 1 增至 2，致使以 a 為根結(jié)點的子樹失去平衡，則只需進(jìn)行一次向右的順時針旋轉(zhuǎn)，如下圖這種情況：

2.單向左旋平衡處理：如果由于結(jié)點 a 的右子樹為根結(jié)點的右子樹上插入結(jié)點，導(dǎo)致結(jié)點 a 的平衡因子由 -1變?yōu)?-2，則以 a 為根結(jié)點的子樹需要進(jìn)行一次向左的逆時針旋轉(zhuǎn)，如下圖這種情況：

3.雙向旋轉(zhuǎn)（先左后右）平衡處理：如果由于結(jié)點 a 的左子樹為根結(jié)點的右子樹上插入結(jié)點，導(dǎo)致結(jié)點 a 平衡因子由 1 增至 2，致使以 a 為根結(jié)點的子樹失去平衡，則需要進(jìn)行兩次旋轉(zhuǎn)操作，如下圖這種情況：

上圖中插入結(jié)點也可以為結(jié)點 C 的右孩子，則（b）中插入結(jié)點的位置還是結(jié)點 C 右孩子，（c）中插入結(jié)點的位置為結(jié)點 A 的左孩子。

4.雙向旋轉(zhuǎn)（先右后左）平衡處理：如果由于結(jié)點 a 的右子樹為根結(jié)點的左子樹上插入結(jié)點，導(dǎo)致結(jié)點 a 平衡因子由 -1 變?yōu)?-2，致使以 a 為根結(jié)點的子樹失去平衡，則需要進(jìn)行兩次旋轉(zhuǎn)（先右旋后左旋）操作，如下圖這種情況：

上圖中插入結(jié)點也可以為結(jié)點 C 的右孩子，則（b）中插入結(jié)點的位置改為結(jié)點 B 的左孩子，（c）中插入結(jié)點的位置為結(jié)點 B 的左孩子

4.構(gòu)建平衡二叉樹的代碼實現(xiàn)

#include <stdio.h> #include <stdlib.h> //分別定義平衡因子數(shù) #define LH +1 #define EH 0 #define RH -1 typedef int ElemType; typedef enum {false,true} bool; //定義二叉排序樹 typedef struct BSTNode{ElemType data;int bf;//balance flagstruct BSTNode *lchild,*rchild; }*BSTree,BSTNode; //對以 p 為根結(jié)點的二叉樹做右旋處理，令 p 指針指向新的樹根結(jié)點 void R_Rotate(BSTree* p) {//借助文章中的圖 5 所示加以理解，其中結(jié)點 A 為 p 指針指向的根結(jié)點BSTree lc = (*p)->lchild;(*p)->lchild = lc->rchild;lc->rchild = *p;*p = lc; } 對以 p 為根結(jié)點的二叉樹做左旋處理，令 p 指針指向新的樹根結(jié)點 void L_Rotate(BSTree* p) {//借助文章中的圖 6 所示加以理解，其中結(jié)點 A 為 p 指針指向的根結(jié)點BSTree rc = (*p)->rchild;(*p)->rchild = rc->lchild;rc->lchild = *p;*p = rc; } //對以指針 T 所指向結(jié)點為根結(jié)點的二叉樹作左子樹的平衡處理，令指針 T 指向新的根結(jié)點 void LeftBalance(BSTree* T) {BSTree lc,rd;lc = (*T)->lchild;//查看以 T 的左子樹為根結(jié)點的子樹，失去平衡的原因，如果 bf 值為 1 ，則說明添加在左子樹為根結(jié)點的左子樹中，需要對其進(jìn)行右旋處理；反之，如果 bf 值為 -1，說明添加在以左子樹為根結(jié)點的右子樹中，需要進(jìn)行雙向先左旋后右旋的處理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;break;}rd->bf = EH;L_Rotate(&(*T)->lchild);R_Rotate(T);break;} } //右子樹的平衡處理同左子樹的平衡處理完全類似 void RightBalance(BSTree* T) {BSTree lc,rd;lc= (*T)->rchild;switch (lc->bf){case RH:(*T)->bf = lc->bf = EH;L_Rotate(T);break;case LH:rd = lc->lchild;switch(rd->bf){case LH:(*T)->bf = EH;lc->bf = RH;break;case EH:(*T)->bf = lc->bf = EH;break;case RH:(*T)->bf = EH;lc->bf = LH;break;}rd->bf = EH;R_Rotate(&(*T)->rchild);L_Rotate(T);break;} }int InsertAVL(BSTree* T,ElemType e,bool* taller) {//如果本身為空樹，則直接添加 e 為根結(jié)點if ((*T)==NULL){(*T)=(BSTree)malloc(sizeof(BSTNode));(*T)->bf = EH;(*T)->data = e;(*T)->lchild = NULL;(*T)->rchild = NULL;*taller=true;}//如果二叉排序樹中已經(jīng)存在 e ，則不做任何處理else if (e == (*T)->data){*taller = false;return 0;}//如果 e 小于結(jié)點 T 的數(shù)據(jù)域，則插入到 T 的左子樹中else if (e < (*T)->data){//如果插入過程，不會影響樹本身的平衡，則直接結(jié)束if(!InsertAVL(&(*T)->lchild,e,taller))return 0;//判斷插入過程是否會導(dǎo)致整棵樹的深度 +1if(*taller){//判斷根結(jié)點 T 的平衡因子是多少，由于是在其左子樹添加新結(jié)點的過程中導(dǎo)致失去平衡，所以當(dāng) T 結(jié)點的平衡因子本身為 1 時，需要進(jìn)行左子樹的平衡處理，否則更新樹中各結(jié)點的平衡因子數(shù)switch ((*T)->bf){case LH:LeftBalance(T);*taller = false;break;case EH:(*T)->bf = LH;*taller = true;break;case RH:(*T)->bf = EH;*taller = false;break;}}}//同樣，當(dāng) e>T->data 時，需要插入到以 T 為根結(jié)點的樹的右子樹中，同樣需要做和以上同樣的操作else{if(!InsertAVL(&(*T)->rchild,e,taller))return 0;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 1; } //判斷現(xiàn)有平衡二叉樹中是否已經(jīng)具有數(shù)據(jù)域為 e 的結(jié)點 bool FindNode(BSTree root,ElemType e,BSTree* pos) {BSTree pt = root;(*pos) = NULL;while(pt){if (pt->data == e){//找到節(jié)點，pos指向該節(jié)點并返回true(*pos) = pt;return true;}else if (pt->data>e){pt = pt->lchild;}elsept = pt->rchild;}return false; } //中序遍歷平衡二叉樹 void InorderTra(BSTree root) {if(root->lchild)InorderTra(root->lchild);printf("%d ",root->data);if(root->rchild)InorderTra(root->rchild); }int main() {int i,nArr[] = {1,23,45,34,98,9,4,35,23};BSTree root=NULL,pos;bool taller;//用 nArr查找表構(gòu)建平衡二叉樹（不斷插入數(shù)據(jù)的過程）for (i=0;i<9;i++){InsertAVL(&root,nArr[i],&taller);}//中序遍歷輸出InorderTra(root);//判斷平衡二叉樹中是否含有數(shù)據(jù)域為 103 的數(shù)據(jù)if(FindNode(root,103,&pos))printf("\n%d\n",pos->data);elseprintf("\nNot find this Node\n");return 0; }

本篇博客轉(zhuǎn)載C語言中文網(wǎng)

總結(jié)

以上是生活随笔為你收集整理的平衡二叉排序树(完整案例详解及完整C代码实现)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。