建一颗平衡二叉树（C语言）

ゝ一世哀愁。 2021-11-10 05:12 265阅读 0赞

#include<stdio.h>
    #include<stdlib.h>
    typedef struct node
    { 
        int data; 	//存储数据
        struct node *lson;
        struct node *rson;
    }NODE;
    
    int deep(NODE *t)  //求深度函数
    { 
        int d=0;
        if(t)
        { 
            int l=deep(t->lson)+1;
            int r=deep(t->rson)+1;
            d=l>r?l:r;
        }
        return d;
    }
    
    NODE *LL(NODE *t)  //左左旋转
    { 
        NODE *p;
        p=t->lson;
        t->lson=p->rson;
        p->rson=t;
        return p;
    }
    NODE *RR(NODE *t)
    { 
        NODE *p;
        p=t->rson;
        t->rson=p->lson;
        p->lson=t;
        return p;
    }
    NODE *LR(NODE *t)
    { 
        t->lson=RR(t->lson);
        return LL(t);
    }
    NODE *RL(NODE *t)
    { 
        t->rson=LL(t->rson);
        return RR(t);
    }
    NODE *creat(NODE *t,int k)
    { 
        if(t==NULL)
        { 
            t=(NODE *)malloc(sizeof(NODE));
            t->data=k;
            t->lson=t->rson=NULL;
        }
        else
        { 
            if(k<t->data)
            { 
                t->lson=creat(t->lson,k);
                if((deep(t->lson)-deep(t->rson))>1) //不满足平衡二叉树的条件，左子树比右子树高，要进行左旋
                { 
                    if(t->lson->data>k) //插在了左子树上
                        t=LL(t);//so，要左左旋
                    else
                        t=LR(t);//否则左右旋
                }
            }
            else
            { 
                t->rson=creat(t->rson,k);
                if((deep(t->rson)-deep(t->lson))>1)//不满足平衡二叉树的条件，右子树比左子树高，要进行右旋
                { 
                    if(t->rson->data>k)//插在了左子树上
                        t=RL(t);//so，要右左旋
                    else
                        t=RR(t);//否则右右旋
                }
            }
        }
        return t;
    }
    int main()
    { 
        int i,n,m;
        scanf("%d",&n);
        NODE *t=NULL;
        for(i=0;i<n;i++)
        { 
            scanf("%d",&m);
            t=creat(t,m);
        }
        printf("%d\n",t->data);
        return 0;
    }