C实现平衡二叉树---AVL
/************************************************************************/ /* C实现平衡二叉树---AVL */ /************************************************************************/ #include <stdio.h> #include <stdlib.h> #define LH (+1) #define EH 0 #define RH (-1) #define TRUE 1#define FALSE 0typedef int ElemType; typedef struct BiTNode{ ElemType data; int bf;//balance flag struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; void R_Rotate(BiTree* p) { BiTree lc = (*p)->lchild; (*p)->lchild = lc->rchild; lc->rchild = *p; *p = lc; } void L_Rotate(BiTree* p) { BiTree rc = (*p)->rchild; (*p)->rchild = rc->lchild; rc->lchild = *p; *p = rc; } void LeftBalance(BiTree* T) { BiTree lc,rd; lc = (*T)->lchild; switch (lc->bf) { case LH: { (*T)->bf = lc->bf = EH; R_Rotate(T); break; } case RH: {rd = lc->rchild; switch(rd->bf){ case LH: {(*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(BiTree* T) { BiTree lc,rd; lc= (*T)->rchild; switch (lc->bf) { case RH: {(*T)->bf = lc->bf = EH; L_Rotate(T); break;} case LH:{rd = lc->lchild; switch(rd->bf){ case LH: {(*T)->bf = EH;lc->bf = RH; break;} case EH: {(*T)->bf = lc->bf = EH; break;} case RH: {(*T)->bf = EH;lc->bf = LH; break;}} } rd->bf = EH; R_Rotate(&(*T)->rchild); L_Rotate(T); break; } } int InsertAVL(BiTree* T,ElemType e,int* taller) { if ((*T)==NULL) { *T=(BiTree)malloc(sizeof(BiTNode)); (*T)->bf = EH; (*T)->data = e; (*T)->lchild = NULL; (*T)->rchild = NULL; *taller=TRUE; } else if (e == (*T)->data) { *taller = FALSE; return 0; } else if (e < (*T)->data) { 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 LH: {(*T)->bf = EH;*taller = FALSE; break;} case EH: {(*T)->bf = RH;*taller = TRUE; break;} case RH: {RightBalance(T); *taller = FALSE; break;} } } } return 1; } int FindNode(BiTree root,ElemType e,BiTree* pos) { BiTree pt = root; (*pos) = NULL; while(pt) { if (pt->data == e) { //找到节点，pos指向该节点并返回true (*pos) = pt; return TRUE; } else {if (pt->data>e) { pt = pt->lchild; } else {pt = pt->rchild; } } } return FALSE; } void InorderTra(BiTree root) { if(root->lchild) { InorderTra(root->lchild); } printf("%d ",root->data); if(root->rchild) { InorderTra(root->rchild); }} int main() { int i,nArr[] = {1,23,45,43,38,95,23,42,55}; BiTree root=NULL,pos; int taller; for (i=0;i<9;i++) { InsertAVL(&root,nArr[i],&taller); } InorderTra(root); if(FindNode(root,95,&pos)) { printf("\n%d\n",pos->data); } else { printf("\nNot find this Node\n"); } return 0; }