平衡二叉树的c语言实现

平衡二叉树

首先该树挺简单的。

大概解释个意思：这种树的最基本的操作是LL和RR两个单旋转函数，这两个函数和链表的插入函数挺相像的。这两个函数要牢记。

其次是LR和RL两个双旋转函数，要在心里绘制出这两种树的形状，这样调用LL还是RR很明了了。

1，在进行增删节点时，和二叉查找树算法一致，不过是多了一步判断左右子树高度并对不符合规格限制的树单旋转抑或是双旋转，并更新高度（这一步很关键）。

2，在LL函数和RR函数的最后要附带更新高度的操作。

3，删除节点和搜索树一致，不过是查找树可以找左树最大抑或是右树最小删除，但是平衡树必须在更高大的子树删去（为了更易平衡，否则删一下就要换一下根节点orz）。增加的节点一定是叶子节点，这个和搜索树一样。

以下代码：

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
typedef struct BiNode
{
	int data;
	int height;
	struct BiNode *lchild;
	struct BiNode *rchild;
}BiNode,*BiTree;
int FindMax(BiTree root)
{
	if(root==NULL)
	{

		return 0;
	}
	else
	{
		BiTree temp;
		temp=root;
		while(temp->rchild!=NULL)
		{
			temp=temp->rchild;
		}
		return temp->data;
	}
}
int FindMin(BiTree root)
{
	if(root==NULL)
	{

		return 0;
	}
	else
	{
		BiTree temp;
		temp=root;
		while(temp->lchild!=NULL)
		{
			temp=temp->lchild;
		}
		return temp->data;
	}
}
int GetHeight(BiTree root)
{
	if(root==NULL)
	{

		return 0;
	}
	else
	{
		return root->height;
	}
}
BiTree LL(BiTree &root)
{
	BiTree temp=root->lchild;
	root->lchild=temp->rchild;
	temp->rchild=root;
	root->height=max(GetHeight(root->lchild),GetHeight(root->rchild))+1;
	temp->height=max(GetHeight(temp->lchild),GetHeight(temp->rchild))+1;
	return temp;
}
BiTree RR(BiTree &root)
{
	BiTree temp=root->rchild;
	root->rchild=temp->lchild;
	temp->lchild=root;
	root->height=max(GetHeight(root->lchild),GetHeight(root->rchild))+1;
	temp->height=max(GetHeight(temp->lchild),GetHeight(temp->rchild))+1;
	return temp;
}
BiTree LR(BiTree &root)
{
	root->lchild=RR(root->lchild);
	return LL(root);
}
BiTree RL(BiTree &root)
{
	root->rchild=LL(root->rchild);
	return RR(root);
}
void Insert(BiTree &root,int x)
{
	if(root==NULL)
	{
		BiTree temp=(BiTree)malloc(sizeof(BiNode));
		temp->data=x;
		temp->lchild=temp->rchild=NULL;
		temp->height=0;
		root=temp;
	}
	else if(root->data<x)
	{
		Insert(root->rchild,x);
		if(GetHeight(root->rchild)-GetHeight(root->lchild)>1)
		{
			if(GetHeight(root->rchild->rchild)-GetHeight(root->rchild->lchild)>1)
			{
				root=RR(root);
			}
			else
			{
				root=RL(root);
			}
		}
		else
		{
			root->height=max(GetHeight(root->lchild),GetHeight(root->rchild))+1;
		}
	}
	else if(root->data>x)
	{
		Insert(root->lchild,x);
		if(GetHeight(root->lchild)-GetHeight(root->rchild)>1)
		{
			if(GetHeight(root->lchild->lchild)-GetHeight(root->lchild->rchild)>1)
			{
				root=LL(root);
			}
			else
			{
				root=LR(root);
			}
		}
		else
		{
			root->height=max(GetHeight(root->lchild),GetHeight(root->rchild))+1;
		}
	}
}
bool Delete(BiTree &root,int x)
{
	if(root==NULL)
	{
		return false;
	}
	else if(root->data==x)
	{
		if(root->lchild!=NULL&&root->rchild!=NULL)
		{
			if(GetHeight(root->lchild)>GetHeight(root->rchild))
			{
				root->data=FindMin(root->rchild);
				Delete(root->rchild,root->data);
			}
			else
			{
				root->data=FindMax(root->lchild);
				Delete(root->lchild,root->data);
			}
		}
		else if(root->lchild!=NULL||root->rchild!=NULL)
		{
			BiTree temp=(BiTree)malloc(sizeof(BiNode));
			root=root->lchild?root->lchild:root->rchild;
			delete(temp);
		}
		else
		{
			delete(root);
		}
	}
	else if(root->data>x)
	{
		Delete(root->lchild,x);
		if(GetHeight(root->rchild)-GetHeight(root->lchild)>1)
		{
			if(GetHeight(root->rchild->rchild)-GetHeight(root->rchild->lchild)>1)
			{
				root=RR(root);
			}
			else
			{
				root=RL(root);
			}
		}
		else
		{
			root->height=max(GetHeight(root->lchild),GetHeight(root->rchild))+1;
		}
	}
	else if(root->data<x)
	{
		Delete(root->rchild,x);
		if(GetHeight(root->lchild)-GetHeight(root->rchild)>1)
		{
			if(GetHeight(root->lchild->lchild)-GetHeight(root->lchild->rchild)>1)
			{
				root=LL(root);
			}
			else
			{
				root=LR(root);
			}
		}
		else
		{
			root->height=max(GetHeight(root->lchild),GetHeight(root->rchild))+1;
		}
	}
	return true;
}

溜了，打dota去了。