avltreeadt.h

本设计使用Ｃ＋＋来实现一个简单的数据结构问题

		                     bool&      shorter)
{
// Local Definitions
	NODE<TYPE>   *leftTree;
	NODE<TYPE>   *rightTree;

// Statements
	switch (root->bal)
	{
	case RH: // Deleted right--Now balanced
		     root->bal   = EH;
		     break;
	case EH: // Now Left high
		     root->bal   = LH;
		     shorter     = false;
		     break;
	case LH: // Left High - Rotate Right
		     leftTree = root->left;
		     if (leftTree->bal ==RH)
		     // Double rotation required
			 {
			  rightTree = leftTree->right;
			
			  switch (rightTree->bal)
			  {
			   case RH: leftTree->bal   = LH;
				        root->bal       = EH;
				        break;
		   	   case EH: root->bal       = EH;
			        	leftTree->bal   = EH;
				        break;
			   case LH: root->bal       = RH;
				        leftTree->bal   = EH;
				        break;
			  } // switch

			  rightTree->bal = EH;

			  // Rotate Left then Right
			  root->left = rotateLeft   (leftTree);
			  root        = rotateRight (root);
			 } // if leftTree->bal == RH
		else
		{
		 // Single Rotation Only
		 switch (leftTree->bal)
			{
			case RH:
			case LH: root->bal       = EH;
				     leftTree->bal   = EH;
				     break;
			case EH: root->bal       = LH;
				     leftTree->bal   = RH;
					 shorter         = false;
				     break;
		 } // switch leftTree->bal
		 root = rotateRight (root);
		} // else
	} // switch root bal
	return root;
} // dltLeftBalance

/* =================== dltRightBalance ================== //8   
  The tree is shorter after a delete on the left.
  Adjust the balance factors and rotate the tree
  to the left if necessary.
     Pre     the tree is shorter
   	 Post    balance factors adjusted and balance restored
	 Returns potentially new root
*/

template <class TYPE ,class KTYPE>
NODE<TYPE>* AvlTree<TYPE,KTYPE>
         :: dltRightBalance (NODE<TYPE> *root,
		                     bool&       shorter)
{
// Local Definitions
	NODE<TYPE>   *rightTree;
	NODE<TYPE>   *leftTree;

// Statements
	switch (root->bal)
	{
	case LH: // Deleted left--Now balanced
		     root->bal   = EH;
		     break;
	case EH: // Now Right high
		     root->bal   = RH;
		     shorter     = false;
		     break;
	case RH: // Right High - Rotate Left
		     rightTree = root->right;
		     if (rightTree->bal ==LH)
		     // Double rotation required
			 {
			  leftTree = rightTree->left;
			
			  switch (leftTree->bal)
			  {
			   case LH: rightTree->bal  = RH;
				        root->bal       = EH;
				        break;
		   	   case EH: root->bal       = EH;
			        	rightTree->bal  = EH;
				        break;
			   case RH: root->bal       = LH;
				        rightTree->bal  = EH;
				        break;
			  } // switch

			  leftTree->bal = EH;

			  // Rotate Right then Left
			  root->right = rotateRight (rightTree);
			  root        = rotateLeft (root);
			 } // if rightTree->bal == LH
		else
		{
		 // Single Rotation Only
		 switch (rightTree->bal)
			{
			case LH:
			case RH: root->bal       = EH;
				     rightTree->bal  = EH;
				     break;
			case EH: root->bal       = RH;
				     rightTree->bal  = LH;
					 shorter         = false;
				     break;
		 } // switch rightTree->bal
		 root = rotateLeft (root);
		} // else
	} // switch root bal
	return root;
} // dltRightBalance

/* =================== _retrieve ================== //9
   Retrieve searches tree for node containing requested
   key and returns its data to the calling function.
      Pre      AVL_Retrieve called: passes key to be located
	  Post     tree searched and data pointer returned
	  Return   address of matching node returned 
	           if not found,NULL returned
*/

template <class TYPE, class KTYPE>
NODE<TYPE>*  AvlTree<TYPE,KTYPE>
        ::  _retrieve (KTYPE       key, 
		               NODE<TYPE> *root)
{
// Statements
	if (root)
	{
		if (key < root->data.key)
			return _retrieve (key, root->left);
		else if(key > root->data.key)
			return _retrieve (key, root->right);
		else 
			// Found equal key
			return (root);
	} // if not
	else
		// Data not in tree
		return root;
} // _retrieve

/* =================== _traversal ================== //10
   Traverse tree using inorder traversal. To process a 
   node, we use the function passed when traversal is called.
      Pre     tree has been created (may be null)
	  Post    all nodes processed
*/

template <class TYPE,class KTYPE>
void  AvlTree<TYPE,KTYPE>
  ::  _traversal (void(*process)(TYPE dataProc),
                  NODE<TYPE> *root)
{
// Statements
	if (root)
	{
		_traversal (process,root->left);
		 process   (root->data);
		_traversal (process,root->right);
	} // if
	return;
} // _traversal

