关于AVL树建立

#include <stdio.h>
#include <stdlib.h>
#include "queue.h"
#include <time.h>

#define N 20

int unbalance;

TreeRoot *CreatAVL();
TreeNode * AVLInsert(TreeNode *T, int data);
TreeNode *LeftBalance(TreeNode *T);
TreeNode *RightBalance(TreeNode *T);
void R_Rotate(TreeNode *T);
void L_Rotate(TreeNode *T);
void ShowAVL(TreeRoot *root);
void PreOrder(TreeRoot *root);

int main()
{
    TreeRoot *root = CreatAVL();
    PreOrder(root);
    ShowAVL(root);
    return 0;
}

TreeRoot *CreatAVL()
{
    TreeRoot *root = (TreeRoot *)malloc(sizeof(TreeRoot));
    root->lchild = root->rchild = NULL;
    int i;
    int data[N];
//    srand(time(NULL));

    for(i=0; i<N; i++)
     data[i] = rand()%100 + 1;
    for(i=0; i<N; i++)
     printf("%d\t", data[i]);
    putchar('\n');    
    root->key = data[0];
    root->bf = 0;
    for(i=1; i<N; i++)
    {
        root = AVLInsert(root, data[i]);
    }
    return root;
}

TreeNode * AVLInsert(TreeNode *T, int data)
{
    if(!T)
    {
        T = (TreeNode *) malloc (sizeof(TreeNode));
        T->key = data;
        T->lchild = T->rchild = NULL;
        T->bf = 0;
        unbalance = 1;
    }
    else if(data < T->key)
    {
        T->lchild = AVLInsert(T->lchild, data);
        if(unbalance)
        {
            switch(T->bf){
                case 1:
                    T = LeftBalance(T);
                    unbalance = 0;
                    break;
                case 0:
                    T->bf = 1;
                    unbalance = 1;
                    break;
                case -1:
                    T->bf = 0;
                    unbalance = 0;
                    break;
            }
        }
    }
    else if(data > T->key)
    {
        T->rchild = AVLInsert(T->rchild, data);
        if(unbalance)
        {
            switch(T->bf){
                case 1:
                    T->bf = 0;
                    unbalance = 0;
                    break;
                case 0:
                    T->bf = -1;
                    unbalance = 1;
                    break;
                case -1:
                    T = RightBalance(T);
                    unbalance = 0;
                    break;
            }
        }
    }
    else
     unbalance = 0;
    return T;
}

TreeNode* LeftBalance(TreeNode *T)
{
    TreeNode *rd, *lc = T->lchild;
    switch(lc->bf){
        case 1:                    //LL

            T->lchild = lc->rchild;
            lc->rchild = T;
            T->bf = 0;
            T = lc;
            break;
        case -1:                //LR

            rd = lc->rchild;
            lc->rchild = rd->lchild;
            rd->lchild = lc;
            T->lchild = rd->rchild;
            rd->rchild = T;
            switch(rd->bf){
                case 1:
                    T->bf = -1;
                    lc->bf = 0;
                    break;
                case 0:
                    T->bf = lc->bf = 0;
                    break;
                case -1:
                    T->bf = 0;
                    lc->bf = 1;
                    break;
            }
            T= rd;
            break;
    }
    T->bf = 0;
    unbalance = 0;
    return T;
}

TreeNode *RightBalance(TreeNode *T)
{
    TreeNode *lc, *rc = T->rchild;
    switch(rc->bf)
    {
        case -1:                //RR

            T->bf = 0;
            T->rchild = rc->lchild;
            rc->lchild = T;
            T = rc;
            break;
        case 1:                    //RL

            lc = rc->lchild;
            rc->lchild = lc->rchild;
            lc->rchild = rc;
            T->rchild = lc->lchild;
            lc->lchild = T;
            switch( lc->bf )
            {
                case 1:
                    T->bf = 0;
                    rc->bf = -1;
                    break;
                case 0:
                    rc->bf = 0;
                    T->bf = 0;
                    break;
                case -1:
                    T->bf = 1;
                    rc->bf = 0;
            }
            T = lc;
    }
    T->bf = 0;
    unbalance = 0;
    return T;
}

void PreOrder(TreeRoot *root)
{
    if(root)
    {
        printf("%d\t%d\n", root->key, root->bf);
        PreOrder(root->lchild);
        PreOrder(root->rchild);
    }
}

void ShowAVL(TreeRoot *root)
{
    TreeRoot *T = root;
    Queue Q;
    QueueInitial(&Q);
    QueuePush(&Q, T);
    while(!QueueEmpty(Q))
    {
        T = QueuePop(&Q);
        printf("%d\n",T->key);
        if(NULL != T->lchild)
         QueuePush(&Q, T->lchild);
        if(NULL != T->rchild)
         QueuePush(&Q, T->rchild);
    }
}