testavltree.cpp

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

#include "avlTree.h"

#include <iostream>
using namespace std;

void AVLTreePrint(avlTreeNode** tree)
{    
	int printChoice;

	queueNode* queueNodeTempPoint = new queueNode;
    queue* qu;
	
	avlTreeNode* tempPoint = new avlTreeNode;
	qu = ( queue* )malloc( sizeof(queue) );
	qu->front = qu->tail = NULL;

	queueNodeTempPoint->next = 0;
	queueNodeTempPoint->data = *tree;
	qu->front = qu->tail = queueNodeTempPoint;                          // 树的跟节点进队列

	tempPoint = qu->front->data;
    
	do
	{     
		cout << "请选择打印类型：" << endl;
    	cout << "1.简单打印：只显示节点数据" << endl;
	    cout << "2.详细打印：显示节点及其属性信息" << endl;
	    cin >> printChoice;
		if( ( 1 != printChoice )&&( 2 != printChoice ) )
			cout << "输入错误！请重新输入正确的序号1或2：" << endl;
	}while( ( 1 != printChoice ) && ( 2 != printChoice ) );

	cout << "二叉平衡树数据为：" << endl;

	while( tempPoint )                                  // 当对头不为空时，继续输出对头数据
	{   
		switch( printChoice )
		{   
		    case 1 :
				   cout << tempPoint->data << "	 ";
				   break;

			case 2 :
				   cout << tempPoint->data 
			            << " { balanceNO:" << tempPoint->balanceNO
			            << " height:" << tempPoint->height
			            << " parent:";

		           if( tempPoint->parent )
			           cout << tempPoint->parent->data;
		           else
			           cout << "NULL";

		           if( tempPoint->lChild )
			           cout << " lChild:" << tempPoint->lChild->data;
		           else
			           cout << " lChild:NULL";

		           if( tempPoint->rChild )
			           cout << " rChild:" << tempPoint->rChild->data << " } ";
		           else
			           cout << " rChild:NULL } ";
                   
				   cout << endl;  
				   break;

			default :
				    cout << "打印出错！" << endl;
                    break;
		}
		
		if( NULL != tempPoint->lChild )
		{   
            queueNodeTempPoint = ( queueNode * )malloc( sizeof(queueNode) );
			queueNodeTempPoint->data = tempPoint->lChild;
			queueNodeTempPoint->next = NULL;
			qu->tail->next = queueNodeTempPoint;
			qu->tail = qu->tail->next;                              //  相当于尾插法
		}
		if( NULL != tempPoint->rChild )
		{   
		    queueNodeTempPoint = ( queueNode * )malloc( sizeof(queueNode) );
			queueNodeTempPoint->data = tempPoint->rChild;
			queueNodeTempPoint->next = NULL;
			qu->tail->next = queueNodeTempPoint;
			qu->tail = qu->tail->next;     
		}
		if( ( 1 == printChoice )&&( qu->front->next )&&( tempPoint->height != qu->front->next->data->height) ) // 当本节点的高度与下一个节点的高度不同时，说明不在同一层，故打印回车换行符
		{    
			cout<<endl;
		}
		qu->front = qu->front->next;
		if(  (qu->front) && (qu->front->data) )
            tempPoint = qu->front->data;                      // 继续打印队列中的下一个节点
	    else
		    tempPoint = 0;		
	} 
	delete queueNodeTempPoint;
	delete tempPoint;
}

int main()
{   
	avlTree* avlTreeObject = new avlTree();

	avlTreeNode** tree = new avlTreeNode*;
    int choiceNum;
        
    int* ifHeight = new int;
	*ifHeight = 0;

	*tree = NULL;
	while( true )
	{   
		cout << endl;
		cout << "请输入相应的序号以进行相应的操作！" << endl << "       操作菜单：" << endl;
        cout << "1.创建平衡二叉树" << endl;
	    cout << "2.遍历平衡二叉树" << endl;
	    cout << "3.往平衡二叉树中插入一个值" << endl;
	    cout << "4.数据按从小到大遍历" << endl;
		cout << "5.删除平衡二叉树中的某个节点" << endl;
	    cout << "6.退出" << endl;
        cin >> choiceNum;
        while( choiceNum < 1 || choiceNum > 6 )
	    {
			cout<<"输入错误！请输入正确的序号："<<endl ;
	        cin>>choiceNum ;
    	}
	    switch(choiceNum)
	    {   
		    case 1 :
				   if(*tree)
					   cout << "二叉平衡树已经存在!" << endl;
				   else
				       avlTreeObject->AVLTreeCreate(tree);
				   break;
		    case 2 :
				   if(*tree)
				       AVLTreePrint(tree);
				   else
					   cout << "二叉平衡树为空！" << endl;
				   break;
		    case 3 :
				   int data;
				   cout<<"请输入要插入的数值："<<endl;
				   cin>>data ;
				   while( ( data < -2147483647 ) || ( data > 2147483647 ) )   // 大数如何处理？无效！ 
		           {
			           cout << "输入类型错误或者数据溢出错误！请重新输入正确的数字：" << endl;
		               cin >> data;
		           }

				   avlTreeObject->AVLTreeInsert( tree , data , ifHeight , 1 );
				   break;
		    case 4 :
				   avlTreeObject->AVLTreeOrder( tree );
				   break;
			case 5 :
				   int deleteValue;
				   cout << "请输入要删除的节点值，并确定该值在平衡二叉树中：" << endl;
				   cin >> deleteValue;
				   avlTreeObject->AVLTreeDelete( tree  , deleteValue , ifHeight );
				   break;
		    case 6 :
				   char exitConfirm;

				   cout << "确定要结束吗？" << endl
						<< "输入y退出，否则继续：" << endl;
				   cin >> exitConfirm;
				   if( 'y' == exitConfirm )
				       exit( 1 );
				   else
					   break;
		    default :
			        cout<<"出错！请输入正确的选择序号："<<endl;
			    	break;
	   	}
	}
	delete avlTreeObject;
	delete tree;
	delete ifHeight;
    return 0;
}