C语言之平衡二叉树详解

#define Ty int  //以整型数据为例
typedef struct node
{
	Ty data;             //数据
	int height;          //高度
	struct Node* LChild; //左子树
	struct Node* RChild; //右子树
}Node,AVLTree;

AVLTree* creatAVLTree(Ty data)
{
    AVLTree* tree = (AVLTree*)malloc(sizeof(AVLTree));
    assert(tree);
    tree->data = data;
    tree->height = 0;
    tree->LChild = NULL;
    tree->RChild = NULL;
    return tree;
}

//辅助函数
#define HEIGHT(x) ((x==NULL)?(-1):(x->height))
#define MAX(a,b)  ((a>b)?(a):(b))
//获取树的新高度
#define GET_NEW_HEIGHT(x) (MAX(HEIGHT(x->LChild),HEIGHT(x->RChild)) + 1)

//前序打印
void show_pre(AVLTree* root)
{
	if(root==NULL)
		return;
	printf("data:%d\theight:%d\n",root->data,root->height);
	show_pre(root->LChild);
	show_pre(root->RChild);
}

//出现不平衡的情况
//左左不平衡
Node *LL_Rotation(Node *curRoot)
{
	Node *newRoot = curRoot->LChild;
	curRoot->LChild = newRoot->RChild;
	newRoot->RChild = curRoot;

	curRoot->height = GET_NEW_HEIGHT(curRoot);
	newRoot->height = GET_NEW_HEIGHT(newRoot);
	return newRoot;
}

//右右不平衡
Node *RR_Rotation(Node *curRoot)
{
	Node *newRoot = curRoot->RChild;
	curRoot->RChild = newRoot->LChild;
	newRoot->LChild = curRoot;

	curRoot->height = GET_NEW_HEIGHT(curRoot);
	newRoot->height = GET_NEW_HEIGHT(newRoot);
	return newRoot;
}
//左右不平衡
Node *LR_Rotation(Node *curRoot)
{
	curRoot->LChild = RR_Rotation(curRoot->LChild);
	return LL_Rotation(curRoot);
}
//右左不平衡
Node *RL_Rotation(Node *curRoot)
{
	curRoot->RChild = LL_Rotation(curRoot->RChild);
	return RR_Rotation(curRoot);
}

//插入数据
Node *insertNode(Node *curRoot, Ty data)
{
	//插入分有四个大情况
	if (curRoot == NULL)			  //当前节点是空的
		curRoot = creatAVLTree(data); //如果是空就直接创建一个新的节点
	else if (data < curRoot->data)	  //要插入的数据比当前节点的数据小
	{
		//往左边跑
		curRoot->LChild = insertNode(curRoot->LChild, data);
		//插入完成之后，判断需不需要调整树
		if (HEIGHT(curRoot->LChild) - HEIGHT(curRoot->RChild) == 2)
			//因为插入的位置在左边，所以插入完成之后，左子树的高度大于等于右子树高度
			curRoot = data < curRoot->LChild->data ? LL_Rotation(curRoot) : LR_Rotation(curRoot);
	}
	else if (data > curRoot->data) //要插入的数据比当前节点的数据大
	{
		//往右边跑
		curRoot->RChild = insertNode(curRoot->RChild, data);
		if (HEIGHT(curRoot->RChild) - HEIGHT(curRoot->LChild) == 2)
			//因为插入的位置在右边，所以插入完成之后，右子树的高度大于等于左子树高度
			curRoot = data > curRoot->RChild->data ? RR_Rotation(curRoot) : RL_Rotation(curRoot);
	}
	else //要插入的数据和当前节点的数据一样大
		printf("无法插入数据\n");
	//获取新高度
	curRoot->height = GET_NEW_HEIGHT(curRoot);
	return curRoot; //插入完成之后返回当前节点的指针
}

//查找节点
//找最大节点
Node *maxNode(Node *curRoot)
{
	if (curRoot == NULL)
		return NULL;
	//往右边找
	while (curRoot->RChild)
		curRoot = curRoot->RChild;
	return curRoot;
}

//找最小节点
Node *minNode(Node *curRoot)
{
	if (curRoot == NULL)
		return NULL;
	while (curRoot->LChild)
		curRoot = curRoot->LChild;
	return curRoot;
}

//删除数据
Node *deleteNode(Node *curRoot, Ty data)
{
	//删除数据有四个大情况
	if (curRoot == NULL)	  //当前节点是空的
		return NULL;		  //删除了个寂寞直接结束掉整个函数
	if (data < curRoot->data) //要删除的数据比当前节点的数据小
	{
		//往左边跑
		curRoot->LChild = deleteNode(curRoot->LChild, data);
		//获取新高度
		curRoot->height = GET_NEW_HEIGHT(curRoot);
		//判断需不需要调整
		if (HEIGHT(curRoot->RChild) - HEIGHT(curRoot->LChild) == 2)
			curRoot = HEIGHT(curRoot->RChild->LChild) > HEIGHT(curRoot->RChild->RChild) ? RL_Rotation(curRoot) : RR_Rotation(curRoot);
	}
	else if (data > curRoot->data) //要删除的数据比当前节点的数据大
	{
		//往右边跑
		curRoot->RChild = deleteNode(curRoot->RChild, data);
		curRoot->height = GET_NEW_HEIGHT(curRoot);
		if (HEIGHT(curRoot->LChild) - HEIGHT(curRoot->RChild) == 2)
			curRoot = HEIGHT(curRoot->LChild->RChild) > HEIGHT(curRoot->LChild->LChild) ? LR_Rotation(curRoot) : LL_Rotation(curRoot);
	}
	else
	{ //要删除的数据和当前节点的数据一样大
		//针对于curRoot这个节点做删除操作
		//主要有两个主要的情况
		if (curRoot->LChild && curRoot->RChild) // curRoot有左子树和右子树
		{
			//先判断左右子树的高度，将高度比较高的子树的节点拿到上面来
			if (HEIGHT(curRoot->LChild) > HEIGHT(curRoot->RChild))
			{ //左子树的高度比右子树的高度高
				//找到左子树的最大节点
				Node *max = maxNode(curRoot->LChild);
				//找到之后就将max的数据替换curRoot的数据
				curRoot->data = max->data;
				//赋值完成之后继续递归，然后释放掉max对应的节点，不能直接在这里释放，因为要调整树的高度
				curRoot->LChild = deleteNode(curRoot->LChild, max->data);
			}
			else
			{ //左子树的高度小于等于右子树的高度
				//找到右子树的最小节点
				Node *min = minNode(curRoot->RChild);
				curRoot->data = min->data;
				curRoot->RChild = deleteNode(curRoot->RChild, min->data);
			}
		}
		else //上一种情况的否定，即curRoot没有子树或者只有一边
		{
			//释放内存
			Node *temp = curRoot;
			// curRoot拿到存在的子树
			curRoot = curRoot->LChild ? curRoot->LChild : curRoot->RChild;
			free(temp);
		}
	}

	return curRoot; //删除完成之后就返回当前节点
}

int main()
{
	AVLTree *tree = NULL;
	for (int i = 1; i < 10; i++)
		tree = insertNode(tree, i);
	show_pre(tree); //前序打印树
	printf("----------------------------\n");
	//删除6这个节点
	tree = deleteNode(tree, 6);
	show_pre(tree);
	printf("程序结束\n");
	return 0;
}