AVL樹(shù)及其實(shí)現(xiàn) 引言
平衡二叉樹(shù)由于logN的時(shí)間效率，在排序和查找中有重要應(yīng)用。 實(shí)現(xiàn) 形態(tài)勻稱(chēng)的二叉樹(shù)稱(chēng)為平衡二叉樹(shù) (Balanced binary tree) ，其嚴(yán)格定義是： 一棵空樹(shù)是平衡二叉樹(shù)；若 T 是一棵非空二叉樹(shù)，其左、右子樹(shù)為 TL 和 TR ，令 hl 和 hr 分別為左、右子樹(shù)的深度。當(dāng)且僅當(dāng) ?、賂L 、 TR 都是平衡二叉樹(shù)； ?、?｜ hl － hr ｜≤ 1； 時(shí)，則 T 是平衡二叉樹(shù)。 以下是它的c代碼實(shí)現(xiàn),具體思想?yún)⒁?jiàn)<<數(shù)據(jù)結(jié)構(gòu)>>(嚴(yán)蔚敏)一書(shū)。  #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; //平衡樹(shù)的定義//中序遍歷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; }}//在平衡二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)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，若沒(méi)找到，則返回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é)果如下:  分類(lèi): 數(shù)據(jù)結(jié)構(gòu)與算法
標(biāo)簽: 數(shù)據(jù)結(jié)構(gòu), 算法 |
|
|
來(lái)自： 昵稱(chēng)1740930 > 《語(yǔ)言》
