/* This file contains the declaration of class BST. ---------------------------------------------------------------*/ #ifndef BSTREE #define BSTREE #include "Boolean.h" #include "Student.h" typedef Student BinTreeElement; class BST { protected: // allow derived classes to access members struct Node // the nodes of the tree { BinTreeElement // the value of the node Data; Node *Left, // the left subtree of the node *Right; // the right subtree of the node /* ----- This function constructs a Node with default values. Precondition: A Node has been declared (no arguments). Postcondition: The Node has been initialized with default values. ------------------------------------------------------------------*/ Node(void) { Left = Right = 0; } /* ----- This function constructs a Node with supplied values. Precondition: A Node has been declared with arguments. Receive: Elem, a BinTreeElement value LPtr and RPtr, two node addresses (default NULL). Postcondition: The Node has been initialized with the given values. ------------------------------------------------------------------*/ Node(const BinTreeElement& Elem, Node *LPtr = 0, Node *RPtr = 0) { Data = Elem; Left = LPtr; Right = RPtr; } /* This function recursively copies any binary subtree. Precondition: A copy of a subtree is needed by the compiler. Receive: ONode, a reference to the root of the subtree being copied Postcondition: The Node containing this function is a copy of ONode, and the subtrees of this Node are copies as well. ------------------------------------------------------------------*/ Node(const Node& ONode); /* --- This function reclaims the storage of a Node's subtrees. Precondition: The lifetime of the Node containing this function is over. Postcondition: All of the dynamic storage allocated to the subtrees of this Node has been reclaimed. ------------------------------------------------------------------*/ ~Node(void) { delete Left; // invoke Left->~Node() indirectly delete Right; // do right subtree the same way } /* This function inserts a BinTreeElement into a Node. Receive: Elem, the BinTreeElement being inserted Return: The Node containing this function, with Elem inserted in the appropriate subtree position ------------------------------------------------------------------*/ void Insert(const BinTreeElement& Elem); /* This function recursively deletes a value from the Nodes of a BST. Receive: Elem, the BinTreeElement being deleted AccessPtr, a (reference) to the pointer by which the Node containing this function was reached Return: The BST containing this function, with the Node containing Elem deleted True if and only if the operation succeeds. ------------------------------------------------------------------*/ Boolean Delete(const BinTreeElement& Elem, Node *& AccessPtr); /* This function recursively displays a Node (and its subtrees), using the inorder traversal pattern. Receive: An ostream and a Node Output: The values from the left subtree, the Node, and its right subtree onto the ostream, in ascending order Return: The ostream ----------------------------------------------------------------*/ friend ostream& operator<<(ostream& Out, const Node& N) /* This function recursively searches the Nodes of a BST for a BinTreeElement. Receive: Elem, the BinTreeElement being sough. Return: True if Elem is in the Node containing this function or in either of its subtrees False, otherwise ------------------------------------------------------------------*/ Boolean Search(const BinTreeElement& Elem) const; }; typedef Node *NodePtr; // an easy-to-read type NodePtr Root; // pointer to the root node of the BST public: /* ----- This function constructs a BST as an empty tree. Precondition: A BST has been declared (no arguments). Postcondition: The BST has been initialized as an empty tree. ---------------------------------------------------------------------*/ BST(void) { Root = 0; } /* This function makes a copy of a binary search tree. Precondition: A copy of a BST is needed by the compiler. Receive: OTree, reference to the original BST (being copied) Postcondition: The BST containing this function is a copy of OTree. --------------------------------------------------------------------*/ BST(const BST& OTree); /* This function tears down a BST, reclaiming its storage. Precondition: The lifetime of the BST containing this function is over. Postcondition: All of the dynamic storage allocated to this BST has been reclaimed. ------------------------------------------------------------------*/ ~BST(void) { delete Root; // invoke Root->~Node() indirectly Root = 0; // reset as empty tree } /* This function inserts a BinTreeElement into a BST. Receive: Elem, the BinTreeElement being inserted Return: The BST containing this function, with Elem inserted in the appropriate BST position ------------------------------------------------------------------*/ void Insert(const BinTreeElement& Elem); /* This function displays a BST. Receive: An ostream and a BST Output: The values of the BST onto the ostream Return: The ostream ----------------------------------------------------------------*/ friend ostream& operator<<(ostream& Out, const BST& Tree); /* This function searches a BST for a BinTreeElement. Receive: Elem, the BinTreeElement being sought Return: True, if Elem is in the BST containing this function, False, otherwise ------------------------------------------------------------------*/ Boolean Search(const BinTreeElement& Elem) const; /* This function deletes a BinTreeElement from a BST. Receive: Elem, the BinTreeElement being deleted Return: The BST containing this function with Elem deleted True if and only if the operation is successful ------------------------------------------------------------------*/ Boolean Delete(const BinTreeElement& Elem); /* This function deletes a Node from a binary search tree. Receive: AccessPtr, a pointer to the Node from its parent (if there is one) Return: The BST of which this node is a part, but with this Node removed --------------------------------------------------------------------*/ friend void DelNode(NodePtr& AccessPtr); /* This function finds the leftmost value in a given subtree, deletes the node containing that value, and returns the value. Receive: NPtr, the pointer by which this Node was accessed Return: The value from the deleted Node The BST of which this node is the root, with its leftmost Node deleted -----------------------------------------------------------------*/ friend BinTreeElement LeftMostValue(NodePtr& NPtr); }; #endif