bst.cpp.~6~

我们高校的数据结构与算法的教师讲义,适合想自学数据结构的朋友参考.

//---------------------------------------------------------------------------

#pragma hdrstop

#include "BST.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)


BinarySearchTree::BinarySearchTree():root(NULL)
{

}// end default constructor

BinarySearchTree::~BinarySearchTree()
{
	destroyTree(root);
} // end destructor

bool BinarySearchTree::isEmpty() const
{
   return (root == NULL);
} // end searchTreeIsEmpty

void BinarySearchTree::Insert(const TreeItemType& newItem)
{
   insertItem(root, newItem);
} // end searchTreeInsert

void BinarySearchTree::Delete(KeyType searchKey)
{
   deleteItem(root, searchKey);
} // end searchTreeDelete

void BinarySearchTree::preorderTraverse(FunctionType visit)
{
   preorder(root, visit);
} // end preorderTraverse

void BinarySearchTree::inorderTraverse(FunctionType visit)
{
   inorder(root, visit);
} // end inorderTraverse

void BinarySearchTree::postorderTraverse(FunctionType visit)
{
   postorder(root, visit);
} // end postorderTraverse

void BinarySearchTree::layerorderTraverse(FunctionType visit)
{
	layerorder(root,visit);
}// end layerorderTraverse

void BinarySearchTree::insertItem(TreeNode *& treePtr,
                                  const TreeItemType& newItem)
{
   if (treePtr == NULL)
   {  // position of insertion found; insert after leaf
 
      // create a new node
      treePtr = new TreeNode(newItem, NULL, NULL);
 
      // was allocation successful?
      if (treePtr == NULL)
         throw TreeException("TreeException: insert failed");
   }

   // else search for the insertion position
   else if (newItem.getKey() < treePtr->item.getKey())
      // search the left subtree
      insertItem(treePtr->leftChildPtr, newItem);

   else // search the right subtree
      insertItem(treePtr->rightChildPtr, newItem);
} // end insertItem

void BinarySearchTree::deleteItem(TreeNode * &treePtr,
                                  KeyType searchKey)

{
#ifdef USERECURSION
	// Calls: deleteNodeItem.
   if (treePtr == NULL)
      throw TreeException(
         "TreeException: delete failed"); // empty tree

   else if (searchKey == treePtr->item.getKey())
      // item is in the root of some subtree
      deleteNodeItem(treePtr); // delete the item

   // else search for the item
   else if (searchKey < treePtr->item.getKey())
      // search the left subtree
      deleteItem(treePtr->leftChildPtr, searchKey);

   else // search the right subtree
      deleteItem(treePtr->rightChildPtr, searchKey);
#else

	TreeNode *p=NULL,*pp=NULL;
	p=treePtr;
	while((p!=NULL)&&(p->item.getKey()!=searchKey))// find the item with key searchKey
	{
		pp=p;
		if(searchKey < p->item.getKey())
			p=p->leftChildPtr;
		else
			p=p->rightChildPtr;
	}
	if(p==NULL)// if there is an item with key searchKey, then it will be p,
		//so p is NULL implies that there is no item with key SearchKey
		//so we need not delete anyone node
		throw TreeException(
			    "TreeException: delete failed"); // cann't find 
	else 
		//searchKey==p->item.getKey() 
		// if there is an item with key searchKey, then it must
		// be p, so p is the item to be deleted
		// and if p isn't root , then pp is p's parent
	{
		//cout<<"find the node to be deleted\n";
		if ((p->leftChildPtr==NULL)||(p->rightChildPtr==NULL))// p has one child at most
		{				
			if(p==root)
			{
				if(p->leftChildPtr!=NULL)
					treePtr= p->leftChildPtr;
				else
					treePtr= p->rightChildPtr;// this includes the case where p is also a leaf	
				
			}
			else //if p is not root, then pp must be p's parent
				if(p==pp->leftChildPtr)  //p is leftChildPtr of pp
					if (p->leftChildPtr!=NULL)
						pp->leftChildPtr=p->leftChildPtr;
					else
						pp->leftChildPtr=p->rightChildPtr;// this includes the case where p is also a leaf
					else // p is rightChildPtr of pp
						if (p->leftChildPtr!=NULL)
							pp->rightChildPtr=p->leftChildPtr;
						else
							pp->rightChildPtr=p->rightChildPtr;// this includes the case where p is also a leaf
			delete p;
		}
		else// p has two children, and p may be root
		{
			//we should find the node just after p in inorder sequence
			TreeNode *fap=p,*fapp=pp;
			TreeNode *fapc=p->rightChildPtr;
			while(fapc!=NULL)//after this, fap is the node just after p in inorder sequence
			{
				fapp=fap;
				fap=fapc;
				fapc=fapc->leftChildPtr;
			}
			p->item=fap->item;
			if(fap==fapp->rightChildPtr)//p's rightChildPtr's leftChildPtr is NULL
				fapp->rightChildPtr=fap->rightChildPtr;
			else
				fapp->leftChildPtr=fap->rightChildPtr;
			delete fap;
		}
	}	
#endif
} // end deleteItem

