avltree.cpp

一个用C++实现的平衡二叉树算法

#include "avlTree.h"

#include <iostream>
using namespace std;

avlTree::avlTree(void)
{
}

avlTree::~avlTree(void)
{
}

//调整节点高度，1表示改子树所有节点高度加1，-1表示改子树所有节点高度减1
void avlTree::AVLTree_HeightChange( avlTreeNode* nodeTempPoint , int operationChoice )
{
	queueNode* queueNodeTempPoint = new queueNode;
	avlTreeNode* tempPoint = new avlTreeNode;
    queue* qu;
	qu = new queue;

	queueNodeTempPoint->data = nodeTempPoint;
	queueNodeTempPoint->next = NULL;
	qu->tail = qu->front = queueNodeTempPoint;
	tempPoint = qu->front->data;
	while( tempPoint )
	{
		switch( operationChoice )
		{   
		    case -1 :
				   tempPoint->height--;
				   break;
			case 1 :
				   tempPoint->height++; 
				   break;
			default:
				   cout <<  "调整高度时传递参数错误！" << endl;
				   break;
		}

		if( tempPoint->lChild )
		{
			queueNodeTempPoint = new queueNode;
			queueNodeTempPoint->data = tempPoint->lChild;
			queueNodeTempPoint->next = NULL;

			qu->tail->next = queueNodeTempPoint;
			qu->tail = queueNodeTempPoint;
		}
		if( tempPoint->rChild )
		{
			queueNodeTempPoint = new queueNode;
			queueNodeTempPoint->data = tempPoint->rChild;
			queueNodeTempPoint->next = NULL;

			qu->tail->next = queueNodeTempPoint;
			qu->tail = queueNodeTempPoint;
		}
		qu->front = qu->front->next;
		if(  (qu->front) && (qu->front->data) )
			tempPoint = qu->front->data;                      // 继续打印队列中的下一个节点
        else
	        tempPoint = 0;
	}
}

void avlTree::AVLTree_BalanceChange( avlTreeNode** tree , avlTreeNode* tempPoint1 , avlTreeNode* tempPoint2 , char directionChoice )
{
    switch( directionChoice )
	{
	    case 'L' :
				 if(tempPoint1)
				 {
	                 if( 1 == tempPoint2->balanceNO )          // 调整平衡度，此时假设新节点插在了C节点的左子树上
	                 {      
				         tempPoint1->balanceNO = 0;  
	                     (*tree)->balanceNO = -1;
	                 }
	                 else if( -1 == tempPoint2->balanceNO )    // 此时处理新节点插在了C节点的右子树上时的情况
	                 {    
		                 tempPoint1->balanceNO = 1;
	                     (*tree)->balanceNO = 0;
	                 }
                     else
	                 {
		                 tempPoint1->balanceNO = 0;
	                     (*tree)->balanceNO = 0;
	                 }
				 }
				 break;
		case 'R':
				if(tempPoint1)
				{
	                if( 1 == tempPoint2->balanceNO )          // 调整平衡度，此时假设新节点插在了C节点的左子树上
		            {      
		        	    tempPoint1->balanceNO = -1;  
		                (*tree)->balanceNO = 0;
		            }
		            else if( -1 == tempPoint2->balanceNO )    // 此时处理新节点插在了C节点的右子树上时的情况
		            {   
			            tempPoint1->balanceNO = 0;
		                (*tree)->balanceNO = 1;
		            }
		            else
		            {   
			            tempPoint1->balanceNO = 0;
		                (*tree)->balanceNO = 0;
		            }
				}
				break;
		default:
			   cout << "方向参数传递错误！" << endl;
               break;
	} 
	//delete tempPoint1;
	//delete tempPoint2;
}

void avlTree::AVLTree_LChange( avlTreeNode** tree )
{
	avlTreeNode* tempPoint1 = new avlTreeNode;
	avlTreeNode* tempPoint2 = new avlTreeNode;
	avlTreeNode* tempPoint3 = new avlTreeNode;

	tempPoint3 = (*tree)->parent;     // 用临时变量暂存节点的父节点
	tempPoint1 = (*tree)->lChild;     // 用临时变量暂存节点的左子树，以待处理
		
	if( 1 == tempPoint1->balanceNO )  // 插入了新节点的子树的平衡度为1，进行LL旋转
	{   
		(*tree)->lChild = tempPoint1->rChild;
		if(tempPoint1->rChild)
			tempPoint1->rChild->parent = (*tree);
	    tempPoint1->rChild = *tree;
		(*tree)->parent = tempPoint1;
		(*tree)->balanceNO = 0;

		(*tree) = tempPoint1;
		(*tree)->parent = tempPoint3;

		(*tree)->height--;                        //改程序段用于调整二叉树的高度，
		if( (*tree)->rChild )                     //参数1表示该子树所有节点高度加1，-1表示高度减1 
		    (*tree)->rChild->height++;            
		if( (*tree)->lChild )
	       	AVLTree_HeightChange( (*tree)->lChild , -1 ); 
		if( (*tree)->rChild->rChild )
		    AVLTree_HeightChange( (*tree)->rChild->rChild , 1 );
	}
	else if( -1 == tempPoint1->balanceNO )        // 插入了新节点的子树的平衡度为-1，进行LR旋转。假设离新节点最近的父节点为C节点
	{   
		tempPoint2 = tempPoint1->rChild;          // 使临时变量2指向C节点。此时，临时变量1指向了C节点的父节点B，而*tee指向了节点B的父节点A
	    (*tree)->lChild = tempPoint2->rChild;     // C节点的右子树成为了A节点的左子树
		tempPoint1->rChild = tempPoint2->lChild;  // C节点的左子树成为了B节点的右子树
		if(tempPoint2->lChild)
		    tempPoint2->lChild->parent = tempPoint1;
		tempPoint2->lChild = tempPoint1;          // B节点成为了C节点的左子树
		if(tempPoint2->rChild)
			tempPoint2->rChild->parent = *tree;
		tempPoint1->parent = tempPoint2;
		tempPoint2->rChild = *tree;               // A节点成为了C节点的右子树
		(*tree)->parent = tempPoint2;
		tempPoint2->rChild->parent = tempPoint2;

		AVLTree_BalanceChange( tree , tempPoint1 , tempPoint2 , 'L' );
	
        (*tree) = tempPoint2;
		(*tree)->parent = tempPoint3;

		(*tree)->height =(*tree)->height - 2;     // 调整子树节点高度
		(*tree)->rChild->height++;
		if( ((*tree)->lChild)&&(*tree)->lChild->rChild )
		    AVLTree_HeightChange( (*tree)->lChild->rChild , -1 );
		if( ((*tree)->rChild)&&(*tree)->rChild->lChild )
		    AVLTree_HeightChange( (*tree)->rChild->lChild , -1 );
		if( ((*tree)->rChild)&&(*tree)->rChild->rChild )
		    AVLTree_HeightChange( (*tree)->rChild->rChild , 1 );
	}
	else 
	{   
		cout<<"左旋转时出错！二叉树已经平衡，无需调整！"<<endl;
	}
	(*tree)->balanceNO = 0;            // 把父节点的平衡度设为0，此时，以*tree为父节点的子树达到平衡，从而整棵树也达到了平衡
} 

void avlTree::AVLTree_RChange(avlTreeNode** tree)
{
	avlTreeNode* tempPoint1 = new avlTreeNode;
	avlTreeNode* tempPoint2 = new avlTreeNode;
	avlTreeNode* tempPoint3 = new avlTreeNode;

	tempPoint3 = (*tree)->parent;
	tempPoint1 = (*tree)->rChild;      // 用临时变量暂存节点的又子树，以待处理

	if( -1 == tempPoint1->balanceNO )  // 插入了新节点的子树的平衡度为-1，进行RR旋转
	{   
		(*tree)->rChild = tempPoint1->lChild; 
		if(tempPoint1->lChild)
		    tempPoint1->lChild->parent = (*tree);
	    tempPoint1->lChild = *tree;
		(*tree)->parent = tempPoint1;
		(*tree)->balanceNO = 0;

		(*tree) = tempPoint1;
		(*tree)->parent = tempPoint3;

		(*tree)->height--;            // 调整子树高度
		if( (*tree)->lChild )
		    (*tree)->lChild->height++;
		if((*tree)->rChild)
		    AVLTree_HeightChange( (*tree)->rChild , -1 );
		if(((*tree)->lChild)&&(*tree)->lChild->lChild)
		    AVLTree_HeightChange( (*tree)->lChild->lChild , 1 );
	}
	else if( 1 == tempPoint1->balanceNO )         // 插入了新节点的子树的平衡度为1，进行RL旋转。假设离新节点最近的父节点为C节点
	{   
		tempPoint2 = tempPoint1->lChild;          // 使临时变量2指向C节点。此时，临时变量1指向了C节点的父节点B，而*tee指向了节点B的父节点A
	    (*tree)->rChild = tempPoint2->lChild;     // C节点的左子树成为了A节点的右子树
		if(tempPoint2->lChild)
		    tempPoint2->lChild->parent = (*tree);
		tempPoint1->lChild = tempPoint2->rChild;  // C节点的右子树成为了B节点的左子树
		if(tempPoint2->rChild)
		    tempPoint2->rChild->parent = tempPoint1;
		tempPoint2->rChild = tempPoint1;          // B节点成为了C节点的右子树
		tempPoint1->parent = tempPoint2;
		tempPoint2->lChild = *tree;               // A节点成为了C节点的左子树
		(*tree)->parent = tempPoint2;
		
        AVLTree_BalanceChange( tree , tempPoint1 , tempPoint2 , 'R' ); 
		
		 *tree = tempPoint2;
		 (*tree)->parent = tempPoint3;

		(*tree)->height =(*tree)->height - 2;    // 调整子树高度
		if( (*tree)->lChild )
		    (*tree)->lChild->height++;
		if(((*tree)->lChild)&&(*tree)->lChild->lChild)
		    AVLTree_HeightChange( (*tree)->lChild->lChild , 1 );
		if( ((*tree)->lChild)&&(*tree)->lChild->rChild )
		    AVLTree_HeightChange( (*tree)->lChild->rChild , -1 );
		if(((*tree)->rChild)&&(*tree)->rChild->lChild)
		    AVLTree_HeightChange( (*tree)->rChild->lChild , -1 );
	}
	else 
	{   
		cout<<"右旋转时出错！二叉树已经平衡，无需调整！"<<endl;
	}
	(*tree)->balanceNO = 0;                      // 把父节点的平衡度设为0，此时，以*tree为父节点的子树达到平衡，从而整棵树也达到了平衡
}

/**算法简述：
插入某节点后，有可能会影响二叉树的平衡性，
可以利用二叉树原来的平衡度对其进行判断，
并同时相应的调整该节点的平衡度**/
void avlTree::AVLTreeInsert(avlTreeNode** tree , int tempData , int *ifHeight , int heightCount)
{
	avlTreeNode* avlTreeNodeTempPoint;
	avlTreeNodeTempPoint = new avlTreeNode;

	if( NULL == *tree )                                     //  原树为空树，待插入点将成为树根
	{   
		*tree = (avlTreeNode*)malloc(sizeof(avlTreeNode));  // 生成根节点
        (*tree)->data = tempData;
		(*tree)->balanceNO = 0;
		(*tree)->height = heightCount;
		(*tree)->lChild = NULL;
		(*tree)->rChild = NULL;
		(*tree)->parent = NULL;

		*ifHeight = 1;                                      // 树的高度增加了。若该节点插入到了原非空树的某子树叶子节点中，则整棵树的高度是否改变还有待确定
	}