class BinarySearchTree
1: // Created by Frank M. Carrano and Timothy M. Henry.
2: // Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
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 "PrecondViolatedExcept.h"
17: #include <memory>
19: template<class ItemType>
20: class BinarySearchTree : public BinaryNodeTree<ItemType>
21: {
22: private:
23: std::shared_ptr<BinaryNode<ItemType>> rootPtr;
24:
25: protected:
26: //------------------------------------------------------------
27: // Protected Utility Methods Section:
28: // Recursive helper methods for the public methods.
29: //------------------------------------------------------------
30: // Places a given new node at its proper position in this binary
31: // search tree.
32: auto placeNode(std::shared_ptr<BinaryNode<ItemType>> subTreePtr,
33: std::shared_ptr<BinaryNode<ItemType>> newNode);
34:
35: // Removes the given target value from the tree while maintaining a
36: // binary search tree.
37: auto removeValue(std::shared_ptr<BinaryNode<ItemType>> subTreePtr,
38: const ItemType target,
39: bool& isSuccessful) override;
40:
41: // Removes a given node from a tree while maintaining a binary search tree.
42: auto removeNode(std::shared_ptr<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: auto removeLeftmostNode(std::shared_ptr<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: auto findNode(std::shared_ptr<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:
72: ItemType getRootData() const throw(PrecondViolatedExcept);
73: void setRootData(const ItemType& newData);
74:
75: bool add(const ItemType& newEntry);
76: bool remove(const ItemType& target);
77: void clear();
78:
79: ItemType getEntry(const ItemType& anEntry) const throw(NotFoundException);
80: bool contains(const ItemType& anEntry) const;
81:
82: //------------------------------------------------------------
83: // Public Traversals Section.
84: //------------------------------------------------------------
85: void preorderTraverse(void visit(ItemType&)) const;
86: void inorderTraverse(void visit(ItemType&)) const;
87: void postorderTraverse(void visit(ItemType&)) const;
88:
89: //------------------------------------------------------------
90: // Overloaded Operator Section.
91: //------------------------------------------------------------
92: BinarySearchTree<ItemType>&
93: operator=(const BinarySearchTree<ItemType>& rightHandSide);
94: }; // end BinarySearchTree
96: #include "BinarySearchTree.cpp"
97: #endif