平衡二叉樹(shù)的定義：

平衡二叉樹(shù)（balanced binary tree)

創(chuàng)新互聯(lián)是一家集網(wǎng)站建設(shè),焦作企業(yè)網(wǎng)站建設(shè),焦作品牌網(wǎng)站建設(shè),網(wǎng)站定制,焦作網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營(yíng)銷,網(wǎng)絡(luò)優(yōu)化,焦作網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長(zhǎng)自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。

又稱AVL樹(shù)（Adelson-Velskii and Landis)

一棵平衡二叉樹(shù)或者是空樹(shù)，或者是具有下列性質(zhì)的二叉排序樹(shù)：

１，左子樹(shù)與右子樹(shù)的高度之差的絕對(duì)值小于等于１；

２，左子樹(shù)和右子樹(shù)也是平衡二叉排序樹(shù)．

為了方便起見(jiàn)，給每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字，給出該結(jié)點(diǎn)左子樹(shù)與右子樹(shù)的高度差．這個(gè)數(shù)字稱為結(jié)點(diǎn)的平衡因子（ＢＦ）．

平衡因子?。健〗Y(jié)點(diǎn)左子樹(shù)的高度?。〗Y(jié)點(diǎn)右子樹(shù)的高度

根據(jù)平衡二叉樹(shù)的定義，平衡二叉樹(shù)上所有結(jié)點(diǎn)的平衡因子只能是-1,0,或1.

例：

對(duì)于一棵有n個(gè)結(jié)點(diǎn)的AVL樹(shù)，其高度保持在O(log2^n)數(shù)量級(jí)

失衡二叉排序樹(shù)的分析與調(diào)整

? 當(dāng)我們?cè)谝粋€(gè)平衡二叉排序樹(shù)上插入一個(gè)結(jié)點(diǎn)時(shí)，有可能導(dǎo)致失衡，不再是一個(gè)平衡二叉排序樹(shù)，即出現(xiàn)平衡因子絕對(duì)值大于１的結(jié)點(diǎn)．

如果在一棵ＡＶＬ樹(shù)中插入一個(gè)新結(jié)點(diǎn)后造成失衡，則必須重新調(diào)整樹(shù)的結(jié)構(gòu)，使之恢復(fù)平衡

平衡調(diào)整的四種類型：

具體的調(diào)整為：

調(diào)整原則為：１）降低高度　２）保持二叉排序樹(shù)的性質(zhì)

規(guī)律：按照二叉排序樹(shù)的性質(zhì)，挑選３個(gè)值的中間值作為調(diào)整后的根結(jié)點(diǎn)，最小值為根結(jié)點(diǎn)的左孩子，大值為根結(jié)點(diǎn)的右孩子．?

例：ＬＬ型

例：ＲＬ型

ＲＲ型和ＬＲ型和上面類似，就不多介紹了，總之，一個(gè)總的原則，就是調(diào)整后必須保證１）降低高度?。玻┍３侄媾判驑?shù)的性質(zhì)

還是那句話，只要知道調(diào)整類型，就可以確定Ａ，Ｂ，Ｃ三個(gè)頂點(diǎn)的位置，中間值為根結(jié)點(diǎn)，大值為右孩子，最小值為左孩子，確定好后，別的結(jié)點(diǎn)就很容易根據(jù)二叉排序樹(shù)的特點(diǎn)找到各自的位置，網(wǎng)上看了很多左旋，右旋，左右旋，頭都暈．只要知道這個(gè)規(guī)律，不用管什么旋，也不用死記硬背還怕忘．隨時(shí)碰到隨時(shí)都可以馬上上手．

接下來(lái)用代碼來(lái)實(shí)現(xiàn)一個(gè)平衡二叉樹(shù)的建立：

例題：輸入關(guān)鍵字序列(16,3,7,11,9,26,18,14,15),創(chuàng)建一個(gè)平衡二叉樹(shù)

第一個(gè)方法是給結(jié)點(diǎn)加了一個(gè)parent域，方便查找，不過(guò)感覺(jué)挺麻煩的，每次調(diào)整都要給parent域賦值，不過(guò)這個(gè)代碼在有多個(gè)失衡點(diǎn)時(shí)會(huì)挑選最小代價(jià)樹(shù)的失衡點(diǎn)，不管失衡點(diǎn)是不是根結(jié)點(diǎn)都是通用的

