[数据结构与算法]编写程序，从键盘输入6个整数，逐个插入到AVL树中，在每次插入时重新平衡。根据你输入的整数序列，在草稿纸上画出该AVL树，遍历输出该树并检查结果是否正确。(C语言)

#include<stdio.h>
#include<stdlib.h>
struct AVLNode{
    int Data;
    int Height;
    struct AVLNode *Left;
    struct AVLNode *Right;
};
int getHeight(struct AVLNode *T){
    if(T==NULL){
        return 0;
    }
    return T->Height;
}
int Max(int n1,int n2){
    if(n1>n2){
        return n1;
    }
    return n2;
}
struct AVLNode *SingleLeftRotation(struct AVLNode *T){
    struct AVLNode *temp;
    temp=T->Left;
    T->Left=temp->Right;
    temp->Right=T;
    T->Height=1+Max(getHeight(T->Left),getHeight(T->Right));
    temp->Height=1+Max(getHeight(T->Left),T->Height);
    return temp;
}
struct AVLNode *SingleRightRotation(struct AVLNode *T){
    struct AVLNode *temp;
    temp=T->Right;
    T->Right=temp->Left;
    temp->Left=T;
    T->Height=1+Max(getHeight(T->Left),getHeight(T->Right));
    temp->Height=1+Max(T->Height,getHeight(T->Right));
    return temp;
}
struct AVLNode *DoubleLeftRotation(struct AVLNode *T){
    T->Left=SingleRightRotation(T->Left);
    return SingleLeftRotation(T);
}
struct AVLNode *DoubleRightRotation(struct AVLNode *T){
    T->Right=SingleLeftRotation(T->Right);
    return SingleLeftRotation(T);
}
struct AVLNode *insertAVL(struct AVLNode *T,int num){
    if(T==NULL){
        T=(struct AVLNode *)malloc(sizeof(struct AVLNode));
        T->Data=num;
        T->Height=1;
        T->Left=NULL;
        T->Right=NULL;
    }else if(T->Data>num){
        T->Left=insertAVL(T->Left,num);
        if(getHeight(T->Left)-getHeight(T->Right)==2){
            if(T->Left->Data>num){
                T=SingleLeftRotation(T);
            }else{
                T=DoubleLeftRotation(T);
            }
        }
    }else if(T->Data<num){
        T->Right=insertAVL(T->Right,num);
        if(getHeight(T->Right)-getHeight(T->Left)==2){
            if(T->Right->Data<num){
                T=SingleRightRotation(T);
            }else{
                T=DoubleRightRotation(T);
            }
        }
    }
    T->Height=1+Max(getHeight(T->Left),getHeight(T->Right));
    return T;
}
void preOrder(struct AVLNode *T){
    if(T!=NULL){
        printf("%4d",T->Data);
        preOrder(T->Left);
        preOrder(T->Right);
    }
}
void inOrder(struct AVLNode *T){
    if(T!=NULL){
        inOrder(T->Left);
        printf("%4d",T->Data);
        inOrder(T->Right);
    }
}
void postOrder(struct AVLNode *T){
    if(T!=NULL){
        postOrder(T->Left);
        postOrder(T->Right);
        printf("%4d",T->Data);
    }
}
int main(){
    struct AVLNode *T;
    T=NULL;
    int num;
    for(int i=0;i<6;i++){
        printf("第%d个data=",i+1);
        scanf("%d",&num);
        T=insertAVL(T,num);
    }
    printf("先序遍历:");
    preOrder(T);
    printf("\n中序遍历:");
    inOrder(T);
    printf("\n后序遍历:");
    postOrder(T);
    return 0;
}

?

?