bst.cpp.~12~

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

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

#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   // else search for the insertion position
   {
		TreeNode *p=NULL,*pp=NULL;
		p=treePtr;
		while((p!=NULL)&&(p->item.getKey()!=newItem.getKey() ))// find the item with key searchKey
		{
			pp=p;
			if(newItem.getKey() < p->item.getKey())
				p=p->leftChildPtr;
			else
				p=p->rightChildPtr;
		}
		if(p==NULL)// if there is an item which has same  key with newItem, then it will be p,
		//so p is NULL implies that there is no item with key SearchKey
		//so we need insert as pp's child
		{
			if(newItem.getKey() < pp->item.getKey())
				pp->leftChildPtr= new TreeNode(newItem, NULL, NULL);
			else
				pp->rightChildPtr= new TreeNode(newItem, NULL, NULL);
		}
		else// if p is not NULL, which means there is an item which has same  key with newItem,
		//so we need not change the tree, so we do nothing.
		;
   }

} // end insertItem

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

{


	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;
		}
	}	

} // 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
   	if(treePtr!=NULL)
	{
		preorder(treePtr->leftChildPtr,visit);
		preorder(treePtr->rightChildPtr,visit);
		visit(treePtr->item);
    }


} // end preorder

void BinarySearchTree::inorder(TreeNode *treePtr,
                         FunctionType visit)
{
	//添加你自己的代码，详见实验 3
	if(treePtr!=NULL)
	{
		inorder(treePtr->leftChildPtr,visit);
		visit(treePtr->item);
		inorder(treePtr->rightChildPtr,visit);
    }
} // end inorder

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



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

}


// End of implementation file.