#include#include#define MAXINT 10000
#define MAXSIZE 10
typedef struct BBTnode{
    int data;//這里為了方便，直接用int,沒(méi)有用結(jié)構(gòu)體．
    int balance;//平衡因子
    struct BBTnode* lchild;
    struct BBTnode* rchild;
    struct BBTnode* parent;
}BBTnode,*BBTree;
BBTree MinBalance;//最小失衡結(jié)點(diǎn)地址
int k = 0;
int i = 0;
BBTree SearchBBT(BBTree T, int m, char* arr)//計(jì)算從某點(diǎn)出發(fā)，到指定數(shù)字的路徑
{
    if(!T || T->data == m)
    {
        return T;
    }
    else if(m< T->data)
    {
        arr[k++] = 'L';
        return SearchBBT(T->lchild, m, arr);
    }
    else
    {
        arr[k++] = 'R';
        return SearchBBT(T->rchild, m, arr);
    }

}

int CountNodes(BBTree T)//計(jì)算樹(shù)中的結(jié)點(diǎn)數(shù)，比較失衡結(jié)點(diǎn)樹(shù)的大小，選擇較小的樹(shù)（當(dāng)不止一個(gè)失衡點(diǎn)時(shí)）
{
    if(!T)
    {
        return 0;
    }
    return CountNodes(T->lchild) + CountNodes(T->rchild) + 1;
}

int DepthBBT(BBTree T)//計(jì)算平衡二叉樹(shù)的深度
{
    int m, n;
    if(!T)
    {
        return 0;
    }
    else
    {
        m = DepthBBT(T->lchild) + 1;//左邊的深度
        n = DepthBBT(T->rchild) + 1;//右邊的深度
    }
    if(m >n)return m;//取較大值
    else return n;
}


void OrderBBT(BBTree* T, BBTree Unbalance[MAXSIZE])//中序遍歷二叉排序樹(shù),更新各結(jié)點(diǎn)平衡因子，把所有失衡點(diǎn)存儲(chǔ)起來(lái)
{
    if(*T == NULL)return;
    else
    {
        OrderBBT(&(*T)->lchild,Unbalance);
        (*T)->balance = abs(DepthBBT((*T)->lchild) - DepthBBT((*T)->rchild));//計(jì)算該結(jié)點(diǎn)平衡因子，左邊深度－右邊深度再取絕對(duì)值
        if((*T)->balance>1)
        {
            Unbalance[i++] = *T;
        }
        OrderBBT(&(*T)->rchild,Unbalance);
    }
}

void AddBBT(BBTree* T, int m, BBTree parent)//二叉排序樹(shù)的遞歸添加元素
{
    if(!(*T))
    {
        *T = malloc(sizeof(BBTnode));
        (*T)->data = m;
        (*T)->lchild = NULL;
        (*T)->rchild = NULL;
        (*T)->balance = 0;
        (*T)->parent = parent;
    }
    else if(m< (*T)->data)
    {
        AddBBT(&(*T)->lchild, m, *T);
    }
    else
    {
        AddBBT(&(*T)->rchild, m, *T);

    }
}


