算法与数据结构实验题 6.32 我不会 AVL

★实验任务

欢迎来到暴走数据结构，我是洪尼玛。今天，我们来玩 AVL树，怎么玩呢？很简单：给 你n个数字，你需要按顺序插入一棵AVL树中，然后输出每个数所在节点的深度（从1开始）。 因为我不会AVL树，所以希望聪明的你们来帮我完成这个任务

★数据输入

输入第一个数为n（n≤100000）表示数字的个数

接下来一行输入n个数，范围在 1 到 n 之间，每个数只出现一次

★数据输出

按输入的顺序依次输出每个数所在节点的深度

6 1 2 3 4 5 6

3 2 3 1 2 3

★提示

注意：输出行末不能有空格

对于50%的数据，1<=n<=100

对于100%的数据，1<=n<=100000

#include<stdio.h>
#include<stdlib.h>

typedef struct TNode *Position;
typedef Position BinTree;
typedef int ElementType;
int maxsize=100005;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
    int Height;
}a[100005];

Position FindMin( BinTree BST ){
    if(!BST || !BST->Left)return BST;
    return FindMin(BST->Left);
}

Position FindMax( BinTree BST ){
    if(!BST || !BST->Right)return BST;
    return FindMax(BST->Right);
}

BinTree Delete(BinTree BST,ElementType X)
{
    Position Tmp;
    if(!BST)
        printf("要删除的元素未找到");
    else
    {
        if(X < BST->Data)
            BST->Left = Delete(BST->Left,X);//左子树递归删除
        else if(X > BST->Data)
            BST->Right = Delete(BST->Right,X);//右子树递归删除
        else{//BST就是要删除的点
            //如果被删除的结点有左右两个子结点 
            if(BST->Left&&BST->Right)
            {
                Tmp = FindMin(BST->Right);
                BST->Data = Tmp->Data;
                BST->Right = Delete(BST->Right,BST->Data);
             }
            else{//被删除的结点只有一个或无子节点 
                Tmp = BST;
                if(!BST->Left)
                    BST = BST->Right;
                else
                    BST = BST->Left;
                free(Tmp);
            }
        }
    }
    return BST;
}

int Max( int a,int b)
{
    return a > b ? a : b;
}

int Height(BinTree t)
 {
     int hl,hr;
     if(!t)return -1;
     hl=Height(t->Left);
     hr=Height(t->Right);
     if(hl>hr) return ++hl;
     else return ++hr;
 }

 int GetHeight(BinTree T){
     if(!T)return 0;
     return T->Height;
 }

BinTree SingleLeftRotation(BinTree A)
{  //注意 A必须有一个左子结点B
   //将A和B做左单旋，更新A和B的高度，返回新的结点B
    BinTree B = A->Left;
    A->Left = B->Right ;
    B->Right = A;
    A->Height = Max( GetHeight(A->Left),GetHeight(A->Right))+1;
    B->Height = Max( GetHeight(B->Left),A->Height)+1;
    return B;
 }

BinTree SingleRightRotation(BinTree A)
{
    BinTree B = A->Right ;
    A->Right = B->Left;
    B->Left = A;
    A->Height = Max( GetHeight(A->Left),GetHeight(A->Right))+1;
    B->Height = Max( GetHeight(B->Right),A->Height)+1;
    return B;
}

BinTree DoubleLeftRightRotation(BinTree A)
{
    /* 注意：A必须有一个左子结点B，且B必须有一个右子结点C */
  /* 将A、B与C做两次单旋，返回新的根结点C */
  /* 将B与C做右单旋，C被返回 */
    A->Left = SingleRightRotation(A->Left);
     /* 将A与C做左单旋，C被返回 */
    return SingleLeftRotation(A);
}

BinTree DoubleRightLeftRotation(BinTree A)
{
    A->Right = SingleLeftRotation(A->Right);
    return SingleRightRotation(A);
}

BinTree Insert(BinTree BST,struct TNode &X)
{
    if(!BST)
    {//若原树为空，生成并返回一个结点的二叉搜索树
        BST = &X;
        BST->Left = BST->Right =NULL;

    }
    else //开始查找要插入的的元素的位置 
    {
        if( X.Data < BST->Data )
        {
            BST->Left = Insert(BST->Left,X);//递归插入左子树
            if(GetHeight(BST->Left) - GetHeight(BST->Right) == 2)
            {
                if( X.Data < BST->Left->Data )
                BST = SingleLeftRotation(BST);
                else
                BST = DoubleLeftRightRotation(BST);
             }
        }
        else if(X.Data > BST->Data)
        {
            BST->Right = Insert(BST->Right,X);//递归插入右子树 
            if(GetHeight(BST->Left) - GetHeight(BST->Right)== -2)
            {
                if(X.Data > BST->Right->Data )
                BST = SingleRightRotation(BST);
                else
                BST = DoubleRightLeftRotation(BST);
            }
        }
        //else X已经存在，什么都不做 
    }
    BST->Height = Max(GetHeight(BST->Left),GetHeight(BST->Right)) + 1;

    return BST;
}



BinTree MakeTree(int N){
    BinTree T=NULL;
    int i,V;
    for(int i=0;i<N;i++){
        scanf("%d",&a[i].Data);
        T = Insert(T,a[i]);
    }
//    for(int i=0;i<N;i++){
//        printf("%d ",T->Height+1-a[i].Height);
//    }
    return     T;
}

void Find(BinTree T,ElementType X,int *deep){
    if(!T||T->Data == X)return ;
    else{
        (*deep)++;
        return Find(T->Data>X ? T->Left : T->Right ,X,deep);
    }
}

void FindDepth(BinTree T,int N)
{
    int deep;
    for(int i=0;i<N;i++)
    {
        deep = 0;
        Find(T,a[i].Data,&deep);
        printf("%d ",deep+1);
    }
}

int main(){
    BinTree T = NULL;
    int n;
    scanf("%d",&n);
    T = MakeTree(n);
    FindDepth(T,n);
    return 0;
}