平衡二叉树的建立 c语言范例

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node
{
    int data;
    int high;
    struct node *lt, *rt;
};

int max(int a, int b)
{
    return a>b?a:b;
}
///深度
int deep(struct node *root)
{
    if(root==NULL)
        return -1;
    else return root->high;
}

struct node *LL(struct node *root)   // 左儿子变为根, 根变为左儿子的右儿子. 
{
    struct node *p=root->lt;
    root->lt=p->rt;     //先把p的右儿子变为root的左儿子,root的左儿子发生改变.  但是root的右儿子没变
    p->rt=root;       //根作为p的右儿子
    root->high=max(deep(root->lt), deep(root->rt))+1;  //root的左儿子lt变了, 所以root的高需要重算
    return p;     //    p的右儿子变了, 新的root也是需要重算高度的,  重算放在Insert函数最后进行
}

struct node *RR(struct node *root)  // 右儿子变为根, 根变为右儿子的左儿子. 
    struct node *p=root->rt;
    root->rt=p->lt;  //root的右儿子发生改变.  但是root的左儿子没变
    p->lt=root;
    root->high=max(deep(root->lt), deep(root->rt))+1;   //root 的右儿子变了, 需要重算高度
    return p;        //新的root也是需要重算高度的,  重算放在Insert函数最后进行
}

struct node *RL(struct node *root)
{
    root->rt=LL(root->rt);
    root=RR(root);
    return root;
}

struct node *LR(struct node *root)
{
    root->lt=RR(root->lt);
    root=LL(root);
    return root;
}

struct node *Insert(struct node *root, int num)
{
    if(!root)
    {
        root=(struct node *)malloc(sizeof(struct node));
        root->data=num;
        root->high=0;
        root->lt=NULL;
        root->rt=NULL;
    }
    else
    {
        if(num<root->data)///数据比根小
        {
            root->lt=Insert(root->lt, num);///加到左子树上

            ///先判断是否要转
            if(abs(deep(root->lt)-deep(root->rt))>1)//深度之差大于一就转
            {
               if(num>=root->lt->data)///比左子根大，转两次，即LR
                {
                    root=LR(root);
                }
                else ///比左子根小，转一次，即LL
                {
                    root=LL(root);
                }
            }

        }
        else///比根大
        {
            root->rt=Insert(root->rt, num);///加到右子树上
            if(abs(deep(root->lt)-deep(root->rt))>1)
            {
                if(num>=root->rt->data)///加到右子树的右边，转一次,RR
                {
                    root=RR(root);
                }
                else///加到右子树的左边，转两次,RL
                {
                    root=RL(root);
                }
            }
        }
    }

    root->high=max(deep(root->lt), deep(root->rt))+1;
    printf("node-data=%d, node-high=%d\n",root->data,root->high);
    return root;
}
int main()
{
    struct node *root=NULL;

    root=Insert(root,23);
    printf("root-data=%d\n", root->data);
    root=Insert(root,10);
    printf("root-data=%d\n", root->data);
    root=Insert(root,17);
    printf("root-data=%d\n", root->data);
    root=Insert(root,73);
    printf("root-data=%d\n", root->data);
    root=Insert(root,8);
    printf("root-data=%d\n", root->data);
    root=Insert(root,11);
    root=Insert(root,46);
    root=Insert(root,27);
    root=Insert(root,6);
    root=Insert(root,3);
    root=Insert(root,10);
    printf("root-data=%d\n", root->data);
    return 0;
}