// Chap 10, pp485 - 489
// Rename this file as 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 "boolean.h"
typedef int keyType; // desired-type-of-search-key
struct dataItem
{ keyType Key;
//... and probably other data members
}; // end struct
typedef dataItem treeItemType;
struct treeNode; // defined in implementation file
typedef treeNode* ptrType;
typedef void (*functionType)(treeItemType& AnItem);
class bstClass
{
public:
// constructors and destructor:
bstClass();
bstClass(const bstClass& T);
virtual ~bstClass();
// binary search tree operations:
// Precondition for all methods: The constructor has been
// called. No two items in a binary search tree have the
// same search key.
virtual boolean SearchTreeIsEmpty();
// Determines whether a binary search tree is empty.
// Postcondition: Returns TRUE if the tree is empty,
// otherwise returns FALSE.
virtual void SearchTreeInsert(treeItemType NewItem,
boolean& Success);
// Inserts an item into a binary search tree.
// Precondition: The item to be inserted into the tree
// is NewItem.
// Postcondition: If the insertion was successful,
// NewItem is in its proper order in the tree and
// Success is TRUE. Otherwise, the tree is unchanged and
// Success is FALSE.
virtual void SearchTreeDelete(keyType SearchKey,
boolean& Success);
// 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 and
// Success is TRUE. Otherwise, the tree is unchanged and
// Success is FALSE.
virtual void SearchTreeRetrieve(keyType SearchKey,
treeItemType& TreeItem,
boolean& Success);
// 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 and Success is
// TRUE. If no such item exists, TreeItem and the tree
// are unchanged and Success is FALSE.
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 occurs 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.
// overloaded operator:
void operator=(const bstClass& T);
protected:
void InsertItem(ptrType& TreePtr, treeItemType NewItem,
boolean& Success);
// Recursively inserts an item into a binary search tree.
// Precondition: TreePtr points to a binary search tree,
// NewItem is the node to be inserted.
// Postcondition: Same as SearchTreeInsert.
void ProcessLeftmost(ptrType& NodePtr,
treeItemType& TreeItem);
// Retrieves and deletes the leftmost descendant of a
// given node.
// Precondition: NodePtr points to a node in a binary
// search tree.
// Postcondition: TreeItem contains the item in the
// leftmost descendant of the node to which NodePtr
// points. The leftmost descendant of NodePtr is
// deleted.
void DeleteRootItem(ptrType& RootPtr);
// Deletes the item in the root of a given tree.
// Precondition: RootPtr points to the root of a
// binary search tree.
// Postcondition: The item in the root of the given
// tree is deleted.
void DeleteItem(ptrType& TreePtr, keyType SearchKey,
boolean& Success);
// 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.
void RetrieveItem(ptrType TreePtr, keyType SearchKey,
treeItemType& TreeItem,
boolean& Success);
// 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.
// The following 3 methods are the same as for the ADT
// binary tree, and so their specifications are abbreviated.
// They recursively traverse the binary search tree to
// which TreePtr points, calling the function Visit once
// for each item.
void Preorder(ptrType TreePtr, functionType Visit);
void Inorder(ptrType TreePtr, functionType Visit);
void Postorder(ptrType TreePtr, functionType Visit);
void CopyTree(ptrType TreePtr,
ptrType& NewTreePtr);
// Copies the tree rooted at TreePtr into a tree rooted
// at NewTreePtr.
void DestroyTree(ptrType& TreePtr);
// Deallocates memory for a tree.
void SetRootPtr(ptrType NewRoot);
// Sets private data member Root to NewRoot.
ptrType RootPtr();
// Returns a pointer to the root of the tree.
private:
ptrType Root; // pointer to root of tree
}; // end class
// End of header file.
(
geocities.com/siliconvalley/program/2864/ds) (
geocities.com/siliconvalley/program/2864) (
geocities.com/siliconvalley/program) (
geocities.com/siliconvalley)