Data Abstraction and Problem Solving with C++

Walls and Mirrors

by Frank M. Carrano

BinarySearchTree Class Reference

#include <BST.h>

List of all members.

Detailed Description

ADT binary search tree. Assumption: A tree contains at most one item with a given search key at any time.

Definition at line 25 of file BST.h.

Public Member Functions

BinarySearchTree ()

BinarySearchTree (const BinarySearchTree &tree) throw (TreeException)

virtual ~BinarySearchTree ()

virtual bool isEmpty () const

virtual void searchTreeInsert (const TreeItemType &newItem) throw (TreeException)

virtual void searchTreeDelete (KeyType searchKey) throw (TreeException)

virtual void searchTreeRetrieve (KeyType searchKey, TreeItemType &treeItem) const throw (TreeException)

virtual void preorderTraverse (FunctionType visit)

virtual void inorderTraverse (FunctionType visit)

virtual void postorderTraverse (FunctionType visit)

virtual BinarySearchTree & operator= (const BinarySearchTree &rhs) throw (TreeException)

Protected Member Functions

void insertItem (TreeNode *&treePtr, const TreeItemType &newItem) throw (TreeException)

void deleteItem (TreeNode *&treePtr, KeyType searchKey) throw (TreeException)

void deleteNodeItem (TreeNode *&nodePtr)

void processLeftmost (TreeNode *&nodePtr, TreeItemType &treeItem)

void retrieveItem (TreeNode *treePtr, KeyType searchKey, TreeItemType &treeItem) const throw (TreeException)

void copyTree (TreeNode *treePtr, TreeNode *&newTreePtr) const throw (TreeException)

void destroyTree (TreeNode *&treePtr)

void preorder (TreeNode *treePtr, FunctionType visit)

void inorder (TreeNode *treePtr, FunctionType visit)

void postorder (TreeNode *treePtr, FunctionType visit)

TreeNode * rootPtr () const

void setRootPtr (TreeNode *newRoot)

void getChildPtrs (TreeNode *nodePtr, TreeNode *&leftChildPtr, TreeNode *&rightChildPtr) const

void setChildPtrs (TreeNode *nodePtr, TreeNode *leftChildPtr, TreeNode *rightChildPtr)

Private Attributes

TreeNode * root

Constructor & Destructor Documentation

BinarySearchTree::BinarySearchTree ( )

Definition at line 22 of file BST.cpp.

BinarySearchTree::BinarySearchTree ( const BinarySearchTree & tree ) throw (TreeException)

Definition at line 26 of file BST.cpp.

BinarySearchTree::~BinarySearchTree ( ) [virtual]

Definition at line 32 of file BST.cpp.
References destroyTree(), and root.

Member Function Documentation

bool BinarySearchTree::isEmpty ( ) const [virtual]

Determines whether a binary search tree is empty.
Returns:
True if the tree is empty; otherwise returns false.

Definition at line 37 of file BST.cpp.
References root.

void BinarySearchTree::searchTreeInsert ( const TreeItemType & newItem ) throw (TreeException) [virtual]

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.

Exceptions:

TreeException If memory allocation fails.

Definition at line 42 of file BST.cpp.

void BinarySearchTree::searchTreeDelete ( KeyType searchKey ) throw (TreeException) [virtual]

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.

Exceptions:

TreeException If searchKey is not found in the tree.

Definition at line 48 of file BST.cpp.

void BinarySearchTree::searchTreeRetrieve ( KeyType searchKey,

TreeItemType & treeItem

) const throw (TreeException) [virtual]

Retrieves an item with a given search key from a binary search tree.
Precondition:
searchKey is the search key of the item to be retrieved.

Postcondition:
If the retrieval was successful, treeItem contains the retrieved item.

Exceptions:

TreeException If no such item exists.

Definition at line 54 of file BST.cpp.

void BinarySearchTree::preorderTraverse ( FunctionType visit ) [virtual]

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.

Definition at line 64 of file BST.cpp.
References preorder(), and root.

void BinarySearchTree::inorderTraverse ( FunctionType visit ) [virtual]

