AVL Tree平衡二叉树

#include <iostream>#include <cstdio>using namespace std;// AVLTree平衡二叉树(Balanced Binary Tree)/高度平衡的二叉查找树 // 插入、删除 typedef int DataType;typedef struct node{	DataType data;	int bf;				// 平衡因子 	struct node *lchild, *rchild;}AVLNode, *AVLTree;// 右单旋转(LL旋转): *a的左子树的左子树上 插入新结点 void RotateLL(AVLNode *&a){	AVLNode *b = a->lchild;	a->lchild = b->rchild;	b->rchild = a;	b->bf = a->bf = 0;	a = b;}// 左单旋转(RR旋转): *a的右子树的右子树上 插入新结点 void RotateRR(AVLNode *&a){	AVLNode *b = a->rchild;	a->rchild = b->lchild;	b->lchild = a;	b->bf = a->bf = 0;	a = b;}// 先左后右双旋转(LR旋转): *a的左子树的右子树上 插入新结点 void RotateLR(AVLNode *&a){	AVLNode *b = a->lchild, *c = b->rchild;	b->rchild = c->lchild;				// 左单旋转 	c->lchild = b;						// 左单旋转 	if(c->bf <= 0)		b->bf = 1;	else		b->bf = 0;	a->lchild = c->rchild;				// 右单旋转 	c->rchild = a;						// 右单旋转 	if(c->bf == -1)		a->bf = 0;	else		a->bf = -1;	c->bf = 0;	a = c;}// 先右后左双旋转(RL旋转): *a的右子树的左子树上 插入新结点 void RotateRL(AVLNode *&a){	AVLNode *b = a->rchild, *c = b->lchild;	b->lchild = c->rchild;				// 右单旋转 	c->rchild = b;						// 右单旋转 	if(c->bf >= 0)		b->bf = -1;	else		b->bf = 0;	a->rchild = c->lchild;				// 左单旋转 	c->lchild = a;						// 左单旋转 	if(c->bf == 1)		a->bf = 0;	else		a->bf = 1;	c->bf = 0;	a = c;}// 先序递归遍历 void PReOrder(AVLTree root){	if(root != NULL)	{		printf("%4d", root->data);		PreOrder(root->lchild);		PreOrder(root->rchild);	}}void PreBF(AVLTree root)	// 先序遍历平衡因子 {	if(root != NULL)	{		printf("%4d", root->bf);		PreBF(root->lchild);		PreBF(root->rchild);	}}void InOrder(AVLTree root)	// 中序递归遍历 {	if(root != NULL)	{		PreOrder(root->lchild);		printf("%4d", root->data);		PreOrder(root->rchild);	}}// 计算树的平衡因子 int count(AVLNode *r){	if(r->lchild == NULL && r->rchild == NULL)	{		r->bf = 0;		return 1;	}	else	{		int lhigh, rhigh;		if(r->lchild != NULL)		{			lhigh = count(r->lchild);		}		else			lhigh = 0;				if(r->rchild != NULL)		{			rhigh = count(r->rchild);		}		else			rhigh = 0;				r->bf = lhigh - rhigh;		// 因子 = 左子树高度 - 右子树高度 		if(lhigh > rhigh)			return lhigh + 1;		else			return rhigh + 1;	}}// 一个结点一个结点地添加/删除，然后调整，所以平衡因子不会超过2/-2 // 在root树种，添加值为x的结点，并且调整成为平衡二叉树 AVLNode* InsertAndBalance(AVLTree &root, DataType x){	AVLNode *s, *p, *f;		if(root == NULL)	{		root = new AVLNode;		if(root == NULL)			return NULL;		root->data = x;		root->bf = 0;		root->lchild = NULL;		root->rchild = NULL;		return root;	}	else	{		if(x > root->data)		{			root->rchild = InsertAndBalance(root->rchild, x);						count(root);	// 修改结点的bf值,并返回高度(此处可以优化,需要重新递归求平衡因子) 						if(root->bf == 2)		// 如果不平衡，进行旋转 			{				if(root->lchild->bf == 1)					RotateLL(root);				else if(root->lchild->bf == -1)					RotateLR(root);				count(root);			}			else if(root->bf == -2)			{				if(root->rchild->bf == -1)					RotateRR(root);				else if(root->rchild->bf == 1)					RotateRL(root);				count(root);			}					}		else if(x < root->data)		{			root->lchild = InsertAndBalance(root->lchild, x);						count(root);	// 修改结点的bf值,并返回高度(此处可以优化,需要重新递归求平衡因子) 						if(root->bf == 2)		// 如果不平衡，进行旋转 			{				if(root->lchild->bf == 1)					RotateLL(root);				else if(root->lchild->bf == -1)					RotateLR(root);				count(root);			}			else if(root->bf == -2)			{				if(root->rchild->bf == -1)					RotateRR(root);				else if(root->rchild->bf == 1)					RotateRL(root);				count(root);			}					}			}		return root;}// 在root树种，删除结点x，并且调整成为平衡二叉树 AVLNode* RemoveAndBalance(AVLTree &root, DataType x){	AVLNode *s, *p, *f;		if(root == NULL)	{		return root;	}	else	{		if(x > root->data)		{			root->rchild = RemoveAndBalance(root->rchild, x);						count(root);	// 修改结点的bf值,并返回高度(此处可以优化,需要重新递归求平衡因子) 						if(root->bf == 2)		// 如果不平衡，进行旋转 			{				if(root->lchild->bf == 1)					RotateLL(root);				else if(root->lchild->bf == -1)					RotateLR(root);				count(root);			}			else if(root->bf == -2)			{				if(root->rchild->bf == -1)					RotateRR(root);				else if(root->rchild->bf == 1)					RotateRL(root);				count(root);			}					}		else if(x < root->data)		{			root->lchild = RemoveAndBalance(root->lchild, x);						count(root);	// 修改结点的bf值,并返回高度(此处可以优化,需要重新递归求平衡因子) 						if(root->bf == 2)		// 如果不平衡，进行旋转 			{				if(root->lchild->bf == 1)					RotateLL(root);				else if(root->lchild->bf == -1)					RotateLR(root);				count(root);			}			else if(root->bf == -2)			{				if(root->rchild->bf == -1)					RotateRR(root);				else if(root->rchild->bf == 1)					RotateRL(root);				count(root);			}					}		else if(x == root->data)		{			AVLNode *s, *f;			if(root->lchild == NULL && root->rchild == NULL)	// 叶子的时候 			{				delete root;				return NULL;			}			else if(root->lchild == NULL && root->rchild != NULL)			{				s = root->rchild;				delete root;				return s;			}			else if(root->lchild != NULL && root->rchild == NULL)			{				s = root->lchild;				delete root;				return s;			}			else if(root->lchild != NULL && root->rchild != NULL)			{				s = root->lchild;				if(s->rchild != NULL)				{					while(s->rchild != NULL)					{						f = s;						s = s->rchild;					}					f->rchild = NULL;					root->data = s->data;					if(s->lchild != NULL)					{						if(f->data > s->lchild->data)							f->lchild = s->lchild;						else							f->rchild = s->lchild;					}				}				else		// 左子树没有右结点时 				{					root->data = s->data;					root->lchild = s->lchild;				}				delete s;				return root;			}		}	}		return root;}int main(){	int high;	AVLNode *s, *f;	AVLTree root = NULL;	InsertAndBalance(root, 53);	InsertAndBalance(root, 17);	InsertAndBalance(root, 9);	InsertAndBalance(root, 45);	InsertAndBalance(root, 23);	InsertAndBalance(root, 78);	InsertAndBalance(root, 65);	InsertAndBalance(root, 66);	InsertAndBalance(root, 67);	//InsertAndBalance(root, 94);	//InsertAndBalance(root, 81);	//InsertAndBalance(root, 88);	//high = count(root);	//cout << "Tree high is " << high << endl;	cout << "数值: ";	PreOrder(root);	cout << endl;	cout << "因子: ";	PreBF(root);	cout << endl << endl;		RemoveAndBalance(root, 45);	RemoveAndBalance(root, 9);	cout << "先序遍历: ";	PreOrder(root);	cout << endl;	cout << "中序遍历: ";	InOrder(root);	cout << endl;	cout << "平衡因子: ";	PreBF(root);	cout << endl << endl;		RemoveAndBalance(root, 17);	RemoveAndBalance(root, 53);	InsertAndBalance(root, 94);	cout << "先序遍历: ";	PreOrder(root);	cout << endl;	cout << "中序遍历: ";	InOrder(root);	cout << endl;	cout << "平衡因子: ";	PreBF(root);	cout << endl << endl;			return 0;}