6.cpp

平衡二叉树的操作演示

#include<stdio.h>
#include<stdlib.h>
#define LH +1
#define EH 0
#define RH -1
typedef struct BSTNode
{
	int data;
	int bf;
	struct BSTNode *LC,*RC;
}BSTNode,*BSTree;//define the stytle of node

int lap;
void R_Rotate(BSTree &P)//对以*p为根的二叉排序树作左旋处理
{
	BSTree lc;
	lc = P->LC;
	P->LC = lc->RC;
	lc->RC = P;P = lc;
}


void L_Rotate(BSTree &P)//对以*p为根的二叉排序树作右旋处理
{
	BSTree rc;
	rc = P->RC;
	P->RC = rc->LC;
	rc->LC = P;P = rc;
}


void LeftBalance(BSTree &T)
{
	BSTree lc,  rd;
	lc = T->LC;
	switch(lc->bf)
	{
	case LH:
		T->bf = lc->bf= EH;
		R_Rotate(T);break;
	case RH:
		rd = lc->RC;
		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->LC);
		R_Rotate(T);
	}
}//LeftBalance

void RightBalance(BSTree &T)
{
	BSTNode *rc;
    BSTNode *ld;
	rc=T->RC;
	switch(rc->bf)
	{
	case RH:T->bf=EH;rc->bf=EH;L_Rotate(T);break;
	case LH:ld=rc->LC;
		switch(ld->bf)
		{
		case LH:T->bf=EH;rc->bf=RH;break;
		case EH:T->bf=EH;rc->bf=EH;break;
		case RH:T->bf=LH;rc->bf=EH;break;
		}
		ld->bf=EH;
		R_Rotate(T->RC);
		L_Rotate(T);
	}
}


BSTree searchBST(BSTree T,int e)
{
	if(!T)
	{
		if(lap==1)

		printf("查找不成功!\n");return 0;
	}
	if(T->data==e)
	{
		if(lap==1)
		printf("查找成功!\n"); 
		return(T);//特殊情况，查找结束
	}
	else if (e<T->data) return (searchBST(T->LC,e));
	else return (searchBST(T->RC,e));
	
}

int InsertAVL(BSTree &T,int e,bool &taller)
{
	if(!T)//空树的情况
	{
		T = (BSTree)malloc(sizeof(BSTNode));
		T->data = e;
		T->LC=T->RC=NULL;
		T->bf = EH;
		taller = true;
	}
	else
	{
		if(	e==T->data)
		{
			taller = false;
			return 0;
		}
		if(e<T->data)
		{
			if(!InsertAVL(T->LC,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;
			
			}	//switch()
		}
		else 
		{
			if(!InsertAVL(T->RC,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;
}//InsertAVL


void  print_Bitree(BSTree T,int i)//凹入表显示递归函数,i表示层数,初始值为0
{
	if(!T)
	{
		printf("此树为空树!\n") ;
	return ;
	}
	int j;
	if(T->RC)
		print_Bitree(T->RC,i+2);
	for(j=1;j<=i;j++)
		printf(" ");
	printf("%d\n",T->data);
	if(T->LC)
		print_Bitree(T->LC,i+2);	
	
}
int Delete(BSTree &T,int e,int low)  
{//删除结点e
	
	BSTree p,q,t;
	if (e<T->data)                                  
	{
		if (!Delete(T->	LC,e,low))
			return 0;
		if (low)                            
			switch(T->bf)                   
		{
                 case LH:
					 T->bf =EH;
					 low=1;
					 break;
				 case EH:
					 T->bf = RH;
					 low=0;
					 break;
				 case RH:
					 RightBalance(T);
					 low=1;
					 break;
		}
	}
	else if(e>T->data)
	{
		if (!Delete(T->RC,e,low))   //右子树寻找
			return 0;
		if (low)                           //树“变矮”
			switch(T->bf)                     //调整树的平衡度
		{
					case LH:
                        LeftBalance(T);						
						low=1;
						break;
					case EH:
						T->bf = LH;
						low=0;
						break;
					case RH:
                        T->bf = EH;
						low=1;
						break;
		}
	}
	else                                  //找到要删除结点e
	{
		
		if (T->RC == NULL)                  //右子树为空
		{
			
			if (T->LC == NULL)              //叶子结点，直接删除
			{
				free(T);
				T = NULL;
			}
			else                                //左子树非空，左子树直接代替他的位置
			{
				p= T->LC;
				T->bf=p->bf;
				T->data=p->data;
				T->LC=p->LC;
				T->RC=p->RC;
				free(p);
			}
			return 1;
		}                                   
		else                                   //左右子树都不为空
		{
			p=T;                            
			q=T->RC;
			while(q->LC)
			{
				p=q;
				q=q->LC;
			}
			if(!q->RC)                  
			{
				if(T->RC->LC&&T->RC->RC)    
				{
					T->bf=q->bf;
					T->data=q->data;
					p->LC=NULL;
					free(q);
				}
				else                                      
				{
					T->bf=q->bf;
					T->data=q->data;
					T->RC=NULL;
					free(q);
				}
			}
			else                             
			{
				p=q->RC;                 //先把T值与q值交换
				T->bf=q->bf;
				T->data=q->data;
				while(p)                     //将原来的T值递归的向q的右子树传递直至树叶
				{
					q->bf=p->bf;
					q->data=p->data;
					t=q;
					q=p;
					p=q->RC;
					
				}
				t->RC=NULL;             //删除带有T值的叶子结点
				free(q);
			}
			return 1;
		}
		
		
		
		switch(T->bf)                        //调整树的平衡度
		{
		case LH:
			LeftBalance(T);						
		low=1;
			break;
		case EH:
			T->bf = LH;
			low=0;
			break;
		case RH:
			T->bf = EH;
			low=1;
			break;
		}
	}	
	return 1;              
}



void main()
{
	int c,keyword;
	bool low=false;
	bool taller=false;
	BSTree T=NULL;
    printf("平衡二叉树操作演示:\n");
	printf("0. EIXT\n1.SEARCH\n2.INSERT\n3.DELETE\n");
	printf("请输入功能选择序号(0~3):\n");
	scanf("%d",&c);
	if(c==0)
        exit(0);
	while(true)
	{
		lap=0;
		switch(c)
		{
		case 1:lap=1;
			printf("请输入要查找的关键字:\n");
		
			scanf("%d",&keyword);
			searchBST(T,keyword);
			break;//查找功能
		case 2:
			
			printf("请输入要插入的关键字:\n");
			scanf("%d",&keyword);
			InsertAVL(T,keyword,taller);
			printf("凹入表显示平衡二叉树如下所示:\n");
            print_Bitree(T,0);
			break;//插入功能
		case 3:
			lap=3;
			printf("请输入要删除的关键字:\n");
			getchar();
			scanf("%d",&keyword);
			if	(!searchBST(T,keyword))
			{
			   printf("树中不存在要删除的结点\n");
			break;
			}
			Delete(T,keyword,low);
	        printf("凹入表显示平衡二叉树如下所示:\n");
            print_Bitree(T,0);
			break;//删除功能
		default: 
			printf("输入错误请重新输入:\n"); break;
		}
		printf("请输入功能选择序号:\n");
		scanf("%d",&c);
		if(c==0) 
         exit(0);
	}
}//主函数界面