程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 平衡二叉樹的調整模版

平衡二叉樹的調整模版

編輯:關於C++
typedef struct avltreenode *avltree;
typedef struct avltreenode{
    int data;
    avltree left;
    avltree right;
    int height;
};

int getheight(avltree a)
{
    if(a==NULL) return -1;
    return a->height;
}

//a必須有一個左子結點b
//a與b做左單旋,更新a與b高度,返回新的根結點b
avltree singleleftrotation(avltree a)
{
    avltree b=a->left;
    a->left=b->right;
    b->right=a;
    a->height=max(getheight(a->left),getheight(a->right))+1;
    b->height=max(getheight(b->left),a->height)+1;

    return b;
}

//右單旋
avltree singlerightrotation(avltree a)
{
    avltree b=a->right;
    a->right=b->left;
    b->left=a;

    a->height=max(getheight(a->left),getheight(a->right))+1;
    b->height=max(getheight(b->right),a->height)+1;

    return b;
}

//左右雙旋
//a必須有一個左子結點b,且b必須有一個右子結點c
//a,b,c,做兩次單旋,返回新的根結點c
//先對b和c做右單旋,在對a和c做左單旋
avltree doubleleftrightrotation(avltree a)
{
    a->left=singlerightrotation(a->left);

    return singleleftrotation(a);
}

//右左雙旋
avltree doublerightleftrotation(avltree a)
{
    a->right=singleleftrotation(a->right);

    return singlerightrotation(a);
}

avltree avl_insertion(int x,avltree t)
{
    /*將X插入avl樹T中,並返回調整後的avl樹*/
    if(!t)/*插入空樹,則新建包含一個結點的樹*/
    {
        t=(avltree)malloc(sizeof(struct avltreenode));
        t->data=x;
        t->height=0;
        t->left=t->right=NULL;
    }/*插入空樹結束*/
    else if(xdata)
    {
        t->left=avl_insertion(x,t->left);
        if(getheight(t->left)-getheight(t->right)==2)
        {
            /*需要左旋*/
            if(xleft->data)
                t=singleleftrotation(t);//左單旋 singleleftrotation
            else
                t=doubleleftrightrotation(t);//左右雙旋
        }
    }
    else if(x>t->data)
    {
        t->right=avl_insertion(x,t->right);
        if(getheight(t->left)-getheight(t->right)==-2)
        {
            /*需要右旋*/
            if(x>t->right->data)
                t=singlerightrotation(t);//右單旋
            else
                t=doublerightleftrotation(t);//右左雙旋
        }
    }

    //x=data,無須插入
    t->height=max(getheight(t->left),getheight(t->right))+1;
    return t;
}

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved