用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编辑过]