[数据结构与算法]随机产生百万个整数，用该整数序列分别生成二叉排序树和AVL树。（1）输出两棵树的结点总数；（2）输出两棵树所有结点所在层次的总和；（3）计算两棵树的平均查找长度ASL（查找成功时）。（C语言）

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
struct AVLNode{
    int Data;
    int Height;
    int state;
    struct AVLNode *Left;
    struct AVLNode *Right;
};
struct stack{
    struct AVLNode **data;
    int top;
    int maxSize;
};
struct stack *createStack(int maxsize){
    struct stack *s;
    s=(struct stack *)malloc(sizeof(struct stack));
    s->data=(struct AVLNode *)malloc(sizeof(struct AVLNode *)*maxsize);
    s->top=-1;
    s->maxSize=maxsize;
    return s;
}
int isFull(struct stack *s){
    return s->top==s->maxSize-1;
}
int isEmpty(struct stack *s){
    return s->top==-1;
}
void push(struct stack *s,struct AVLNode *AVLT){
    if(isFull(s)){
        printf("stack is full\n");
        return;
    }
    s->data[++s->top]=AVLT;
}
struct AVLNode *pop(struct stack *s){
    if(isEmpty(s)){
        printf("stack is empty\n");
        exit(-1);
    }
    return s->data[s->top--];
}
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 *AVLT){
    struct AVLNode *temp;
    temp=AVLT->Left;
    AVLT->Left=temp->Right;
    temp->Right=AVLT;
    AVLT->Height=1+Max(getHeight(AVLT->Left),getHeight(AVLT->Right));
    temp->Height=1+Max(getHeight(temp->Left),AVLT->Height);
    return temp;
}
struct AVLNode *SingleRightRotation(struct AVLNode *AVLT){
    struct AVLNode *temp;
    temp=AVLT->Right;
    AVLT->Right=temp->Left;
    temp->Left=AVLT;
    AVLT->Height=1+Max(getHeight(AVLT->Left),getHeight(AVLT->Right));
    temp->Height=1+Max(AVLT->Height,getHeight(temp->Right));
    return temp;
}
struct AVLNode *DoubleLeftRotation(struct AVLNode *AVLT){
    AVLT->Left=SingleRightRotation(AVLT->Left);
    return SingleLeftRotation(AVLT);
}
struct AVLNode *DoubleRightRotation(struct AVLNode *AVLT){
    AVLT->Right=SingleLeftRotation(AVLT->Right);
    return SingleRightRotation(AVLT);
}
struct AVLNode *AVLinsert(struct AVLNode *AVLT,int num){
    if(AVLT==NULL){
        AVLT=(struct AVLNode *)malloc(sizeof(struct AVLNode));
        AVLT->Data=num;
        AVLT->Height=1;
        AVLT->state=0;
        AVLT->Left=NULL;
        AVLT->Right=NULL;
    }else if(AVLT->Data>num){
        AVLT->Left=AVLinsert(AVLT->Left,num);
        if(getHeight(AVLT->Left)-getHeight(AVLT->Right)==2){
            if(AVLT->Left->Data>num){
                AVLT=SingleLeftRotation(AVLT);
            }else{
                AVLT=DoubleLeftRotation(AVLT);
            }
        }
    }else if(AVLT->Data<num){
        AVLT->Right=AVLinsert(AVLT->Right,num);
        if(getHeight(AVLT->Right)-getHeight(AVLT->Left)==2){
            if(AVLT->Right->Data<num){
                AVLT=SingleRightRotation(AVLT);
            }else{
                AVLT=DoubleRightRotation(AVLT);
            }
        }
    }
    AVLT->Height=1+Max(getHeight(AVLT->Left),getHeight(AVLT->Right));
    return AVLT;
}
int Count(struct AVLNode *T){
    if(T==NULL){
        return 0;
    }
    return 1+Count(T->Left)+Count(T->Right);
}
int getTotalASL(struct AVLNode *T){
    struct stack *s;
    s=createStack(100);
    int total=0;
    int num=1;
    while(1){
        if(T->state==0){
            total+=num;
            T->state=1;
            if(T->Left!=NULL){
                push(s,T);
                T=T->Left;
                num++;
            }
        }else if(T->state==1){
            T->state=2;
            if(T->Right!=NULL){
                push(s,T);
                T=T->Right;
                num++;
            }
        }else{
            num--;
            T->state=0;
            T=pop(s);
            if(T->state==2&&isEmpty(s)){
                T->state=0;
                break;
            }
        }
    }
    return total;
}
struct AVLNode *SqTinsert(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;
        T->state=0;
    }else if(T->Data>num){
        T->Left=SqTinsert(T->Left,num);
    }else if(T->Data<num){
        T->Right=SqTinsert(T->Right,num);
    }
    T->Height=Max(getHeight(T->Left),getHeight(T->Right));
    return T;
}
int main(){
    struct AVLNode *AVLT=NULL;
    struct AVLNode *SqT=NULL;
    srand(time(NULL));
    for(int i=1;i<1000200;i++){
        int num=(rand()<<15)|rand();
        AVLT=AVLinsert(AVLT,num);
        SqT=SqTinsert(SqT,num);
    }
    printf("\nAVL树节点总数=%d\n",Count(AVLT));
    printf("AVL树所有节点所在层次总和=%d\n",getTotalASL(AVLT));
    printf("AVL树平均ASL=%lf\n",(double)getTotalASL(AVLT)/Count(AVLT));

    printf("\n顺序二叉树节点总数=%d\n",Count(SqT));
    printf("顺序二叉树所有节点所在层次总和=%d\n",getTotalASL(SqT));
    printf("顺序二叉树平均ASL=%lf",(double)getTotalASL(SqT)/Count(SqT));
    return 0;
}