AVL树及其实现 引言
平衡二叉树由于logN的时间效率,在排序和查找中有重要应用。 实现 形态匀称的二叉树称为平衡二叉树 (Balanced binary tree) ,其严格定义是: 一棵空树是平衡二叉树;若 T 是一棵非空二叉树,其左、右子树为 TL 和 TR ,令 hl 和 hr 分别为左、右子树的深度。当且仅当 ①TL 、 TR 都是平衡二叉树; ② | hl - hr |≤ 1; 时,则 T 是平衡二叉树。 以下是它的c代码实现,具体思想参见<<数据结构>>(严蔚敏)一书。 #include <stdio.h> #include <malloc.h> #define LH 1 //左高 #define EH 0 //等高 #define RH -1//右高 #define TRUE 1 #define FALSE 0 typedef int ElemType; typedef struct BSTNode { ElemType key; int bf; struct BSTNode *lchild,*rchild; }BSTNode,*BSTree; //平衡树的定义 //中序遍历 void InOrderTraverse(BSTree root) { if(root) { InOrderTraverse(root->lchild); printf("%d, ",root->key); InOrderTraverse(root->rchild); } } //前序遍历 void PreOrderTraverse(BSTree root) { if(root) { printf("%d, ",root->key); PreOrderTraverse(root->lchild); PreOrderTraverse(root->rchild); } } //右旋 如图1 void R_Rotate(BSTree &p) { BSTree lc=p->lchild; p->lchild=lc->rchild; lc->rchild=p; p=lc; } //左旋 void L_Rotate(BSTree &p) { BSTree rc=p->rchild; p->rchild=rc->lchild; rc->lchild=p; p=rc; } //左平衡处理 void LeftBalance(BSTree &T) { BSTree lc=T->lchild; switch(lc->bf) { case LH: T->bf=lc->bf=EH; R_Rotate(T); break; case RH: BSTree rd=lc->rchild; switch(rd->bf) { case LH: //如图2所示 T->bf=RH; lc->bf=EH; break; case EH: T->bf=lc->bf=EH; break; case RH: T->bf=EH; lc->bf=LH; break; } rd->bf=EH; L_Rotate(T->lchild);//先左旋 R_Rotate(T);//右旋 break; } } //右平衡处理 void RightBalance(BSTree &T) { BSTree rc=T->rchild; switch(rc->bf) { case RH: T->bf=rc->bf=EH; L_Rotate(T); break; case LH: BSTree ld=rc->lchild; switch(ld->bf) { case RH: T->bf=LH; rc->bf=EH; break; case EH: T->bf=rc->bf=EH; break; case LH: T->bf=EH; rc->bf=RH; break; } ld->bf=EH; R_Rotate(T->rchild); L_Rotate(T); break; } } //在平衡二叉排序树中插入一个结点 int InsertAVL(BSTree &t,ElemType e,bool &taller) { if(!t) { t=(BSTree)malloc(sizeof(BSTNode)); t->key=e; t->lchild=t->rchild=NULL; t->bf=EH; taller=TRUE; } else { if(e==t->key) { taller=FALSE; return 0; } if(e<t->key) { if(!InsertAVL(t->lchild,e,taller)) return 0; //未插入 if(taller) { switch(t->bf) { case LH: LeftBalance(t); taller=FALSE; break; case EH: t->bf=LH; taller=TRUE; break; case RH: t->bf=EH; taller=FALSE; break; } } } else { if(!InsertAVL(t->rchild,e,taller)) return 0; //未插入 if(taller) { switch(t->bf) { case RH: RightBalance(t); taller=FALSE; break; case EH: t->bf=RH; taller=TRUE; break; case LH: t->bf=EH; taller=FALSE; break; } } } } return 1; } //查找key,若没找到,则返回NULL BSTree Search(BSTree t,ElemType key) { BSTree p=t; while(p) { if(p->key==key) return p; else if(p->key<key) p=p->rchild; else p=p->lchild; } return p; } /**/ int main(int argc,char *argv[]) { BSTree root=NULL,r; bool taller=FALSE; int array[]={13,24,37,90,53}; for(int i=0;i<5;i++) InsertAVL(root,array[i],taller); printf("inorder traverse\n"); InOrderTraverse(root); printf("\npreorder traverse\n"); PreOrderTraverse(root); printf("\nsearch key\n"); r=Search(root,37); if(r) { printf("%d\n",r->key); } else { printf("not find!\n"); } } 图1. 图2 输出结果如下: |
|