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