欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-05-03 17:53:49
//avl(自动平衡二叉树) #include #include typedef int elemtype; //每个结点的平均值 typedef enum { eh =...
//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;
}

 

结果:

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