balanced tree.cpp

数据结构实验 平衡二叉树的各种操作 包括删除操作

#include<stdio.h>
#include<malloc.h>
#include <stdlib.h>



typedef struct BSTnode{
	int data;
	int bf;
	struct BSTnode *lchild,*rchild;
}BSTnode,*bstree;



#define LH +1
#define EH 0
#define RH -1

#define TRUE 1
#define FALSE 0

int taller=0;		//taller反映T长高与否
int shorter=0;		//shorter反映T变矮与否



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

////左旋
bstree L_Rotate(bstree &p){
	bstree rc;
	rc=p->rchild;
	p->rchild=rc->lchild;
	rc->lchild=p;
	p=rc;
	return p;
}

/////左平衡处理
bstree LeftBalance(bstree &T){
	bstree lc,rd;
	lc=T->lchild;				//lc指向*T的左子树根结点
	switch(lc->bf)	{			//检查*T的左子树平衡度，并做相应的平衡处理
		case LH:				//新结点插入在*T的左孩子的左子树上，要做单右旋处理
			T->bf=lc->bf=EH;
			T=R_Rotate(T);
			break;
		case RH:				//新结点插入在*T的左孩子的右子树上，要做双旋处理
			rd=lc->rchild;		//rd指向*T的左孩子的右子树根
			switch(rd->bf){		//修改*T及其左孩子的平衡因子
				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;
			}//////////switch(rd->bf)
			rd->bf=EH;
			T->lchild=L_Rotate(T->lchild);	//对*T的左孩子做左旋平衡处理
			T=R_Rotate(T);					//对*T做右旋处理
	}////////switch(lc->bf)
	return T;
}




////右平衡处理
bstree RightBalance(bstree &T)
{   
	bstree rc,ld;
	rc=T->rchild;				//rc指向*T的右子树根结点
	switch(rc->bf)	{			//检查*T的右子树平衡度，并做相应的平衡处理
		case RH:				//新结点插入在*T的右孩子的右子树上，要做单右旋处理
			T->bf=rc->bf=EH;
			T=L_Rotate(T);
			break;
		case LH:				//新结点插入在*T的右孩子的左子树上，要做双旋处理
			ld=rc->lchild;		//ld指向*T的右孩子的左子树根
			switch(ld->bf){		//修改*T及其右孩子的平衡因子
				case LH:
					T->bf=EH;
					rc->bf=RH;
					break;
				case EH:
					T->bf=rc->bf=EH;
					break;
				case RH:
					T->bf=LH;
					rc->bf=EH;
					break;
			}///switch(ld->bf)
			ld->bf=EH;
			T->rchild=R_Rotate(T->rchild);	//对*T的右孩子做右旋平衡处理
			T=L_Rotate(T);					//对*T做左旋处理
	}/////switch(rc->bf)
	return T;
}




bstree InsertAVL(bstree &T, int e)
{   
	bstree p;
	//插入新结点，树长高置taller为TRUE
	if(!T)	{
		T=(bstree)malloc(sizeof(BSTnode));
		T->data=e;
		T->lchild=T->rchild=NULL;
		T->bf=EH;
		taller=TRUE;
	}
	else	{
		//树中存在和e有相同关键字的结点则不再插入
		if(e==T->data){
			taller=FALSE;
			return NULL;
		}

		//值小于则继续在树的左子树中搜索
		if(e < T->data){
			//插入到左子树且左子树长高
			p=InsertAVL(T->lchild,e);
			if(p){
				T->lchild=p;
				if(taller)	{
					switch(T->bf){				//检查*T的平衡度
						case LH:				//原本左子树比右子树高，需要做左平衡处理
							T=LeftBalance(T);
							taller=FALSE;
							break;
						case EH:				//原本左子树和右子树同高，现因左子树争高而使树增高
							T->bf=LH;
							taller=TRUE;
							break;
						case RH:				//原本右子树比左子树高，现在左右子树等高
							T->bf=EH;
							taller=FALSE;
							break;
					}///////switch(T->bf)
				}///////if(taller)
			}/////if(p)
		}///////if(e < T->data)
		//继续在*T的右子树中搜索
		else{
			//插入到右子树且使右子树长高
			p=InsertAVL(T->rchild,e);
			if (p){
				T->rchild=p;
				if(taller)	{
					switch(T->bf){				//检查*T的平衡度
						case LH:				//原本左子树比右子树高，现在左右子树等高
							T->bf=EH;
							taller=FALSE;
							break;
						case EH:				//原本左子树和右子树同高，现因右子树增高而使树增高
							T->bf=RH;
							taller=TRUE;
							break;
						case RH:				//原本右子树比左子树高，需要做右平衡处理
							T=RightBalance(T);	
							taller=FALSE;
							break;
					}//////switch(T->bf)
				}/////if(taller)
			}/////if (p)
		}//////if(e > T->data)
	}///////else
	return T;
}



int Preordertraverse(bstree T){
	if(T){
			printf(" %d %d\n",T->data,T->bf);
			Preordertraverse(T->lchild);
			Preordertraverse(T->rchild);
	}
	return 1;
}




int FindAVL(bstree p,int e){
	if(p==NULL)return NULL;
	else if(e==p->data) return true;
		else if(e<p->data){
						p=p->lchild;
						return	FindAVL(p, e);		
						}////左子树上查找
				else {
						p=p->rchild;
					return	FindAVL( p, e);
						}////右子树上查找
}



