| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1299 人关注过本帖, 1 人收藏
标题:AVL树~
只看楼主 加入收藏
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
结帖率:99.25%
收藏(1)
已结贴  问题点数:5 回复次数:3 
AVL树~
用AVL树实现搜索的效率挺高的~感觉大数据查重效率较高~~~拿出来弄一下~

这数据结构不必要看明白~就是九九要每日积累一点点~把代码发在这里~

代码参考网上的~有兴趣的可以网上搜搜相关资料~

程序代码:
/*AVL树的创建完整C代码*/
#include<stdio.h>
#include<stdlib.h>

#define MAX(a,b) ((a)>(b)?(a):(b))

typedef int ElemType;

typedef struct AVLNode
{
    ElemType data;
    int height;
    struct AVLNode* lchild;
    struct AVLNode* rchild;
}AVLNode,*AVLTree;

int GetHeight (AVLTree t);   //获取AVL树高度

void SingleRotateWithRight(AVLTree* t);   //右旋操作
void SingleRotateWithLeft(AVLTree* t);    //左旋操作
void DoubleRotateWithLeft(AVLTree* t);    //双旋操作,先左后右
void DoubleRotateWithRight(AVLTree* t);   //双旋操作,先右后左

void ChangeAVLLeft(AVLTree* t,ElemType e);   //检查左子树
void ChangeAVLRight(AVLTree* t,ElemType e);   //检查左子树

void Insert(AVLTree* t,ElemType e);       //插入函数
void CreatAVL(AVLTree* t,ElemType* a,int n);  //创建AVL树函数 
void InOrderPrint(AVLTree t);                  //打印AVL树

int main()
{
    int n=0;
    int i=0;

    AVLTree t=NULL;

    ElemType* a=NULL;

    printf("请输入AVL节点个数:");
    scanf("%d",&n);

    a=(ElemType*)malloc(n*sizeof (ElemType));

    printf("请输入节点数据:\n");

    for (i=0;i!=n;++i)
        scanf("%d",&a[i]);

    CreatAVL(&t,a,n);

    printf("该AVL树的中序遍历结果为:\n");
    InOrderPrint(t);

    puts("");

    return 0;
}

int GetHeight(AVLTree t)   //利用递归获取AVL树的高度
{
    if (t==NULL)
        return -1;
    else
        return (1+MAX(GetHeight(t->lchild),GetHeight(t->rchild)));
}

void SingleRotateWithRight(AVLTree* t)   //右旋操作
{
    AVLTree p=NULL;

    p=(*t)->lchild;               
    (*t)->lchild=p->rchild;       
    p->rchild=(*t);               


    //结点的位置改变,更新结点的高度值
    (*t)->height=GetHeight(*t);
    p->height=GetHeight(p);

    *t=p;
}

void SingleRotateWithLeft(AVLTree* t)    //左旋操作
{
    AVLTree p=NULL;

    p=(*t)->rchild;
    (*t)->rchild=p->lchild;
    p->lchild=(*t);

    (*t)->height=GetHeight(*t);
    p->height=GetHeight(p);

    *t=p;
}

void DoubleRotateWithLeft(AVLTree* t)   //LR型失衡
{
    SingleRotateWithLeft(&((*t)->lchild));
    SingleRotateWithRight(t);
}

void DoubleRotateWithRight(AVLTree* t)   //双旋操作,先右后左
{
    SingleRotateWithRight(&((*t)->rchild));
    SingleRotateWithLeft(t);
}

void ChangeAVLLeft(AVLTree* t,ElemType e)   //检查左子树
{
        Insert( &(*t)->lchild, e );
        
        if( GetHeight((*t)->lchild) - GetHeight((*t)->rchild) != 2 )
        {
            (*t)->height=MAX(GetHeight((*t)->lchild),GetHeight((*t)->rchild))+1;
            return ;
        }
                                                //AVL树不平衡  
        if( e < (*t)->lchild->data )            //LL插入到左子树左边  
            SingleRotateWithRight( &(*t) );  
        else  
            DoubleRotateWithLeft( &(*t) );      //LR插入到左子树右边,先对左子树左旋,再对当前根节点右旋  

        (*t)->height=MAX(GetHeight((*t)->lchild),GetHeight((*t)->rchild))+1;

}
void ChangeAVLRight(AVLTree* t,ElemType e)   //检查左子树
{
        Insert( &(*t)->rchild, e );

        if( GetHeight((*t)->lchild) - GetHeight((*t)->rchild) != -2 )
        {
            (*t)->height=MAX(GetHeight((*t)->lchild),GetHeight((*t)->rchild))+1;
            return ;
        }

        if( e > (*t)->rchild->data )           //插入到右子树右边  
            SingleRotateWithLeft( &(*t) );  
         else  
            DoubleRotateWithRight( &(*t) );    //插入到右子树左边,先对右子树右旋,再对当前根节点左旋   

        (*t)->height=MAX(GetHeight((*t)->lchild),GetHeight((*t)->rchild))+1;
}
void Insert(AVLTree* t,ElemType e)       //插入函数
{
    if(*t==NULL) 
    {  
        (*t) = (AVLTree)malloc(sizeof(AVLNode));  
        (*t)->data = e;  
        (*t)->height = 0;  
        (*t)->lchild = (*t)->rchild = NULL;
        (*t)->height=MAX(GetHeight((*t)->lchild),GetHeight((*t)->rchild))+1;
        return ;
    }  
  
    if( e < (*t)->data )           //插入到左子树中  
        ChangeAVLLeft(t,e); 
  
   if( e > (*t)->data )  
       ChangeAVLRight(t,e);
}

void CreatAVL(AVLTree* t,ElemType* a,int n)  //创建AVL树函数 
{
    int i=0;

    *t=NULL;

    for (i=0;i!=n;++i)
        Insert(t,a[i]);
}

void InOrderPrint(AVLTree t)
{
    if (t==NULL)
        return ;

    InOrderPrint(t->lchild);
    printf("%d ",t->data);
    InOrderPrint(t->rchild);
}


就是插入那里感觉很复杂~弄了很久~

[此贴子已经被作者于2017-3-18 20:16编辑过]

搜索更多相关主题的帖子: 资料 网上 搜搜 
2017-03-18 20:15
marlow
Rank: 6Rank: 6
等 级:侠之大者
威 望:2
帖 子:125
专家分:419
注 册:2016-7-18
收藏
得分:2 
不知道为什么函数的形式参数要搞成指针的指针,然后在函数体内又是取值又是加括号的←_←

一切都在学习、尝试、摸索中
2017-03-18 23:03
烟雨晨曦
Rank: 7Rank: 7Rank: 7
等 级:黑侠
威 望:7
帖 子:150
专家分:599
注 册:2017-3-5
收藏
得分:2 
回复 2楼 marlow
指针传递,函数执行时只会传递一个指针而已,而如果值传递,会复制一份传递进来的值的拷贝,如果所占内存小还无所谓,大的话影响程序执行效率,而指针传递就不会有这个问题,值本身再大也无所谓,传递过来的就一个地址。
2017-03-18 23:31
lin5161678
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:45
帖 子:1136
专家分:3729
注 册:2011-12-3
收藏
得分:2 
回复 2楼 marlow
直接传递指针无法修改指针的值
只能修改指针指向对象的值
所以要修改指针得传入一个指向指针的指针
也就是 二级指针

https://zh.
2017-03-19 02:21
快速回复:AVL树~
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.022048 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved