AVL Tree平衡二叉樹

2019-11-14 09:20:18

字體：大中小

來源：轉載

供稿：網友

#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;}

上一篇：宏

下一篇：STM32F4移植ucos_II