平衡二叉樹:保持子樹深度不會超過1
實現(xiàn)：
#include#include
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100? ? ? ? ? ? ? ? ? ? /* 存儲空間初始分配量 */
typedef int Status;? ? ? ? ? ? ? ? ? ? /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */
/* 二叉樹的二叉鏈表結(jié)點結(jié)構(gòu)定義 */
typedef? struct BitNode? ? ? ? ? ? ? ? /* 結(jié)點結(jié)構(gòu) */
{
? ? int data;? ? ? ? ? ? ? ? ? ? ? ? ? /* 結(jié)點數(shù)據(jù) */
? ? int bf;? ? ? ? ? ? ? ? ? ? ? ? ? ? /*? 結(jié)點的平衡因子 */
? ? struct BitNode *lchild, *rchild;? ? /* 左右孩子指針 */
} BitNode, *BiTree;
/* 對以p為根的二叉排序樹作右旋處理 */
/* 處理之后p指向新的樹根結(jié)點，即旋轉(zhuǎn)處理之前的左子樹的根結(jié)點 */
//右旋-順時針旋轉(zhuǎn)(如LL型就得對根結(jié)點做該旋轉(zhuǎn))
void R_Rotate(BiTree *P)
{
? ? BiTree L;
? ? L=(*P)->lchild;? ? ? ? ? ? ? ? ? ? ? /*? L指向P的左子樹根結(jié)點 */
? ? (*P)->lchild=L->rchild;? ? ? ? ? ? ? /*? L的右子樹掛接為P的左子樹 */
? ? L->rchild=(*P);
? ? *P=L;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? /*? P指向新的根結(jié)點 */
}
/* 對以P為根的二叉排序樹作左旋處理总处， */
/* 處理之后P指向新的樹根結(jié)點择诈，即旋轉(zhuǎn)處理之前的右子樹的根結(jié)點0? */
//左旋-逆時針旋轉(zhuǎn)(如RR型就得對根結(jié)點做該旋轉(zhuǎn))
void L_Rotate(BiTree *P)
{
? ? BiTree R;
? ? R = (*P)->rchild;? ? ? ? ? ? ? ? ? ? /* R指向P的右子樹根結(jié)點 */
? ? (*P)->rchild = R->lchild;? ? ? ? /* R的左子樹掛接為P的右子樹 */
? ? R->lchild = (*P);
? ? *P = R;? ? ? ? ? ? ? ? ? ? ? ? ? ? /* P指向新的根結(jié)點 */
}
#define LH +1? ? ? ? ? ? ? ? ? ? ? ? ? /*? 左高 */
#define EH 0? ? ? ? ? ? ? ? ? ? ? ? ? ? /*? 等高 */
#define RH -1? ? ? ? ? ? ? ? ? ? ? ? ? /*? 右高 */
/*? 對以指針T所指結(jié)點為根的二叉樹作左平衡旋轉(zhuǎn)處理 */
/*? 本算法結(jié)束時昙篙，指針T指向新的根結(jié)點 */
void LeftBalance(BiTree *T)
{
? ? BiTree L,Lr;
? ? L = (*T)->lchild;? ? ? ? ? ? ? ? ? ? /*? L指向T的左子樹根結(jié)點 */
? ? switch(L->bf)
? ? {
? ? ? ? /* 檢查T的左子樹的平衡度昧旨，并作相應(yīng)平衡處理 */
? ? ? ? case LH:? ? ? ? ? ? ? ? ? ? ? ? /* 新結(jié)點插入在T的左孩子的左子樹上，要作單右旋處理 */
? ? ? ? ? ? (*T)->bf=L->bf=EH;
? ? ? ? ? ? R_Rotate(T);
? ? ? ? ? ? break;
? ? ? ? case RH:? ? ? ? ? ? ? ? ? ? ? ? /* 新結(jié)點插入在T的左孩子的右子樹上请祖，要作雙旋處理 */ //
? ? ? ? ? ? Lr=L->rchild;? ? ? ? ? ? ? ? /* Lr指向T的左孩子的右子樹根 */
? ? ? ? ? ? switch(Lr->bf)
? ? ? ? ? ? {?
? ? ? ? ? ? ? ? /* 修改T及其左孩子的平衡因子 */
? ? ? ? ? ? ? ? case LH:
? ? ? ? ? ? ? ? ? ? (*T)->bf=RH;
? ? ? ? ? ? ? ? ? ? L->bf=EH;
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? case EH:
? ? ? ? ? ? ? ? ? ? (*T)->bf=L->bf=EH;
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? case RH:
? ? ? ? ? ? ? ? ? ? (*T)->bf=EH;
? ? ? ? ? ? ? ? ? ? L->bf=LH;
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? ? ? Lr->bf=EH;
? ? ? ? ? ? L_Rotate(&(*T)->lchild); /* 對T的左子樹作左旋平衡處理 */
? ? ? ? ? ? R_Rotate(T);? ? ? ? ? ? ? ? /* 對T作右旋平衡處理 */
? ? }
}
/*? 對以指針T所指結(jié)點為根的二叉樹作右平衡旋轉(zhuǎn)處理您机， */
/*? 本算法結(jié)束時穿肄，指針T指向新的根結(jié)點 */
void RightBalance(BiTree *T)
{
? ? BiTree R,Rl;
? ? R=(*T)->rchild;? ? ? ? ? ? ? ? ? ? ? /*? R指向T的右子樹根結(jié)點 */
? ? switch(R->bf)
? ? {
? ? ? ? /*? 檢查T的右子樹的平衡度，并作相應(yīng)平衡處理 */
? ? ? ? case RH:? ? ? ? ? ? ? ? ? ? ? ? /*? 新結(jié)點插入在T的右孩子的右子樹上际看，要作單左旋處理 */
? ? ? ? ? ? (*T)->bf=R->bf=EH;
? ? ? ? ? ? L_Rotate(T);
? ? ? ? ? ? break;
? ? ? ? case LH:? ? ? ? ? ? ? ? ? ? ? ? /*? 新結(jié)點插入在T的右孩子的左子樹上咸产，要作雙旋處理 */ //最小不平衡樹的根結(jié)點為負(fù)，其右孩子為正
? ? ? ? ? ? Rl=R->lchild;? ? ? ? ? ? ? ? /*? Rl指向T的右孩子的左子樹根 */
? ? ? ? ? ? switch(Rl->bf)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? /*? 修改T及其右孩子的平衡因子 */
? ? ? ? ? ? ? ? case RH:
? ? ? ? ? ? ? ? ? ? (*T)->bf=LH;
? ? ? ? ? ? ? ? ? ? R->bf=EH;
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? case EH:
? ? ? ? ? ? ? ? ? ? (*T)->bf=R->bf=EH;
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? case LH:
? ? ? ? ? ? ? ? ? ? (*T)->bf=EH;
? ? ? ? ? ? ? ? ? ? R->bf=RH;
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? ? ? Rl->bf=EH;
? ? ? ? ? ? R_Rotate(&(*T)->rchild); /*? 對T的右子樹作右旋平衡處理 */
? ? ? ? ? ? L_Rotate(T);? ? ? ? ? ? ? ? /*? 對T作左旋平衡處理 */
? ? }
}
/*? 若在平衡的二叉排序樹T中不存在和e有相同關(guān)鍵字的結(jié)點仲闽，則插入一個 */
/*? 數(shù)據(jù)元素為e的新結(jié)點脑溢，并返回1，否則返回0赖欣。若因插入而使二叉排序樹 */
/*? 失去平衡屑彻，則作平衡旋轉(zhuǎn)處理，布爾變量taller反映T長高與否顶吮。 */
Status InsertAVL(BiTree *T,int e,Status *taller)
{?
? ? if(!*T)
? ? {
? ? ? ? /*? 插入新結(jié)點社牲，樹“長高”，置taller為TRUE */
? ? ? ? *T=(BiTree)malloc(sizeof(BitNode));
? ? ? ? (*T)->data=e;
? ? ? ? (*T)->lchild=(*T)->rchild=NULL;
? ? ? ? (*T)->bf=EH;
? ? ? ? *taller=TRUE;
? ? }
? ? else
? ? {
? ? ? ? if (e==(*T)->data)
? ? ? ? {
? ? ? ? ? ? /*? 樹中已存在和e有相同關(guān)鍵字的結(jié)點則不再插入 */
? ? ? ? ? ? *taller=FALSE;
? ? ? ? ? ? return FALSE;
? ? ? ? }
? ? ? ? if (e<(*T)->data)
? ? ? ? {
? ? ? ? ? ? /*? 應(yīng)繼續(xù)在T的左子樹中進(jìn)行搜索 */
? ? ? ? ? ? if(!InsertAVL(&(*T)->lchild, e, taller)) /*? 未插入 */
? ? ? ? ? ? ? ? return FALSE;
? ? ? ? ? ? if(*taller)? ? ? ? ? ? ? ? ? ? ? ? ? ? /*? 已插入到T的左子樹中且左子樹“長高” */
? ? ? ? ? ? ? ? switch((*T)->bf)? ? ? ? ? ? ? ? /*? 檢查T的平衡度 */
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? case LH:? ? ? ? ? ? ? ? ? ? ? ? /*? 原本左子樹比右子樹高悴了，需要作左平衡處理 */
? ? ? ? ? ? ? ? ? ? ? ? LeftBalance(T);
? ? ? ? ? ? ? ? ? ? ? ? *taller=FALSE;
? ? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? ? ? case EH:? ? ? ? ? ? ? ? ? ? ? ? /*? 原本左搏恤、右子樹等高，現(xiàn)因左子樹增高而使樹增高 */
? ? ? ? ? ? ? ? ? ? ? ? (*T)->bf=LH;
? ? ? ? ? ? ? ? ? ? ? ? *taller=TRUE;
? ? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? ? ? case RH:? ? ? ? ? ? ? ? ? ? ? ? /*? 原本右子樹比左子樹高湃交，現(xiàn)左熟空、右子樹等高 */
? ? ? ? ? ? ? ? ? ? ? ? (*T)->bf=EH;
? ? ? ? ? ? ? ? ? ? ? ? *taller=FALSE;
? ? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? }
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? /*? 應(yīng)繼續(xù)在T的右子樹中進(jìn)行搜索 */
? ? ? ? ? ? if(!InsertAVL(&(*T)->rchild,e, taller)) /*? 未插入 */
? ? ? ? ? ? {
? ? ? ? ? ? ? ? return FALSE;
? ? ? ? ? ? }
? ? ? ? ? ? if(*taller)? ? ? ? ? ? ? ? ? ? ? ? ? ? /*? 已插入到T的右子樹且右子樹“長高” */
? ? ? ? ? ? {
? ? ? ? ? ? ? ? switch((*T)->bf)? ? ? ? ? ? ? ? /*? 檢查T的平衡度 */
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? case LH:? ? ? ? ? ? ? ? ? ? ? ? /*? 原本左子樹比右子樹高，現(xiàn)左搞莺、右子樹等高 */
? ? ? ? ? ? ? ? ? ? ? ? (*T)->bf=EH;
? ? ? ? ? ? ? ? ? ? ? ? *taller=FALSE;?
? ? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? ? ? case EH:? ? ? ? ? ? ? ? ? ? ? ? /*? 原本左息罗、右子樹等高，現(xiàn)因右子樹增高而使樹增高? */
? ? ? ? ? ? ? ? ? ? ? ? (*T)->bf=RH;
? ? ? ? ? ? ? ? ? ? ? ? *taller=TRUE;
? ? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? ? ? case RH:? ? ? ? ? ? ? ? ? ? ? ? /*? 原本右子樹比左子樹高才沧，需要作右平衡處理 */
? ? ? ? ? ? ? ? ? ? ? ? RightBalance(T);
? ? ? ? ? ? ? ? ? ? ? ? *taller=FALSE;
? ? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? return TRUE;
}
/*
若在平衡的二叉排序樹t中存在和e有相同關(guān)鍵字的結(jié)點阱当，則刪除之
并返回TRUE俏扩，否則返回FALSE。若因刪除而使二叉排序樹
失去平衡弊添，則作平衡旋轉(zhuǎn)處理，布爾變量shorter反映t變矮與否
*/
int deleteAVL(BiTree *t, int key, int *shorter)
{
? ? if(*t == NULL)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //不存在該元素
? ? {
? ? ? ? return FALSE;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //刪除失敗
? ? }
? ? else if(key == (*t)->data)? ? ? ? ? ? ? ? ? ? ? ? ? //找到元素結(jié)點
? ? {
? ? ? ? BitNode *q = NULL;
? ? ? ? if((*t)->lchild == NULL)? ? ? ? ? ? ? ? ? ? //左子樹為空
? ? ? ? {
? ? ? ? ? ? q = (*t);
? ? ? ? ? ? (*t) = (*t)->rchild;
? ? ? ? ? ? free(q);
? ? ? ? ? ? *shorter = TRUE;
? ? ? ? }
? ? ? ? else if((*t)->rchild == NULL)? ? ? ? ? ? ? ? ? ? //右子樹為空
? ? ? ? {
? ? ? ? ? ? q = (*t);
? ? ? ? ? ? (*t) = (*t)->lchild;
? ? ? ? ? ? free(q);
? ? ? ? ? ? *shorter = TRUE;
? ? ? ? }
? ? ? ? else? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //左右子樹都存在,
? ? ? ? {
? ? ? ? ? ? q = (*t)->lchild;
? ? ? ? ? ? while(q->rchild)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? q = q->rchild;
? ? ? ? ? ? }
? ? ? ? ? ? (*t)->data = q->data;
? ? ? ? ? ? deleteAVL(&(*t)->lchild, q->data, shorter);? //在左子樹中遞歸刪除前驅(qū)結(jié)點
? ? ? ? }
? ? }
? ? else if(key < (*t)->data)? ? ? ? ? ? ? ? ? ? ? ? //左子樹中繼續(xù)查找
? ? {
? ? ? ? if(!deleteAVL(&(*t)->lchild, key, shorter))
? ? ? ? {
? ? ? ? ? ? return FALSE;
? ? ? ? }
? ? ? ? if(*shorter)
? ? ? ? {
? ? ? ? ? ? switch((*t)->bf)
? ? ? ? ? ? {
? ? ? ? ? ? case LH:
? ? ? ? ? ? ? ? (*t)->bf = EH;
? ? ? ? ? ? ? ? *shorter = TRUE;
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? case EH:
? ? ? ? ? ? ? ? (*t)->bf = RH;
? ? ? ? ? ? ? ? *shorter = FALSE;
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? case RH:
? ? ? ? ? ? ? ? RightBalance(&(*t));? ? ? ? //右平衡處理
? ? ? ? ? ? ? ? if((*t)->rchild->bf == EH)? ? //注意這里捌木，畫圖思考一下
? ? ? ? ? ? ? ? ? ? *shorter = FALSE;
? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? *shorter = TRUE;
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? else? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //右子樹中繼續(xù)查找
? ? {
? ? ? ? if(!deleteAVL(&(*t)->rchild, key, shorter))
? ? ? ? {
? ? ? ? ? ? return FALSE;
? ? ? ? }
? ? ? ? if(shorter)
? ? ? ? {
? ? ? ? ? ? switch((*t)->bf)
? ? ? ? ? ? {
? ? ? ? ? ? case LH:
? ? ? ? ? ? ? ? LeftBalance(&(*t));? ? ? ? //左平衡處理
? ? ? ? ? ? ? ? if((*t)->lchild->bf == EH)? //注意這里油坝，畫圖思考一下
? ? ? ? ? ? ? ? ? ? *shorter = FALSE;
? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? *shorter = TRUE;
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? case EH:
? ? ? ? ? ? ? ? (*t)->bf = LH;
? ? ? ? ? ? ? ? *shorter = FALSE;
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? case RH:
? ? ? ? ? ? ? ? (*t)->bf = EH;
? ? ? ? ? ? ? ? *shorter = TRUE;
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? return TRUE;
}
void InOrderTraverse(BiTree t)
{
? ? if(t)
? ? {
? ? ? ? InOrderTraverse(t->lchild);
? ? ? ? printf("%d? ", t->data);
? ? ? ? InOrderTraverse(t->rchild);
? ? }
}
int main(void)
{? ?
? ? int i;
? ? int a[10]={3,2,1,4,5,6,7,10,9,8};
? ? BiTree T=NULL;
? ? Status taller;
? ? for(i=0;i<10;i++)
? ? {
? ? ? ? InsertAVL(&T,a[i],&taller);
? ? }
? ? printf("中序遍歷二叉平衡樹:\n");
? ? InOrderTraverse(T);
? ? printf("\n");
? ? printf("刪除結(jié)點元素5后中序遍歷:\n");
? ? int shorter;
? ? deleteAVL(&T, 5, &shorter);
? ? InOrderTraverse(T);
? ? printf("\n");
? ? return 0;
}
