bst.cpp.~7~

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

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

#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)
{

   //添加你自己的代码，详见实验 3

} // end preorder

void BinarySearchTree::inorder(TreeNode *treePtr,
                         FunctionType visit)
{
	//添加你自己的代码，详见实验 3
} // end inorder

void BinarySearchTree::postorder(TreeNode *treePtr,
						   FunctionType visit)
{
	//添加你自己的代码，详见实验 3
} // end postorder



void BinarySearchTree::layerorder(TreeNode *treePtr, FunctionType visit)
{
	//添加你自己的代码，详见实验 3

}


// End of implementation file.