GitCode-AI社区

#include <iostream>
#include <string>
#include <fstream>
using namespace std;

const int LH = 1;
const int EH = 0;
const int RH = -1;

typedef struct BSTNode
{
	string* data;
	int bf;//balance factor
	struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;

//右旋处理,处理后p指向新的树根结点,即原先树根的左子树的跟结点
void R_Rotate(BSTree &p);
//左旋处理,处理后p指向新的树根结点,即原先树根的右子树的跟结点
void L_Rotate(BSTree &p);
//对以指针T所指结点为根的二叉树做左平衡处理
void LeftBalance(BSTree &T);
//对以指针T所指结点为根的二叉树做右平衡处理
void RightBalance(BSTree &T);

//右旋处理,处理后p指向新的树根结点,即原先树根的左子树的跟结点
void R_Rotate(BSTree &p)
{
	BSTree lc = p->lchild;//lc指向*p的左子树的根结点
	p->lchild = lc->rchild;//lc的右子树挂接为*p的左子树
	lc->rchild = p;//*p挂接为lc的右子树
	p = lc;//p指向新的根结点
}

//左旋处理,处理后p指向新的树根结点,即原先树根的右子树的跟结点
void L_Rotate(BSTree &p)
{
	BSTree rc = p->rchild;
	p->rchild = rc->lchild;
	rc->lchild = p;
	p = rc;
}

/**
*若在平衡二叉排序树中不存在和e有相同关键字的结点,则插入一个数据元素为e的新结点,
*并返回1,否则返回0
*若因插入而使二叉排序树失去平衡,则做平衡选择处理,taller反应T是否变高
**/
int InsertAVL(BSTree &T, string e, bool &taller)
{
	//空树
	if(!T)
	{
		T = (BSTree)malloc(sizeof(BSTNode));
		T->data = new string(e);
		T->lchild = T->rchild = NULL;
		T->bf = EH;
		taller = true;
	}
	else
	{
		//树中已经存在和e有相同关键字的结点,不插入
		if(e == *(T->data))
		{
			taller = false;
			return 0;
		}
		//在*T的左子树中搜索
		if(e < *(T->data))
		{
			//已经存在
			if(!InsertAVL(T->lchild, e, taller))
			{
				return 0;
			}
			//插入并且*T的左子树长高
			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
			}//if
		}//if
		else
		{
			if(!InsertAVL(T->rchild, 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;
}



//对以指针T所指结点为根的二叉树做左平衡处理
void LeftBalance(BSTree &T)
{
	BSTree lc = T->lchild;
	switch(lc->bf)
	{
	case LH://新结点插入在*T的左孩子的左子树上,做LL旋转
		T->bf = lc->bf = EH;
		R_Rotate(T);
		break;
	case RH://新结点插入在*T的左孩子的右子树上,做LR旋转
		BSTree rd = lc->rchild;
		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;
		}
		rd->bf = EH;
		L_Rotate(T->lchild);
		R_Rotate(T);
	}
}



//对以指针T所指结点为根的二叉树做右平衡处理
void RightBalance(BSTree &T)
{
	BSTree rc = T->rchild;
	switch(rc->bf)
	{
	case RH:
		T->bf = rc->bf = EH;
		L_Rotate(T);
		break;
	case LH://新结点插入在*T的右子树的左孩子上,做RL旋转
		BSTree rd = rc->lchild;
		switch(rd->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;
		}
		rd->bf = EH;
		R_Rotate(T->rchild);
		L_Rotate(T);
	}
}


void InitBSTree(BSTree &T)
{
	T = NULL;

	cout<<"输入文件名:"<<endl;
	string fileName;
	cin>>fileName;
	
	fstream file(fileName.c_str());
	
	string word;
	bool taller = false;
	while(file>>word, !file.eof())
	{
		InsertAVL(T, word, taller);
		taller = false;
	}

	file.close();
	return ;
}


void DestroyBSTree(BSTree &T)
{
	if(T)
	{
		if(T->lchild)
			DestroyBSTree(T->lchild);
		if(T->rchild)
			DestroyBSTree(T->rchild);
		delete T->data;
		free(T);
		T = NULL;
	}
}


BSTree SearchBST(BSTree T, string e)
{
	if(!T || e == *(T->data))
		return T;
	else if(e < *(T->lchild->data))
		return SearchBST(T->lchild, e);
	else
		return SearchBST(T->rchild, e);
}



void InorderTraverse(BSTree T)
{
	if(T)
	{
		InorderTraverse(T->lchild);
		cout<<*(T->data)<<endl;
		InorderTraverse(T->rchild);
	}
}


void main()
{
	BSTree T;
	InitBSTree(T);
	InorderTraverse(T);
	DestroyBSTree(T);
	return ;
}