AVL樹及其實現(xiàn) 引言
平衡二叉樹由于logN的時間效率，在排序和查找中有重要應(yīng)用。 實現(xiàn) 形態(tài)勻稱的二叉樹稱為平衡二叉樹 (Balanced binary tree) ，其嚴(yán)格定義是： 一棵空樹是平衡二叉樹；若 T 是一棵非空二叉樹，其左、右子樹為 TL 和 TR ，令 hl 和 hr 分別為左、右子樹的深度。當(dāng)且僅當(dāng) ?、賂L 、 TR 都是平衡二叉樹； ?、?｜ hl － hr ｜≤ 1； 時，則 T 是平衡二叉樹。 以下是它的c代碼實現(xiàn),具體思想?yún)⒁?lt;<數(shù)據(jù)結(jié)構(gòu)>>(嚴(yán)蔚敏)一書。  #include <stdio.h>#include <malloc.h>#define LH 1 //左高#define EH 0 //等高#define RH -1//右高 #define TRUE 1#define FALSE 0typedef 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); }}//右旋 如圖1void 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; }}//在平衡二叉排序樹中插入一個結(jié)點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，若沒找到，則返回NULLBSTree 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 輸出結(jié)果如下:  標(biāo)簽: 數(shù)據(jù)結(jié)構(gòu), 算法 |
|
|
