class BinaryNodeTree
1: // Created by Frank M. Carrano and Timothy M. Henry.
2: // Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
4: // Listing 16-3.
6: /** ADT binary tree: Link-based implementation.
7: @file BinaryNodeTree.h */
8:
9: #ifndef BINARY_NODE_TREE_
10: #define BINARY_NODE_TREE_
12: #include "BinaryTreeInterface.h"
13: #include "BinaryNode.h"
14: #include "PrecondViolatedExcept.h"
15: #include "NotFoundException.h"
16: #include <memory>
18: template<class ItemType>
19: class BinaryNodeTree : public BinaryTreeInterface<ItemType>
20: {
21: private:
22: std::shared_ptr<BinaryNode<ItemType>> rootPtr;
23:
24: protected:
25: //------------------------------------------------------------
26: // Protected Utility Methods Section:
27: // Recursive helper methods for the public methods.
28: //------------------------------------------------------------
29: int getHeightHelper(std::shared_ptr<BinaryNode<ItemType>> subTreePtr) const;
30: int getNumberOfNodesHelper(std::shared_ptr<BinaryNode<ItemType>> subTreePtr) const;
31:
32: // Recursively adds a new node to the tree in a left/right fashion to keep tree balanced.
33: auto balancedAdd(std::shared_ptr<BinaryNode<ItemType>> subTreePtr,
34: std::shared_ptr<BinaryNode<ItemType>> newNodePtr);
35:
36: // Removes the target value from the tree.
37: virtual auto removeValue(std::shared_ptr<BinaryNode<ItemType>> subTreePtr,
38: const ItemType target, bool& isSuccessful);
39:
40: // Copies values up the tree to overwrite value in current node until
41: // a leaf is reached; the leaf is then removed, since its value is stored in the parent.
42: auto moveValuesUpTree(std::shared_ptr<BinaryNode<ItemType>> subTreePtr);
43:
44: // Recursively searches for target value.
45: virtual auto findNode(std::shared_ptr<BinaryNode<ItemType>> treePtr,
46: const ItemType& target, bool& isSuccessful) const;
47:
48: // Copies the tree rooted at treePtr and returns a pointer to the root of the copy.
49: auto copyTree(const std::shared_ptr<BinaryNode<ItemType>> oldTreeRootPtr) const;
50:
51: // Recursively deletes all nodes from the tree.
52: void destroyTree(std::shared_ptr<BinaryNode<ItemType>> subTreePtr);
53:
54: // Recursive traversal helper methods:
55: void preorder(void visit(ItemType&), std::shared_ptr<BinaryNode<ItemType>> treePtr) const;
56: void inorder(void visit(ItemType&), std::shared_ptr<BinaryNode<ItemType>> treePtr) const;
57: void postorder(void visit(ItemType&), std::shared_ptr<BinaryNode<ItemType>> treePtr) const;
58:
59: public:
60: //------------------------------------------------------------
61: // Constructor and Destructor Section.
62: //------------------------------------------------------------
63: BinaryNodeTree();
64: BinaryNodeTree(const ItemType& rootItem);
65: BinaryNodeTree(const ItemType& rootItem,
66: const std::shared_ptr<BinaryNodeTree<ItemType>> leftTreePtr,
67: const std::shared_ptr<BinaryNodeTree<ItemType>> rightTreePtr);
68: BinaryNodeTree(const std::shared_ptr<BinaryNodeTree<ItemType>>& tree);
69: virtual ~BinaryNodeTree();
70:
71: //------------------------------------------------------------
72: // Public BinaryTreeInterface Methods Section.
73: //------------------------------------------------------------
74: bool isEmpty() const;
75: int getHeight() const;
76: int getNumberOfNodes() const;
77:
78: ItemType getRootData() const throw(PrecondViolatedExcept);
79: void setRootData(const ItemType& newData);
80:
81: bool add(const ItemType& newData); // Adds an item to the tree
82: bool remove(const ItemType& data); // Removes specified item from the tree
83: void clear();
84:
85: ItemType getEntry(const ItemType& anEntry) const throw(NotFoundException);
86: bool contains(const ItemType& anEntry) const;
87:
88: //------------------------------------------------------------
89: // Public Traversals Section.
90: //------------------------------------------------------------
91: void preorderTraverse(void visit(ItemType&)) const;
92: void inorderTraverse(void visit(ItemType&)) const;
93: void postorderTraverse(void visit(ItemType&)) const;
94:
95: //------------------------------------------------------------
96: // Overloaded Operator Section.
97: //------------------------------------------------------------
98: BinaryNodeTree& operator=(const BinaryNodeTree& rightHandSide);
99: }; // end BinaryNodeTree
101: #include "BinaryNodeTree.cpp"
102: #endif