void BinarySearchTree::destroyTree(TreeNode *& treePtr)
{
   // postorder traversal
   if (treePtr != NULL)
   {  destroyTree(treePtr->leftChildPtr);
      destroyTree(treePtr->rightChildPtr);
      delete treePtr;
      treePtr = NULL;
   } // end if
} // end destroyTree

void BinarySearchTree::preorder(TreeNode *treePtr,
                          FunctionType visit)
{
#ifdef USERECURSION
   if (treePtr != NULL)
   {  visit(treePtr->item);
      preorder(treePtr->leftChildPtr, visit);
      preorder(treePtr->rightChildPtr, visit);
   } // end if
#else
	Stack S;
	if (treePtr!=NULL)
	{
		S.push(treePtr);
		while(!S.isEmpty())
		{
			S.pop(treePtr);
			visit(treePtr->item);
			if(treePtr->rightChildPtr!=NULL)
				S.push(treePtr->rightChildPtr);
			if(treePtr->leftChildPtr!=NULL)
				S.push(treePtr->leftChildPtr);
		}
	}
#endif
} // end preorder

void BinarySearchTree::inorder(TreeNode *treePtr,
                         FunctionType visit)
{
#ifdef USERECURSION
   if (treePtr != NULL)
   {  inorder(treePtr->leftChildPtr, visit);
      visit(treePtr->item);
      inorder(treePtr->rightChildPtr, visit);
   } // end if
#else

	Stack S;
	if (treePtr!=NULL)
	{
		S.push(treePtr);
		treePtr=treePtr->leftChildPtr;
		while(!S.isEmpty())
		{
			while(treePtr!=NULL)
			{
				S.push(treePtr);
				treePtr=treePtr->leftChildPtr;		
			}
			S.pop(treePtr);
			visit(treePtr->item);
			treePtr=treePtr->rightChildPtr;
			if(treePtr!=NULL)
			{					
				S.push(treePtr);
				treePtr=treePtr->leftChildPtr;
			}			
		}
	}
#endif
} // end inorder

void BinarySearchTree::postorder(TreeNode *treePtr,
                           FunctionType visit)
{
#ifdef USERECURSION
   if (treePtr != NULL)
   {  postorder(treePtr->leftChildPtr, visit);
      postorder(treePtr->rightChildPtr, visit);
      visit(treePtr->item);
   } // end if
#else
	Stack S;
	TreeNode *tempnode;
	if(treePtr!=NULL)
	{
		while(treePtr!=NULL)
		{
			S.push(treePtr);
			treePtr=treePtr->leftChildPtr;
		}
		while(!S.isEmpty())
		{
			S.getTop(tempnode);		
			while (treePtr!=tempnode->rightChildPtr)
			{
				treePtr=tempnode->rightChildPtr;
				while(treePtr!=NULL)
				{
					S.push(treePtr);
					treePtr=treePtr->leftChildPtr;
				}
				S.getTop(tempnode);
			}
			S.pop(treePtr);
			visit(treePtr->item);
		}
	}
#endif
} // end postorder



void BinarySearchTree::layerorder(TreeNode *treePtr, FunctionType visit)
{
	Queue Q;
	if(treePtr!=NULL)
	{
		Q.enqueue(treePtr);
		while(!Q.isEmpty())
		{
			Q.dequeue(treePtr);
			visit(treePtr->item);
			if(treePtr->leftChildPtr!=NULL)
				Q.enqueue(treePtr->leftChildPtr);
			if(treePtr->rightChildPtr!=NULL)
				Q.enqueue(treePtr->rightChildPtr);
		}
	}

}


// End of implementation file.