/* =================== _destroyAVL ================== //11
   Deletes all data in tree and recycle memory. 
   The nodes are deleted by calling a recursive 
   function to traverse the tree in postorder sequence.
      Pre    tree is being destroyed
	  Post   all data have been deleted
*/

template <class TYPE, class KTYPE>
void  AvlTree<TYPE,KTYPE>
  ::  _destroyAVL (NODE<TYPE> *root)
{
//Statements
	if (root)
	{
		_destroyAVL (root->left);
		_destroyAVL (root->right);
         delete root;
	} // if
	return;
} // _destroyAVL

/*	=================== Constructor ================== //12     	
    Initializes private data.
	   Pre     class is being defined 
	   Post    private data initialized
*/

template <class TYPE, class KTYPE>
AvlTree<TYPE,KTYPE> :: AvlTree (void)                        
{
// Statements
	tree  = NULL;
	count = 0;
}// Constructor

/* =================== Destructor ================== //13
   Deletes all data in tree and recycles memory.
   The nodes are deleted by calling a recursive 
   function to traverse the tree in inorder sequence.
      Pre    tree is a pointer to a valid tree
	  Post   all data have been deleted
*/

template <class TYPE, class KTYPE>
AvlTree<TYPE,KTYPE> :: ~AvlTree (void)
{
//Statements
	if (tree)
		_destroyAVL (tree);
} // Destructor

/*	=================== AVL_Insert ================== //14     	
    This function inserts new data into the tree.
	   Pre     dataIn countains data to be inserted 
	   Post    data have been inserted or memory overflow
       Return  success (true) or overflow (false)     
*/

template <class TYPE,class KTYPE>
bool AvlTree<TYPE,KTYPE> :: AVL_Insert (TYPE dataIn)
{
// Local Definitions
	NODE<TYPE> *newPtr;
	bool        taller;

// Statements
	if (!(newPtr = new NODE<TYPE>))
		return false;
	newPtr->bal      = EH;
    newPtr->right    = NULL;
	newPtr->left     = NULL;
	newPtr->data     = dataIn;

	tree = _insert(tree, newPtr, taller);
	count++;

	return true;
} // Avl_Insert 

/*	=================== AVL_Delete ================== //15     	
    This function deletes a node from the tree and rebalances
	it if nessary.
	   Pre     dltKey contains key to be deleted 
	   Post    the node is deleted and its space recycled
	           -or- an error code is returned 
	   Return success (true) or not found (false)
*/

template <class TYPE, class KTYPE>
bool AvlTree<TYPE, KTYPE> :: AVL_Delete (KTYPE dltKey)
{
// Local Definitions
	bool shorter;
	bool success;

	NODE<TYPE> *newRoot;

// Statements
	newRoot = _delete (tree, dltKey, shorter, success);
	if (success)
	{
		tree = newRoot;
		count--;
	} // if
	return success;
} // AVL_Delete

/* =================== AVL_Retrieve ================== //16
   Retrieve node searches the tree for the node containing 
   the requested key and returns pointer to its data.
      Pre     dataOut is variable to receive data 
      Post    tree searched and data returned
	  Return  true if found,false if not found
*/

template <class TYPE, class KTYPE>
bool   AvlTree<TYPE, KTYPE>
   ::  AVL_Retrieve (KTYPE key, TYPE& dataOut)
{
// Local Definitions
	NODE<TYPE> *node;

// Statements
	if (!tree)
		return false;

	node = _retrieve (key,tree);
	if (node)
	{
		dataOut = node->data;
		return true;
	} // if found
	else
		return false;
} // AVL_Retrieve

/* =================== AVL_Traverse ================== //17
   Process tree using inorder traveral.
      Pre    process used to "visit" nodes during traversal
	  Post   all nodes process in LNR (inorder) sequence
*/

template <class TYPE,class KTYPE>
void  AvlTree<TYPE,KTYPE>
  ::  AVL_Traverse (void (*process)(TYPE dataProc))
{
// Statements
	_traversal (process, tree);
	return;
} // end AVL_Traverse

/* =================== AVL_Empty ================== //18
   Returns true if tree is empty, false if any data.
      Pre      tree has been created; may be null
	  Returns  true if tree empty ,false if any data
*/

template <class TYPE,class KTYPE>
bool  AvlTree<TYPE, KTYPE> :: AVL_Empty (void)
{
// Statements
	return (count==0);
} // AVL_Empty

/* =================== AVL_Full ================== //19
   If there is not room for another node, returns true.
     Pre        tree has been created
     Returns    true if not room,false if room
*/

template <class TYPE,class KTYPE>
bool AvlTree<TYPE, KTYPE> :: AVL_Full (void)
{
//Local Definitions
	NODE<TYPE> *newPtr;

//Statements
	newPtr = new NODE<TYPE>;
	if (newPtr)
	{
		delete newPtr;
		return false;
	} // if
	else
		return true;
} // AVL_Full

/* =================== AVL_Count ================== //20
   Returns nomber of nodes in tree.
      Pre       tree has been created
	  Returns   tree count
*/

template <class TYPE,class KTYPE>
int   AvlTree<TYPE, KTYPE> :: AVL_Count (void)
{
//Statements
return (count);

} // AVL_Count