class BinarySearchTree
1: // Created by Frank M. Carrano and Tim Henry.
2: // Copyright (c) 2013 __Pearson Education__. All rights reserved.
4: // Listing 16-4.
6: /** Link-based implementation of the ADT binary search tree.
7: @file BinarySearchTree.h */
8:
9: #ifndef _BINARY_SEARCH_TREE
10: #define _BINARY_SEARCH_TREE
12: #include "BinaryTreeInterface.h"
13: #include "BinaryNode.h"
14: #include "BinaryNodeTree.h"
15: #include "NotFoundException.h"
16: #include "PrecondViolatedExcep.h"
18: template<class ItemType>
19: class BinarySearchTree : public BinaryNodeTree<ItemType>
20: {
21: private:
22: BinaryNode<ItemType>* rootPtr;
23:
24: protected:
25: //------------------------------------------------------------
26: // Protected Utility Methods Section:
27: // Recursive helper methods for the public methods.
28: //------------------------------------------------------------
29: // Recursively finds where the given node should be placed and
30: // inserts it in a leaf at that point.
31: BinaryNode<ItemType>* insertInorder(BinaryNode<ItemType>* subTreePtr,
32: BinaryNode<ItemType>* newNode);
33:
34: // Removes the given target value from the tree while maintaining a
35: // binary search tree.
36: BinaryNode<ItemType>* removeValue(BinaryNode<ItemType>* subTreePtr,
37: const ItemType target,
38: bool& success);
39:
40: // Removes a given node from a tree while maintaining a
41: // binary search tree.
42: BinaryNode<ItemType>* removeNode(BinaryNode<ItemType>* nodePtr);
43:
44: // Removes the leftmost node in the left subtree of the node
45: // pointed to by nodePtr.
46: // Sets inorderSuccessor to the value in this node.
47: // Returns a pointer to the revised subtree.
48: BinaryNode<ItemType>* removeLeftmostNode(BinaryNode<ItemType>* subTreePtr,
49: ItemType& inorderSuccessor);
50:
51: // Returns a pointer to the node containing the given value,
52: // or nullptr if not found.
53: BinaryNode<ItemType>* findNode(BinaryNode<ItemType>* treePtr,
54: const ItemType& target) const;
55:
56: public:
57: //------------------------------------------------------------
58: // Constructor and Destructor Section.
59: //------------------------------------------------------------
60: BinarySearchTree();
61: BinarySearchTree(const ItemType& rootItem);
62: BinarySearchTree(const BinarySearchTree<ItemType>& tree);
63: virtual ~BinarySearchTree();
64:
65: //------------------------------------------------------------
66: // Public Methods Section.
67: //------------------------------------------------------------
68: bool isEmpty() const;
69: int getHeight() const;
70: int getNumberOfNodes() const;
71: ItemType getRootData() const throw(PrecondViolatedExcep);
72: void setRootData(const ItemType& newData) const
73: throw(PrecondViolatedExcep);
74: bool add(const ItemType& newEntry);
75: bool remove(const ItemType& anEntry);
76: void clear();
77: ItemType getEntry(const ItemType& anEntry) const
78: throw(NotFoundException);
79: bool contains(const ItemType& anEntry) const;
80:
81: //------------------------------------------------------------
82: // Public Traversals Section.
83: //------------------------------------------------------------
84: void preorderTraverse(void visit(ItemType&)) const;
85: void inorderTraverse(void visit(ItemType&)) const;
86: void postorderTraverse(void visit(ItemType&)) const;
87:
88: //------------------------------------------------------------
89: // Overloaded Operator Section.
90: //------------------------------------------------------------
91: BinarySearchTree<ItemType>& operator=(const BinarySearchTree<ItemType>& rightHandSide);
92: }; // end BinarySearchTree
94: #include "BinarySearchTree.cpp"
96: #endif