[C++知识库]平衡二叉树的创建（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=Max(getHeight(T->left),getHeight(T->right))+1;
    temp->height=Max(getHeight(temp->left),T->height)+1;
    return temp;
}
struct AVLNode *SingleRightRotation(struct AVLNode *T){/*右单旋*/
    struct AVLNode *temp;
    temp=T->right;
    T->right=temp->left;
    temp->left=T;
    T->height=Max(getHeight(T->left),getHeight(T->right))+1;
    temp->height=Max(T->height,getHeight(temp->right))+1;
    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 SingleRightRotation(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(num<T->data){
        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(num>T->data){
        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=Max(getHeight(T->left),getHeight(T->right)+1);
    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<10;i++){
        printf("data=");
        scanf("%d",&num);
        T=insertAVL(T,num);
    }
    printf("前序遍历:\n");
    preOrder(T);
    printf("\n中序遍历:\n");
    inOrder(T);
    printf("\n后序遍历:\n");
    postOrder(T);
    return 0;
}

?

?