int Delete(bstree &T,int e){
	//删除结点
	bstree p,q;
	e=0;
	p=T;
	if(!T->rchild) {//右子数为空需要重接它的左子数
	    T=T->lchild;
		free(p);
		shorter=true;
		}
	else if(!T->lchild) {//重接它的右子数
		T=T->rchild;
		free(p);
		shorter=true;
		}
		else{ //左右子数均不空
			q=T->lchild;
			while(q->rchild!=NULL){//转左，然后向右到尽头
							q=q->rchild;
						}
			e=q->data;
			}
		return e;
}






void Delete_Rightbalance(bstree &T){
	///////////删除在左子树上的，相当于插入在右子树
	bstree rc=T->rchild,ld;
	switch(rc->bf){
	case LH://///////双旋 ，先右旋后左旋
		ld=rc->lchild;
		rc->lchild=ld->rchild;
		ld->rchild=rc;
		T->rchild=rc->lchild;
		rc->lchild=T;
		switch(ld->bf)	{
				case LH:T->bf=EH;
						rc->bf=RH;	
						break;
				case EH:T->bf=rc->bf=EH;
						break;
				case RH:T->bf=LH;
						rc->bf=EH;
						break;
				}
		ld->bf=EH;
		T=rc;
		shorter=true;break;
	case EH:///////删除在左子树，相当于插入在右子树，左单旋
		T->rchild=rc->lchild;
		rc->lchild=T;
		rc->bf=LH;
		T->bf=RH;
		T=rc;
		shorter=EH;break;
	case RH:///////删除在左子树，相当于插入在右子树，左单旋
		T->rchild=rc->lchild;
		rc->lchild=T;
		rc->bf=T->bf=EH;
		T=rc;
		shorter=true;break;
	}
}



void Delete_Leftbalance(bstree &T)/////删除右子树上的，相当于插入在左子树上
{
		bstree p1,p2;
		p1=T->lchild;
		switch(p1->bf) 	{
				case LH:T->lchild=p1->rchild;//////右旋
					p1->rchild=T;
					p1->bf=T->bf=EH;
					T=p1;	
					shorter=true;
					break;
				case EH:T->lchild=p1->rchild;///////右旋
						p1->rchild=T;
						p1->bf=RH;
						T->bf=LH;
						T=p1;
						shorter=false;
						break;
				case RH:p2=p1->rchild;//////////右双旋
						p1->rchild=p2->lchild;
						p2->lchild=p1;
						T->lchild=p2->rchild;
						p2->rchild=T;
						switch(p2->bf){
											case LH:T->bf=RH;p1->bf=EH;break;
											case EH:T->bf=EH;p1->bf=EH;break;
											case RH:T->bf=EH;p1->bf=LH;break;
										}
				p2->bf=EH;
				T=p2;
			shorter=true;break;
			} 
}


bstree DeleteAVL(bstree &T,int e){
	//删除后要保证该二叉树还是平衡的
	int n,m=0;/////标记
	bstree q;
	if(!T)return NULL;
	else	{
		if(e==T->data)	{////直接删除
			n=Delete(T,e);
			m=n;
			if(m!=0) {
				q=T;
				DeleteAVL(T,m);
				q->data=m;}	
		}
		else {
					if(e<T->data){////在左子树上寻找
							DeleteAVL(T->lchild,e);
							if(shorter){
									switch(T->bf){
														case LH:T->bf=EH;shorter=true;break;
														case EH:T->bf=RH;shorter=false;break;
														case RH:Delete_Rightbalance(T);shorter=true;break;
												}////switch(T->bf)
											}/////if(shorter)
									}/////if(e<T->data)
					else{ /////////在右子树上寻找
					DeleteAVL(T->rchild,e);
					if(shorter)
						switch(T->bf){
												case LH:Delete_Leftbalance(T);shorter=true;break;
												case EH:T->bf=LH;shorter=false;break;
												case RH:T->bf=EH;shorter=true;break;
										}////////switch(T->bf)
						}////////在右子数上寻找完
				}////////在左右子上完
		}///////////删除完
return T;
}












void main(){
	bstree T;
	T=NULL;
	int e,b,t,c,d;
	printf("请按广度遍历输入平衡二叉树，中间以回车键隔开，输入0为结束\n");
	while(e!=0){
		scanf("%d",&e);
		if(e!=0)	InsertAVL(T,e);
	}
	printf("请输入要插入的节点,不插入则输入0\n");
	scanf("%d",&d);
	while(d!=0){
		if(d!=0)	InsertAVL(T,d);
		Preordertraverse(T);
		printf("请继续输入要插入的节点,不插入则输入0\n");
		scanf("%d",&d);
	}

	printf("请输入要查找的节点\n");
	scanf("%d",&t);
	c=FindAVL(T,t);
	if(c==1)printf("有要查找的节点\n");
	else printf("无要查找的节点\n");
	
	
	do{
		printf("请输入要删除的节点\n");
		scanf("%d",&b);
		DeleteAVL(T,b);
		Preordertraverse(T);
		printf("继续删除请输入1\n");
		scanf("%d",&b);
	}while(b==1);
}