Chapter 11 - Binary Search Tree-based Table: BST.h Source File

00001 
00016 #include "TreeException.h"
00017 #include "TreeNode.h"
00018 
00019 typedef void (*FunctionType)(TreeItemType& anItem);
00020 
00025 class BinarySearchTree
00026 {
00027 public:
00028 // constructors and destructor:
00029    BinarySearchTree();
00030    BinarySearchTree(const BinarySearchTree& tree)
00031       throw(TreeException);
00032    virtual ~BinarySearchTree();
00033 
00034 // binary search tree operations:
00035 // Precondition for all methods: No two items in a binary
00036 // search tree have the same search key.
00037 
00041    virtual bool isEmpty() const;
00042 
00047    virtual void searchTreeInsert(const TreeItemType& newItem)
00048       throw(TreeException);
00049 
00058    virtual void searchTreeDelete(KeyType searchKey)
00059       throw(TreeException);
00060 
00068    virtual void searchTreeRetrieve(KeyType searchKey,
00069                TreeItemType& treeItem) const
00070       throw(TreeException);
00071 
00079    virtual void preorderTraverse(FunctionType visit);
00080 
00083    virtual void inorderTraverse(FunctionType visit);
00084 
00087    virtual void postorderTraverse(FunctionType visit);
00088 
00089 // overloaded operator:
00090    virtual BinarySearchTree& operator=(const BinarySearchTree& rhs)
00091       throw(TreeException);
00092 
00093 protected:
00099    void insertItem(TreeNode *& treePtr,
00100                    const TreeItemType& newItem)
00101       throw(TreeException);
00102 
00108    void deleteItem(TreeNode *& treePtr, KeyType searchKey)
00109       throw(TreeException);
00110 
00115    void deleteNodeItem(TreeNode *& nodePtr);
00116 
00124    void processLeftmost(TreeNode *& nodePtr,
00125                         TreeItemType& treeItem);
00126 
00132    void retrieveItem(TreeNode *treePtr, KeyType searchKey,
00133                      TreeItemType& treeItem) const
00134       throw(TreeException);
00135 
00136 // The following 9 methods are the same as for the ADT
00137 // binary tree, and so their specifications are abbreviated.
00138    void copyTree(TreeNode *treePtr, TreeNode *& newTreePtr) const
00139       throw(TreeException);
00140    void destroyTree(TreeNode *& treePtr);
00141 
00142    void preorder(TreeNode *treePtr, FunctionType visit);
00143    void inorder(TreeNode *treePtr, FunctionType visit);
00144    void postorder(TreeNode *treePtr, FunctionType visit);
00145 
00146    TreeNode *rootPtr() const;
00147    void setRootPtr(TreeNode *newRoot);
00148 
00149    void getChildPtrs(TreeNode *nodePtr,
00150                      TreeNode *& leftChildPtr,
00151                      TreeNode *& rightChildPtr) const;
00152    void setChildPtrs(TreeNode *nodePtr,
00153                      TreeNode *leftChildPtr,
00154                      TreeNode *rightChildPtr);
00155 
00156 private:
00158    TreeNode *root;
00159 }; // end BinarySearchTree
00160 // End of header file.
Data Abstraction and Problem Solving with C++

Walls and Mirrors

by Frank M. Carrano

BST.h
