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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法与数据结构实验题 6.32 我不会 AVL，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3913字，纯文字阅读大概需要6分钟。

内容图文

★实验任务

欢迎来到暴走数据结构，我是洪尼玛。今天，我们来玩 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;
} 

 

内容总结

以上是互联网集市为您收集整理的算法与数据结构实验题 6.32 我不会 AVL全部内容，希望文章能够帮你解决算法与数据结构实验题 6.32 我不会 AVL所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---