数据结构之---C语言实现平衡二叉树（AVL树）

//avl(自动平衡二叉树)
#include 
#include 
typedef int elemtype;
//每个结点的平均值
typedef enum
{
 	eh = 0,
 	lh = 1,
 	rh = -1 
}bh_t;

typedef enum
{
  	false = 0,
  	true = 1
}bool_t;

//定义平衡二叉树
typedef struct bstnode
{
 	elemtype key;								//平衡值
 	int bf;                             
 	struct bstnode *lchild,*rchild;				
}bstnode, *bstree;


//中序遍历
void inordertraverse(bstree root)
{
 	if(null != root)
 	{
  		inordertraverse(root->lchild);
  		printf(%d	,root->key);
  		inordertraverse(root->rchild);
	}
}


//前序遍历
void preordertraverse(bstree root)
{
 	if(null != root)
	{
  		printf(%d	,root->key);
  		preordertraverse(root->lchild);
  		preordertraverse(root->rchild);
 	}
}


//右旋
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;
 	bstree rd = lc->rchild;
 	//判断进行向哪边旋转
	switch(lc->bf)
 	{
  		case lh:
   			(*t)->bf=lc->bf=eh;
   			r_rotate(t);
   			break;
  		case rh:
   			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(bstree *t)
{
 	bstree rc=(*t)->rchild;
 	bstree ld=rc->lchild;
 	switch(rc->bf)
 	{
  		case rh:
   			(*t)->bf=rc->bf=eh;
   			l_rotate(t);
   			break;
  		case lh:
   			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;
 }
}


//插入元素
bool_t insertavl(bstree *t,elemtype e,bool_t *taller)
{
 	if(null == t)
  		return false;
 	if(null == *t)
 	{
  		*t=(bstree)malloc(sizeof(bstnode));
  		if(null == *t)
   			return false;
  		(*t)->key=e;
  		(*t)->lchild=(*t)->rchild=null;
  		(*t)->bf=eh;
  		*taller=true;
 	}
 	else
 	{
  		if(e==(*t)->key)
  		{
   			*taller=false;
   			return false;
  		}
 		if(e<(*t)->key)
  		{
   			if(false == insertavl(&((*t)->lchild),e,taller))
    			return false;
   			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(false == insertavl(&((*t)->rchild),e,taller))
    			return false;
   			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 true;
}


bstree searchavl(bstree t,elemtype key)
{
 	bstree p=t;
 	while(p)
 	{
  		if(p->key==key)
   			return p;
  		else if(p->keyrchild;
  		else
   			p=p->lchild;
 	}
 	return p;
}

static void destroy(bstree *t)
{
 	if(null != *t)
 	{
  		destroy(&((*t)->lchild));
  		destroy(&((*t)->rchild));
  		free(*t);
  		*t = null;
 	}
 	return;
}
void destroyavl(bstree root)
{
 	if(null != root)
 	{
  		destroy(&root);
 	}
 	return;
}

int main()
{
 	bstree root=null,r;
 	bool_t taller=false;
 	int array[]={13,24,37,90,53};
 	int i = 0;
 	for(i=0; i < 5; i++)
  		insertavl(&root,array[i],&taller);
 	printf(中序遍历:
);
 	inordertraverse(root);
 	printf(
先序遍历
);
 	preordertraverse(root);
	printf(
搜索：37
);
 	r=searchavl(root,37);
 	if(r)
 	{
  		printf(%d
,r->key);
 	}
 	else
 	{
 	 	printf(not find!
);
 	}
 	destroyavl(root);
 	root = null;
 	return 0;
}

 

结果：