C兑现平衡二叉树-AVL

C实现平衡二叉树---AVL

/************************************************************************/  
/*                    C实现平衡二叉树---AVL                             */  
/************************************************************************/  
#include <stdio.h>  
#include <stdlib.h>  
#define LH (+1)  
#define EH  0  
#define RH (-1)  
#define TRUE 1
#define FALSE 0
typedef 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;  
}