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