#include "iostream.h"	template <class Type> class AVLTree 	{					//平衡的二叉搜索樹（AVL）類定義	public:	   struct AVLNode {							//AVL樹結(jié)點的類定義  		 Type data;  AVLNode *left, *right;  int balance;		 AVLNode ( ) : left (NULL), right (NULL), balance (0) { }		 AVLNode ( Type d, AVLNode *l=NULL, AVLNode *r=NULL ) :	           data (d), left (l), right (r), balance (0) { }	   };		protected:	   Type RefValue;										//插入結(jié)束的標(biāo)志	   AVLNode *root;										//根結(jié)點的指針	   int Insert ( AVLNode* &tree, Type x, int & taller );				//插入	   void RotateLeft ( AVLNode *Tree, AVLNode* &NewTree );			//左單旋轉(zhuǎn)	   void RotateRight ( AVLNode *Tree, AVLNode* &NewTree );			//右單旋轉(zhuǎn)	   void LeftBalance ( AVLNode* &Tree, int & taller );				//左平衡化	   void RightBalance ( AVLNode* &Tree, int & taller );				//右平衡化	   int Depth ( AVLNode *t ) const;							//求高度	   void Traverse ( AVLNode *ptr, ostream & out )const ;	public:	   AVLTree ( ) : root (NULL) { }								//構(gòu)造函數(shù)：構(gòu)造一棵空AVL樹	   AVLTree ( Type Ref ) : RefValue (Ref), root (NULL) { }				//構(gòu)造函數(shù)：構(gòu)造非空AVL樹	   int Insert ( Type x ) { int taller; return Insert ( root, x, taller ); }	   friend istream& operator >> ( istream& in, AVLTree<Type>& Tree );	   friend ostream& operator << ( ostream& out, const AVLTree<Type>& Tree );	   int Depth ( ) const;	};		template <class Type> void AVLTree<Type>::RotateLeft ( AVLNode * Tree, AVLNode* &NewTree )		{		//右子樹比左子樹高: 對以Tree為根的AVL樹做左單旋轉(zhuǎn)(左折), 旋轉(zhuǎn)后新根在NewTree。		   NewTree = Tree->right;					//新的根為C		   Tree->right = NewTree->left;				//結(jié)點C的左子女轉(zhuǎn)為結(jié)點A的右子女		   NewTree->left = Tree;					//結(jié)點A成為C的左子女		};		template <class Type> void AVLTree<Type>::RotateRight ( AVLNode *Tree, AVLNode* &NewTree )		{		//左子樹比右子樹高: 對以Tree為根的AVL樹做右單旋轉(zhuǎn)(右折), 旋轉(zhuǎn)后新根在NewTree。		   NewTree = Tree->left;					//新的根在B		   Tree->left = NewTree->right;				//結(jié)點B的右子女轉(zhuǎn)為A的左子女		   NewTree->right = Tree;					//結(jié)點A成為B的右子女		};	 		template <class Type> void AVLTree<Type>::LeftBalance ( AVLNode * &Tree, int & taller ) {		   AVLNode *leftsub = Tree->left,  *rightsub;		   switch ( leftsub->balance ) {							//判斷左子樹的平衡因子			 case -1 :	Tree->balance = leftsub->balance = 0;		//左高，修改平衡因子					RotateRight ( Tree, Tree );	taller = 0;  break;	//做右單旋轉(zhuǎn)			 case 0 :	cout << "LeftBalance error: Tree already balanded.\n";  				        break;	//沒有發(fā)生不平衡			 case 1 :	rightsub = leftsub->right;					//右高, 取左子樹的右子樹					switch ( rightsub->balance ) {				//判斷該右子樹的平衡因子					   case -1: Tree->balance = 1;  								leftsub->balance = 0;  break;					   case 0 : Tree->balance = leftsub->balance = 0;  								break;					   case 1 : Tree->balance = 0;  						        leftsub->balance = -1;  								break;					}								//調(diào)整旋轉(zhuǎn)后各結(jié)點的平衡因子					rightsub->balance = 0;						RotateLeft ( leftsub, Tree->left );				//左單旋轉(zhuǎn)					RotateRight ( Tree, Tree );	taller = 0;			//右單旋轉(zhuǎn)				}	}		template <class Type> void AVLTree<Type>::RightBalance ( AVLNode * &Tree, int & taller ) {		   AVLNode *rightsub = Tree->right,  *leftsub;		   switch ( rightsub->balance ) {						//判斷右子樹的平衡因子			 case 1 :	Tree->balance = rightsub->balance = 0;		//右高					RotateLeft ( Tree, Tree );  					taller = 0;  break;		//做左單旋轉(zhuǎn)			 case 0 :	cout << "RightBalance error:Tree already balanded.\n";  				        break;			 case -1 :	leftsub = rightsub->left;					//左高, 取右子樹的左子樹					switch ( leftsub->balance ) {				//判斷該左子樹的平衡因子					   case 1 : Tree->balance = -1; 						        rightsub->balance = 0;  								break;					   case 0 : Tree->balance = rightsub->balance = 0;  						        break;					   case -1 : Tree->balance = 0;  						         rightsub->balance = 1;  								 break;					}					leftsub->balance = 0;					RotateRight ( rightsub, Tree->right );			//右單旋轉(zhuǎn)					RotateLeft ( Tree, Tree );  taller = 0;			//左單旋轉(zhuǎn)	   }	}		template <class Type> int AVLTree<Type>::Insert ( AVLNode* &tree, Type x, int &taller ) {		//在以tree為根的AVL樹中插入新元素x, 如果插入成功, taller返回1, 否則返回0。 		   int success;		   if ( tree == NULL ) {								//原為空樹, 或某結(jié)點的空鏈域			 tree = new AVLNode (x);							//創(chuàng)建新結(jié)點并插入			 success = tree != NULL ? 1 : 0;						//成功標(biāo)志: 存儲分配成功為1			 if ( success )				 taller = 1;		   }		   else if ( x < tree->data ) {							//判斷是向左插入還是向右插入			 success = Insert ( tree->left, x, taller );					//插入到左子樹			 if ( taller )									//插入成功 			   switch ( tree->balance ) {						//判斷平衡因子				 case -1 :	LeftBalance ( tree, taller );  					        break;		//原左子樹高，不平衡，調(diào)整				 case 0 :	tree->balance = -1;  					        break;			//原兩子樹等高，僅改平衡因子				 case 1 :	tree->balance = 0;  					        taller = 0;  					        break;	//原右子樹高，僅改平衡因子			   }      		   }	        else {			   success = Insert ( tree->right, x, taller );				//插入到右子樹			   if ( taller )								//插入成功				 switch ( tree->balance ) {					//判斷平衡因子				 case -1 :	tree->balance = 0;							taller = 0;  							break;	//原左子樹高， 僅改平衡因子				 case 0 :	tree->balance = 1;  							break;			//原兩子樹等高， 僅改平衡因子				 case 1 :						        RightBalance ( tree, taller );  							break;		//原右子樹高，不平衡，調(diào)整			   }				}		return success;									//向上層傳送插入成功信息		}		template <class Type> istream & operator >> ( istream & in, AVLTree<Type> & Tree ) {		//輸入一系列的值, 建立AVL樹。約定Tree中的RefValue是終止輸入的標(biāo)記。		   Type item;									//輸入暫存單元		   cout << "Construct AVL tree :\n";						//提示：構(gòu)造AVL樹		   cout << "Input Data (end with " << Tree.RefValue << "): ";		//提示：輸入數(shù)據(jù)(以RefValue結(jié)束		   in >> item;									//輸入		   while ( item != Tree.RefValue ) {						//當(dāng)輸入不等于RefValue時		      Tree.Insert (item);								//插入到樹中			 		      cout << "Input Data (end with " << Tree.RefValue << "): ";		//提示：輸入數(shù)據(jù)(以RefValue結(jié)束		      in >> item;									//輸入		   }		   return in;		}		template <class Type> ostream & operator << ( ostream & out, const AVLTree<Type> & Tree ) {		   out << "Inorder traversal of AVL tree.\n";					//提示：AVL樹的中序遍歷		   Tree.Traverse ( Tree.root, out );						//以中序次序輸出樹中各結(jié)點的數(shù)據(jù)		   out << endl;		   return out;									//返回輸出對象		}		template <class Type> void AVLTree <Type>::Traverse ( AVLNode *ptr, ostream & out ) const {		   if ( ptr != NULL ) {								//樹非空		      Traverse ( ptr->left, out );						//中序遍歷左子樹		      out << ptr->data << ' ';							//輸出根的數(shù)據(jù)		      Traverse ( ptr->right, out );						//中序遍歷右子樹			  		   }		}