bst.h.~5~

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

#ifndef BST_H
#define BST_H

// *********************************************************
// Header file BST.h for the ADT binary search tree.
// Assumption: A tree contains at most one item with a given
// search key at any time.
// *********************************************************
#include "TreeNodeBST.h"  // Note use of file TreeNodeBST.h
                          // Defines TreeNode with KeyedItem

typedef void (*FunctionType)(TreeItemType& anItem);

class BinarySearchTree
{
public:

// constructors and destructor:
   BinarySearchTree();
//   BinarySearchTree(const BinarySearchTree& tree);
   virtual ~BinarySearchTree();

// binary search tree operations:
// Precondition for all methods: No two items in a binary
// search tree have the same search key.

   virtual bool isEmpty() const;
   // Determines whether a binary search tree is empty.
   // Postcondition: Returns true if the tree is empty;
   // otherwise returns false.

   virtual void Insert(const TreeItemType& newItem);
   // Inserts an item into a binary search tree.
   // Precondition: The item to be inserted into the tree
   // is newItem.
   // Postcondition: newItem is in its proper order in the
   // tree.

   virtual void Delete(KeyType searchKey);

   // Deletes an item with a given search key from a binary
   // search tree.
   // Precondition: searchKey is the search key of the item
   // to be deleted.
   // Postcondition: If the item whose search key equals
   // searchKey existed in the tree, the item is deleted.
   // Otherwise, the tree is unchanged

   virtual void preorderTraverse(FunctionType visit);
   // Traverses a binary search tree in preorder,
   // calling function visit() once for each item.
   // Precondition: The function represented by visit()
   // exists outside of the class implementation.
   // Postcondition: visit's action occurred once for each
   // item in the tree.
   // Note: visit() can alter the tree.

   virtual void inorderTraverse(FunctionType visit);
   // Traverses a binary search tree in sorted order,
   // calling function visit() once for each item.

   virtual void postorderTraverse(FunctionType visit);
   // Traverses a binary search tree in postorder,
   // calling function visit() once for each item.

   virtual void layerorderTraverse(FunctionType visit);  
   // Traverses a binary search tree layer by layer,
   // calling function visit() once for each item.

   // overloaded operator:

protected:

   void insertItem(TreeNode * &treePtr,
                   const TreeItemType& newItem);
   // Recursively inserts an item into a binary search tree.
   // Precondition: treePtr points to a binary search tree,
   // newItem is the item to be inserted.
   // Postcondition: Insert.

   void deleteItem(TreeNode * &treePtr, KeyType searchKey);
   // Recursively deletes an item from a binary search tree.
   // Precondition: treePtr points to a binary search tree,
   // searchKey is the search key of the item to be deleted.
   // Postcondition: Same as Delete.

   void destroyTree(TreeNode * &treePtr);

   void preorder(TreeNode *treePtr, FunctionType visit);
   void inorder(TreeNode *treePtr, FunctionType visit);
   void postorder(TreeNode *treePtr, FunctionType visit);
   void layerorder(TreeNode *treePtr, FunctionType visit);
private:
   TreeNode *root; // pointer to root of tree
}; // end class
// End of header file.

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.


#endif