bst.h.~3~

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

#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.

#endif