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