treefile.h

数据结构 Balance-Bi-Tree 数据结构 Balance-Bi-Tree 数据结构 Balance-Bi-Tr

//头文件
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>

//宏定义
#define NULL 0
#define LH 1
#define EH 0
#define RH -1
#define TRUE 1
#define FALSE 0

//平衡二叉树的结构定义
typedef struct BSTNode{
	int data;
	int bf;
	struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

//右旋
void R_Rotate(BSTree &p)
{
	BSTree lc;
	lc=p->lchild;
	p->lchild=lc->rchild;
	lc->rchild=p;
	p=lc;
}

//左旋
void L_Rotate(BSTree &p)
{
	BSTree lc;
	lc=p->rchild;
	p->rchild=lc->lchild;
	lc->lchild=p;
	p=lc;
}

//左旋调平衡
void Leftbalance(BSTree &T)
{
	BSTree 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);
	}
}
//左旋调平衡（用于删除结点）
void Leftbalanced(BSTree &T,int &fag)
{
	BSTree lc,rd;
	lc=T->lchild;
	switch(lc->bf){
	  case LH:
		T->bf=lc->bf=EH;
		R_Rotate(T);
		break;
	  case EH:
		if(lc->rchild){
			T->bf=LH;
			lc->bf=RH;
			R_Rotate(T);
			fag=1;}
		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);
	}
}

//右旋调平衡
void Rightbalance(BSTree &T)
{
	BSTree 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=LH;
			lc->bf=EH;
			break;
		}
		rd->bf=EH;
		R_Rotate(T->rchild);
		L_Rotate(T);
	}
}

//右旋调平衡（用于删除结点）
void Rightbalanced(BSTree &T,int &fag)
{
	BSTree lc,rd;
	lc=T->rchild;
	switch(lc->bf){
	  case RH:
		T->bf=lc->bf=EH;
		L_Rotate(T);
		break;
	  case EH:
		if(lc->rchild){
			T->bf=RH;
			lc->bf=LH;
			L_Rotate(T);
			fag=1;}
		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=LH;
			lc->bf=EH;
			break;
		}
		rd->bf=EH;
		R_Rotate(T->rchild);
		L_Rotate(T);
	}
}

//向平衡二叉树中插入结点，并调平衡
void InsertAVL(BSTree &T,int e,int &taller)
{
	if(!T){
	  T=(BSTree)malloc(sizeof(BSTNode));
	  T->data=e;
	  T->lchild=T->rchild=NULL;
	  T->bf=EH;
	  taller=TRUE;
	}
	else{
	  if(e==T->data)
		{taller=FALSE; return;}
	  if(e<T->data){
		InsertAVL(T->lchild,e,taller);
		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{
		InsertAVL(T->rchild,e,taller);
		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;
		  }
	  }
	}
}

//创建一个结点的树
void creattree(BSTree &T,int e)
{
	T=(BSTree)malloc(sizeof(BSTNode));
	T->data=e;
	T->bf=EH;
	T->lchild=T->rchild=NULL;
}


//删除结点中，所删结点之下调平衡，递归算法
void InLBalance(BSTree &T,BSTree &f,int &shorter,int &tag,int &fag)
{
	if(T->rchild)
	  InLBalance(T->rchild,T,shorter,tag,fag);
	else{
	if(tag==1){
	  if(shorter)
	    switch(f->bf){
		case LH:  Leftbalanced(f,fag);
			     if(fag)  
					{shorter=0;fag=0;}
			     else	  shorter=1;
				 break;
		case EH:  f->bf=LH;
			   shorter=0;break;
		case RH:  f->bf=EH;
			   shorter=1;break;
	    }
	   tag=0;
	}
	else  
	  if(shorter)
	    switch(T->bf){
		case LH:  Leftbalanced(T,fag);
			     if(fag)  
					{shorter=0;fag=0;}
			     else	  shorter=1;
				 break;
		case EH:  T->bf=LH;
			   shorter=0;break;
		case RH:  T->bf=EH;
			   shorter=1;break;
	    }
	}
}

//删除所要删的结点，并调平衡
void  delet(BSTree &p,BSTree &f,int &shorter)
{
	int flag=0,tag=0,fag=0;
	BSTree pre,s,q;
	if(!f)  
		flag=0;
	else
	  if(f->lchild==p)  flag=1;
	  else     flag=-1;
	if(!p->rchild && !p->lchild)
		{pre=NULL;free(p);shorter=1;}
	else if(!p->rchild){
		pre=p->lchild;
		shorter=1;
		free(p);
	}
	else if(!p->lchild){
		pre=p->rchild;
		shorter=1;
		free(p);
	}
	else{
	  q=p;s=p->lchild;
	  while(s->rchild)
		{q=s;s=s->rchild;}
	  if(q!=p){
		if(s->lchild==NULL)	
			tag=0;
		else	
			tag=1;
		shorter=1;
		q->rchild=s->lchild;
		InLBalance(p->lchild,p,shorter,tag,fag);
		fag=0;
		s->lchild=p->lchild;
		s->rchild=p->rchild;
		pre=s;	  
	  }
	  else{
		s->rchild=p->rchild;
		pre=s;shorter=1;
	  }
	  pre->bf=p->bf;
	  if(shorter)
		switch(pre->bf){
		  case LH:  pre->bf=EH;
			     shorter=1;break;
		  case EH:  pre->bf=RH;
			     shorter=0;break;
		  case RH:  Rightbalanced(pre,fag);
			     if(fag)  shorter=0;
			     else	  shorter=1;
				 break;
	  	}
	  free(p);
	}
	if(flag==0)
	  {f=NULL;p=pre;}
	else if(flag==1)
	  {f->lchild=pre;p=pre;}
	else if(flag==-1)
	  {f->rchild=pre;p=pre;}
}

//向平衡二叉树中删除结点
void deletnode(BSTree &T,int k,BSTree &f,int &shorter,int &fag)
{
	if(T){
	  if(T->data==k)
		delet(T,f,shorter);
	  else if(T->data>k){
		deletnode(T->lchild,k,T,shorter,fag);
		if(shorter)
		   switch(T->bf){
			case LH:  T->bf=EH;
			   	   shorter=1;break;
			case EH:  T->bf=RH;
				   shorter=0;break;
			case RH:  Rightbalanced(T,fag);
			     if(fag)  
				 {shorter=0;fag=0;}
			     else	  shorter=1;
				 break;
		   }
	  }
	  else{
		deletnode(T->rchild,k,T,shorter,fag);
		if(shorter)
		   switch(T->bf){
			case LH:  Leftbalanced(T,fag);
			     if(fag)  
				 {shorter=0;fag=0;}
			     else	  shorter=1;
				 break;
			case EH:  T->bf=LH;
				   shorter=0;break;
			case RH:  T->bf=EH;
				   shorter=1;break;
		   }
	  }
	}
}

//先序遍历树，获取结点信息
void preorder(BSTree &T,int *c,int *d,int *bf,int &i)
{
	int t;
	if(T){
	  c[i]=1;
	  d[i]=T->data;
	  bf[i]=T->bf;
	  t=i; i=t*2;
	  preorder(T->lchild,c,d,bf,i);
	  i=t*2+1;
	  preorder(T->rchild,c,d,bf,i);
	}
}