void creatBBT(BBTree* T)//創(chuàng)建平衡二叉排序樹(shù)，實(shí)際上就是給一個(gè)空樹(shù)添加元素
{
    int input = 1;
    BBTree A,B,C;//定義圖示中表示的三個(gè)頂點(diǎn)
    while(input)
    {
        printf("請(qǐng)依次輸入數(shù)字序列，輸入完畢以0結(jié)束:>");
        scanf("%d",&input);
        if(input == 0)break;
        AddBBT(T, input,*T);
        MinBalance = 0;//重置最小平衡因子為空
        int temp = MAXINT;
        int j;
        BBTree Unbalance[MAXSIZE] = {0};//定義一個(gè)失衡結(jié)點(diǎn)數(shù)組，用來(lái)存放當(dāng)前樹(shù)中存在的失衡結(jié)點(diǎn)
        i = 0;//重置數(shù)組Unbalance的下標(biāo)為0開(kāi)始
        OrderBBT(T,Unbalance);//更新平衡因子，得到平衡因子數(shù)組Unbalance
        for(j = 0; j< MAXSIZE; j++)//從數(shù)組Unbalance找出最小失衡因子，并返回該地址到MinBalance
        {
            if(!Unbalance[j])break;
            if(CountNodes(Unbalance[j])< temp)
            {
                temp = CountNodes(Unbalance[j]);
                MinBalance = Unbalance[j];
            }
        }
        char ChoiceType[MAXSIZE] = {0};//選擇調(diào)整類型的數(shù)組（ＬＬ，ＲＲ．ＬＲ，ＲＬ）
        k = 0;//重置SearchBBT里的k變量
        SearchBBT(MinBalance, input, ChoiceType);//得到從失衡點(diǎn)出發(fā)到添加結(jié)點(diǎn)間的路徑
        if(ChoiceType[0] == 'L' && ChoiceType[1] == 'L')//ＬＬ型調(diào)整
        {
            A = MinBalance;
            B = MinBalance->lchild;
            C = MinBalance->lchild->lchild;
            if(A->parent)//如果這個(gè)失衡點(diǎn)不是根結(jié)點(diǎn)
            {
                if(A->data< A->parent->data)A->parent->lchild = B;
                else A->parent->rchild = B;
            }
            else *T = B;

            A->lchild = B->rchild;
            if(B->rchild)B->rchild->parent = A;
            B->rchild = A;
            B->parent = A->parent;
            A->parent = B;

        }
        else if(ChoiceType[0] == 'R' && ChoiceType[1] == 'R')//ＲＲ型調(diào)整
        {
            A = MinBalance;
            B = MinBalance->rchild;
            C = MinBalance->rchild->rchild;
            if(A->parent)//如果這個(gè)失衡點(diǎn)不是根結(jié)點(diǎn)
            {
                if(A->data< A->parent->data)A->parent->lchild = A->rchild;
                else A->parent->rchild = A->rchild;
            }
            else *T = B;//如果是根結(jié)點(diǎn)，那么根結(jié)點(diǎn)變成調(diào)整后的根結(jié)點(diǎn)
            A->rchild = B->lchild;
            if(B->lchild)B->lchild->parent = A;
            B->lchild = A;
            B->parent = A->parent;
            A->parent = B;



        }
        else if(ChoiceType[0] == 'L' && ChoiceType[1] == 'R')//ＬＲ型調(diào)整
        {
            A = MinBalance;
            B = MinBalance->lchild;
            C = MinBalance->lchild->rchild;
            if(A->parent)//如果這個(gè)失衡點(diǎn)不是根結(jié)點(diǎn)
            {
                if(A->data< A->parent->data)A->parent->lchild = C;
                else A->parent->rchild = C;
            }
            else *T = C;
            B->rchild = C->lchild;
            if(C->lchild)C->lchild->parent =B;
            A->lchild = C->rchild;
            if(C->rchild)C->rchild->parent = A;
            C->rchild = A;
            C->lchild = B;
            C->parent = A->parent;
            A->parent = C;
            B->parent = C;

        }
        else if(ChoiceType[0] == 'R' && ChoiceType[1] == 'L')//ＲＬ型調(diào)整
        {
            A = MinBalance;
            B = MinBalance->rchild;
            C = MinBalance->rchild->lchild;
            if(A->parent)//如果這個(gè)失衡點(diǎn)不是根結(jié)點(diǎn)
            {
                if(A->data< A->parent->data)A->parent->lchild = C;
                else A->parent->rchild = C;
            }
            else *T = C;
            A->rchild = C->lchild;
            if(C->lchild)C->lchild->parent = A;
            B->lchild = C->rchild;
            if(C->rchild)C->rchild->parent = B;
            C->lchild = A;
            C->rchild = B;
            C->parent = A->parent;
            A->parent = C;
            B->parent = C;
        }
    }
    BBTree arr[MAXSIZE] = {0};//這個(gè)只為為了下面這個(gè)OrderBBT函數(shù)能運(yùn)行，沒(méi)有別的意義
    OrderBBT(T,arr);
}
void printBBT(BBTree T)//中序輸出二叉排序樹(shù)，得到的是一個(gè)遞增數(shù)列
{
    if(T == NULL)return;
    else
    {
        printBBT(T->lchild);
        printf("%d號(hào)結(jié)點(diǎn)平衡因子為%d\n",T->data,T->balance);
        printBBT(T->rchild);
    }
}

int main()
{
    BBTree T = NULL;//定義二叉排序樹(shù)Ｔ
    creatBBT(&T);//創(chuàng)建二叉排序樹(shù)
    printBBT(T);//輸出創(chuàng)建好的二叉排序樹(shù)
    return 0;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站名稱：數(shù)據(jù)結(jié)構(gòu)之平衡二叉樹(shù)詳解-創(chuàng)新互聯(lián)
地址分享：http://weahome.cn/article/dchohd.html