📄 bstree.cpp

📁 程序包括了平衡二叉树的查找,插入,删除,合并等操作
💻 CPP
字号:
#include <stdio.h>
#include <malloc.h>
#include "bstree.h"

//右旋转处理函数
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 rc;
	rc=p->rchild;
	p->rchild=rc->lchild;
	rc->lchild=p;
	p=rc;
}

#define LH 1
#define EH 0
#define RH -1
//创建平衡二叉树函数
int CreatAVL(BSTree &T,bool &taller)
{
	ElemType e;
	int insert;
	if(T)    //判断平衡二叉树是否为空，若不空则将该树释放
	{
		DestroyAVL(T);
			T=NULL;
	}
	printf("\n■请输入要构造的平衡二叉树:  ");
	fflush(stdin);
	e=getchar();	
	while(e!='\n')   //循环调用插入函数来构造平衡二叉树
	{	   
		InsertAVL(T,e,taller,insert);
			e=getchar();
	}
	return 1;
}
//插入函数
int InsertAVL(BSTree &T,ElemType e,bool &taller,int &insert)
{
	if(!T)   //插入新节点，这时树长高，置taller为true
	{
		T=(BSTree)malloc(sizeof(BSTNode));
		T->data=e;
		T->lchild=T->rchild=NULL;
		T->bf=EH;
		taller=true;
	}
	else
	{
		if(EQ(e,T->data))  //树中已存在和e相同的节点
		{
			insert = 0;     //将标志变量置0
			taller=false;   //不再进行插入操作
			return 0;
		}
		if(LT(e,T->data))   //左子树插入操作
		{
			if(!InsertAVL(T->lchild,e,taller,insert))
				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;
				}
		}
		else           //右子树的插入操作
		{
			if(!InsertAVL(T->rchild,e,taller,insert))
				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;
}
//插入操作时左平衡旋转处理函数
void LeftBalance(BSTree &T)
{
	BSTree lc,rd;
	lc=T->lchild;  
	switch(lc->bf)    //检查T的左子树的平衡度，并作相应的平衡处理
	{
		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 RightBalance(BSTree &T)
{
	BSTree rc,ld;
	rc=T->rchild;
	switch(rc->bf)     //检查T的右子树的平衡度，并作相应的平衡处理
	{
		case RH:T->bf=rc->bf=EH;
			    L_Rotate(T);
				break;
		case LH:ld=rc->lchild;
				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;
				R_Rotate(T->rchild);
				L_Rotate(T);
	}
}
//销毁平衡二叉树操作函数
int DestroyAVL(BSTree &T)
{
	if(!T)
		return 0;
	DestroyAVL(T->lchild);   //递归调用该函数销毁整棵平衡二叉树
	DestroyAVL(T->rchild);
	free(T);
	return 0;
}	
//查找关键字函数
int SearchAVL(BSTree &T,ElemType e,int &find)
{
	if(!T)
		return 0;
	if(EQ(e,T->data))
	{
		find = 1;    //若查找到该关键字则将find置1
		return 0;
	}
	else if(LT(e,T->data))
		SearchAVL(T->lchild,e,find);
	else
		SearchAVL(T->rchild,e,find);
	return 0;
}
//删除关键字函数
int DeleteAVL(BSTree &T,ElemType e,bool &taller,int &del)
{
	ElemType temp;
	BSTree p;
	if(!T)
	{
		del = 0;    //若到叶子节点了还未找到则将del置0
		return 0;
	}
	else
	{
		if(EQ(e,T->data))
		{
			taller=true;   //关键字存在时进行删除操作，将taller置为true
			if(T->lchild == NULL && T->rchild == NULL) //若为叶子节点则删除节点
			{
				free(T);
				T = NULL;
			}
			else if(T->lchild)  //若左子树不空，则将T->data与左子树的最右的孩子交换
			{
				p = T->lchild;
				while(p->rchild != NULL)
					p = p->rchild;
				temp = T->data;
				T->data = p->data;
				p->data = temp;
				if(!DeleteAVL(T->lchild,e,taller,del)) //递归调用左子树
					return 0;
				if(taller)    //若树不平衡则进行平衡处理
					switch(T->bf)
					{
						case LH:T->bf=EH;
							    taller=true;
								break;
						case EH:T->bf=RH;
							    taller=false;
								break;
						case RH:RightBalance2(T,taller); 
								break;
					}
			}
			else    //若左空，右子树不空，则将T->data与右子树的最左的孩子交换
			{
				p = T->rchild;
				while(p->lchild != NULL)
					p = p->lchild;
				temp = T->data;
				T->data = p->data;
				p->data = temp;
				if(!DeleteAVL(T->rchild,e,taller,del))   //递归调用左子树
					return 0;
				if(taller)   //若树不平衡则进行平衡处理
					switch(T->bf)
					{
						case LH:LeftBalance2(T,taller);  
							    taller=true;
								break;
						case EH:T->bf=LH;
							    taller=false;
								break;
						case RH:T->bf=EH;
							    taller=true;
								break;
					}
			}
			return 1;
		}
		if(LT(e,T->data))
		{
			if(!DeleteAVL(T->lchild,e,taller,del))  //当e小于T->data时递归调用其左子树
				return 0;
			if(taller)    //若树不平衡则进行平衡处理
					switch(T->bf)
					{
						case LH:T->bf=EH;
							    taller=true;
								break;
						case EH:T->bf=RH;
							    taller=false;
								break;
						case RH:RightBalance2(T,taller);
								break;
					}
		}
		else   
		{
			if(!DeleteAVL(T->rchild,e,taller,del))   //当e大于T->data时递归调用其左子树
				return 0;
			if(taller)    //若树不平衡则进行平衡处理
					switch(T->bf)
					{
						case LH:LeftBalance2(T,taller);
								break;
						case EH:T->bf=LH;
							    taller=false;
								break;
						case RH:T->bf=EH;
							    taller=true;
								break;
					}
		}
	}
	return 1;
}
//删除关键字时的右平衡旋转处理函数
void RightBalance2(BSTree &T,bool &taller)
{
	BSTree rc,ld;
	rc=T->rchild;
	switch(rc->bf)     //检查T的左子树的平衡度，并作相应的平衡处理
	{
		case RH:T->bf=rc->bf=EH;
			    L_Rotate(T);
				taller = true;
				break;
		case EH:T->bf=RH;
				rc->bf=LH;
				L_Rotate(T);
				taller = false;
				break;
		case LH:ld=rc->lchild;
				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;
				R_Rotate(T->rchild);
				L_Rotate(T);
				taller = true;
				break;
	}
}
//删除关键字时的左平衡旋转处理函数
void LeftBalance2(BSTree &T,bool &taller)
{
	BSTree lc,rd;
	lc=T->lchild;
	switch(lc->bf)    //检查T的右子树的平衡度，并作相应的平衡处理
	{
		case LH:T->bf=lc->bf=EH;
			    R_Rotate(T);
				taller = true;
				break;
		case EH:T->bf=LH;
				lc->bf=RH;
				R_Rotate(T);
				taller = false;
				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);
				taller = true;
				break;
	}
}
//合并两棵平衡二叉树的操作函数
int MergeAVL(BSTree &T1,BSTree &T2,bool &taller,int &insert)
{
	if(!T2)
		return 0;
	MergeAVL(T1,T2->lchild,taller,insert);   //用左右孩子上的递归操作实现合并操作
	InsertAVL(T1,T2->data,taller,insert);   
	MergeAVL(T1,T2->rchild,taller,insert);
	InsertAVL(T1,T2->data,taller,insert);
	return 1;
}
//输出平衡二叉树的函数
void PrintAVL(BSTree &T,int n)
{
	int i;
	if(T)
	{
		PrintAVL(T->rchild,n+1);  //递归输出
		for(i=0;i<n;++i)
			printf("   ");
		printf("%c\n",T->data);
		PrintAVL(T->lchild,n+1);
	}
}
💿 文件大小 4 K
👤 上传用户 lwc_1978
📂 所属分类数据结构
🏷️ 相关标签

#程序 #二叉树 #删除 #合并
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -