avltree.cpp

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

	else                                                    // 原树为非空
	{   
		if( tempData < (*tree)->data )                      // 插入值小于树的节点值，插入其左子树中
	    {   
			heightCount++;
			AVLTreeInsert(&(*tree)->lChild , tempData , ifHeight , heightCount);
			(*tree)->lChild->parent = *tree;
	      
			if( 1 == *ifHeight )                            // 在原树的左子树中插入了新节点，此时需要调整各节点的平衡度
			{ 	
				switch( (*tree)->balanceNO )                // 根据节点原平衡度来重新调整平衡度
				{   
				    case -1:                               // 原树的左子树高度小于右子树高度，此时在左子树中插入新节点不会改变整棵树的高度
						   (*tree)->balanceNO = 0;
                           *ifHeight = 0;
						   break;
					case 0 :
						   (*tree)->balanceNO = 1;
						   break;
					case 1 :                                // 原树的左右子树高度相同，新节点的插入使整棵树的高度增加了1，所以此时*IfHeight的值为1
						   AVLTree_LChange(tree);
						   *ifHeight = 0;
						   break;
					default:
						   cout<<"插入函数中调整平衡度出错!"<<endl;
						   break;
				}
			}
	    }
		else if( tempData > (*tree)->data )                // 插入值大于原树节点值，插入其右子树中。以下的注释与插入左子树时情况类似，可参考上面插入左子树的情形
		{   
			heightCount++;
			AVLTreeInsert(&(*tree)->rChild , tempData , ifHeight , heightCount);
			(*tree)->rChild->parent = *tree;
	         
			if( 1 == *ifHeight )
			{   
				switch((*tree)->balanceNO)
		        {  
					case -1:
						   AVLTree_RChange(tree);
                           *ifHeight = 0;
						   break;
					case 0 :
						   (*tree)->balanceNO = -1;
						   break;
					case 1 :
						   (*tree)->balanceNO = 0;
						   *ifHeight = 0;
						   break;
				    default:
						   cout<<"error!"<<endl;
						   break;
				}
			}
	    }
		else
		{
			*ifHeight = 0;                                 // 原树的高度没有增加，此时原树的平衡性也没有打乱，无需做任何调整
			cout << "该值已经存在！" << endl;
		}
    }
}

void avlTree::AVLTreeCreate(avlTreeNode** tree)
{   
	int data;
    int *height = new int;

	cout<<"开始创建平衡二叉树。请输入数据，以数字0作为结束标志："<<endl;
    do
	{   
		cin>>data;
	    while( ( data < -2147483647 ) || ( data > 2147483647 ) )  // ！！！！！！如何限制输入的是数字呢 ？
		{
			cout << "输入类型错误或者数据溢出错误！请重新输入正确的数字：" << endl;
		    cin >> data;
		}
	    *height = 0;
		if( 0 != data)
		    AVLTreeInsert( tree , data , height , 1 );
	}while( 0 != data );
	cout<<"输入结束！平衡二叉树已经创立！"<<endl;
}

void avlTree::AVLTreeOrder(avlTreeNode **tree)
{
	stackNode* stackTopPoint = new stackNode;
	stackNode* stackTempPoint;
	avlTreeNode* avlTreeNodeTempPoint = new avlTreeNode;
	int countStackSize = 0;
	int countOutPutSize = 0;

	avlTreeNodeTempPoint = *tree;
	stackTopPoint->data = NULL;
	stackTopPoint->next = NULL;
	if( !avlTreeNodeTempPoint )
	{
		cout << "二叉平衡树为空！" << endl;
	}
	else
	{   
		cout << "二叉平衡树从小到大排列节点值为：" << endl;
		while( 0 <= countStackSize )
	    {   
			while( avlTreeNodeTempPoint )
			{
				stackTempPoint = new stackNode;
				stackTempPoint->data = avlTreeNodeTempPoint;
        	    stackTempPoint->next = stackTopPoint;
			    stackTopPoint = stackTempPoint;
				countStackSize++;
				avlTreeNodeTempPoint = avlTreeNodeTempPoint->lChild;
			}
			if( stackTopPoint && stackTopPoint->data )
                do
			    {
				    avlTreeNodeTempPoint = stackTopPoint->data;
				    stackTopPoint = stackTopPoint->next;
					countStackSize--;
					if( avlTreeNodeTempPoint && avlTreeNodeTempPoint->data )
					{
						cout << avlTreeNodeTempPoint->data << "  ";
						countOutPutSize++;
					}
					if( 0 == (countOutPutSize%5) )
						cout << endl << endl;
			    }while( (0 <= countStackSize) && !(avlTreeNodeTempPoint && avlTreeNodeTempPoint->rChild) );
            if( avlTreeNodeTempPoint && avlTreeNodeTempPoint->rChild )
			{
				avlTreeNodeTempPoint = avlTreeNodeTempPoint->rChild;
			}
	    }
	}
}