Traverses a binary search tree in sorted order, calling function visit() once for each item.
Definition at line 69 of file BST.cpp.
References inorder(), and root.
Referenced by Table::traverseTable().

void BinarySearchTree::postorderTraverse ( FunctionType visit ) [virtual]

Traverses a binary search tree in postorder, calling function visit() once for each item.
Definition at line 74 of file BST.cpp.
References postorder(), and root.

virtual BinarySearchTree& BinarySearchTree::operator= ( const BinarySearchTree & rhs ) throw (TreeException) [virtual]

void BinarySearchTree::insertItem ( TreeNode *& treePtr,

const TreeItemType & newItem

) throw (TreeException) [protected]

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:
Same as searchTreeInsert.

Exceptions:

Same as searchTreeInsert.

Definition at line 79 of file BST.cpp.

void BinarySearchTree::deleteItem ( TreeNode *& treePtr,

KeyType searchKey

) throw (TreeException) [protected]

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

Exceptions:

Same as searchTreeDelete.

Definition at line 106 of file BST.cpp.

void BinarySearchTree::deleteNodeItem ( TreeNode *& nodePtr ) [protected]

Deletes the item in the root of a given tree.
Precondition:
nodePtr points to the root of a binary search tree; nodePtr != NULL.

Postcondition:
The item in the root of the given tree is deleted.

Definition at line 127 of file BST.cpp.
References TreeNode::item, TreeNode::leftChildPtr, processLeftmost(), and TreeNode::rightChildPtr.

void BinarySearchTree::processLeftmost ( TreeNode *& nodePtr,

TreeItemType & treeItem

) [protected]

Retrieves and deletes the leftmost descendant of a given node.
Precondition:
nodePtr points to a node in a binary search tree; nodePtr != NULL.

Postcondition:
treeItem contains the item in the leftmost descendant of the node to which nodePtr points. The leftmost descendant of nodePtr is deleted.

Definition at line 169 of file BST.cpp.
References TreeNode::item, TreeNode::leftChildPtr, and TreeNode::rightChildPtr.
Referenced by deleteNodeItem().

void BinarySearchTree::retrieveItem ( TreeNode * treePtr,

KeyType searchKey,

TreeItemType & treeItem

) const throw (TreeException) [protected]

Recursively retrieves 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 retrieved.

Postcondition:
Same as searchTreeRetrieve.

Exceptions:

Same as searchTreeRetrieve.

Definition at line 183 of file BST.cpp.

void BinarySearchTree::copyTree ( TreeNode * treePtr,

TreeNode *& newTreePtr

) const throw (TreeException) [protected]

void BinarySearchTree::destroyTree ( TreeNode *& treePtr ) [protected]

Referenced by ~BinarySearchTree().

void BinarySearchTree::preorder ( TreeNode * treePtr,

FunctionType visit

) [protected]

Referenced by preorderTraverse().

void BinarySearchTree::inorder ( TreeNode * treePtr,

FunctionType visit

) [protected]

Referenced by inorderTraverse().

void BinarySearchTree::postorder ( TreeNode * treePtr,

FunctionType visit

) [protected]

Referenced by postorderTraverse().

TreeNode* BinarySearchTree::rootPtr ( ) const [protected]

void BinarySearchTree::setRootPtr ( TreeNode * newRoot ) [protected]

void BinarySearchTree::getChildPtrs ( TreeNode * nodePtr,

TreeNode *& leftChildPtr,

TreeNode *& rightChildPtr

) const [protected]

void BinarySearchTree::setChildPtrs ( TreeNode * nodePtr,

TreeNode * leftChildPtr,

TreeNode * rightChildPtr

) [protected]

Member Data Documentation

TreeNode* BinarySearchTree::root [private]

Pointer to root of tree.
Definition at line 158 of file BST.h.
Referenced by inorderTraverse(), isEmpty(), postorderTraverse(), preorderTraverse(), and ~BinarySearchTree().

The documentation for this class was generated from the following files:

Generated on Sun Aug 27 22:04:07 2006 for

1.4.6