//avlTreeNode* avlTree::AVLTree_ResearchNode(avlTreeNode **tree , int researchValue)
//{
//	avlTreeNode* avlTreeNodeTempPoint;
//    avlTreeNodeTempPoint = *tree;
//    while( avlTreeNodeTempPoint )
//	{
//		if( researchValue < avlTreeNodeTempPoint->data )
//			avlTreeNodeTempPoint = avlTreeNodeTempPoint->lChild;
//		if( researchValue > avlTreeNodeTempPoint->data )
//			avlTreeNodeTempPoint = avlTreeNodeTempPoint->rChild;
//		if( researchValue == avlTreeNodeTempPoint->data )
//			return avlTreeNodeTempPoint;
//	}
//	return NULL;
//}

//void avlTree::AVLTree_ParentBalanceChange( avlTreeNode* avlTreeNodeTempPoint )
//{
//	if( !avlTreeNodeTempPoint )
//		return;
//	while( avlTreeNodeTempPoint->parent )
//	{
//		avlTreeNodeTempPoint->parent->balanceNO--;
//		avlTreeNodeTempPoint = avlTreeNodeTempPoint->parent;
//	}
//}

void avlTree::AVLTree_Swap( avlTreeNode* tempPoint1 , avlTreeNode* tempPoint2 )
{
	int temp;
	temp = tempPoint1->data;
	tempPoint1->data = tempPoint2->data;
	tempPoint2->data = temp;
}

void avlTree::AVLTree_BalanceSwitch( avlTreeNode** tree ,int* unbalance )
{       
	switch( (*tree)->balanceNO )
	{        
	    case -1 :
		  	    (*tree)->balanceNO = 0;
		        break;
		case 0 :
	  	       (*tree)->balanceNO = 1;
		       *unbalance = 0;
		       break;
		case 1 :
		       AVLTree_LChange( tree );
		       *unbalance = 0;
		       break;
		default:
			   cout << "右删除时调整平衡度出错！" << endl;
			   break;
	 }
}

void avlTree::AVLTreeDelete(avlTreeNode** tree , int deleteValue , int* unbalance )
{
	avlTreeNode* tempPoint1;
	if( deleteValue == (*tree)->data )
	{
		*unbalance = 1;
		if( !((*tree)->lChild) && !((*tree)->rChild) )
		{
			(*tree) = NULL;
		}
		else if( ((*tree)->lChild) && !((*tree)->rChild) )
		{
			(*tree)->lChild->parent = (*tree)->parent;
			(*tree) = (*tree)->lChild;
			AVLTree_HeightChange( *tree , -1 );
		}
		else if( !((*tree)->lChild) && ((*tree)->rChild) )
		{
			(*tree)->rChild->parent = (*tree)->parent;
			(*tree) = (*tree)->rChild;
			AVLTree_HeightChange( *tree , -1 );
		}
		else if( ((*tree)->lChild) && ((*tree)->rChild) )
		{
			tempPoint1 = (*tree)->rChild;
			while( tempPoint1->lChild )
				tempPoint1 = tempPoint1->lChild;
			AVLTree_Swap( *tree , tempPoint1 );
			AVLTreeDelete( &((*tree)->rChild) , deleteValue , unbalance );
			AVLTree_BalanceSwitch( tree , unbalance );
		}
	}
	else if( deleteValue < (*tree)->data )
	{
		if( !((*tree)->lChild) )
		{
			cout << "左删除错误！该值在平衡二叉树中不存在" << endl;
			return;
		}
		AVLTreeDelete( &((*tree)->lChild) , deleteValue , unbalance );
		if( 1 == *unbalance )
		{
			switch( (*tree)->balanceNO )
			{   
		    	case -1 :
					    AVLTree_RChange( tree );
                        *unbalance = 0;
						break;
				case 0 :
					   (*tree)->balanceNO = -1;
					   *unbalance = 0;
					   break;
				case 1 :
					   (*tree)->balanceNO = 0;
					   break;
				default:
					   cout << "左删除时调整平衡度出错！" << endl;
					   break;
			}
		}
	}
	else if( deleteValue > (*tree)->data )
	{
		if( !((*tree)->rChild) )
		{
            cout << "右删除错误！该值在平衡二叉树中不存在！" << endl;
			return;
		}
		AVLTreeDelete( &((*tree)->rChild) , deleteValue , unbalance );
		if( 1 == *unbalance )
		{
			AVLTree_BalanceSwitch( tree , unbalance );
		}
	}
}