1: // Created by Frank M. Carrano and Tim Henry.
2: // Copyright (c) 2013 __Pearson Education__. All rights reserved.
4: // PARITALLY COMPLETE.
6: /** @file BinaryTree.cpp */
8: #include "BinaryNodeTree.h"
9: #include "BinaryNode.h"
10: #include <iostream>
12: //////////////////////////////////////////////////////////////
13: // Protected Utility Methods Section
14: //////////////////////////////////////////////////////////////
16: template<class ItemType>
17: int BinaryNodeTree<ItemType>::getHeightHelper(BinaryNode<ItemType>* subTreePtr) const
18: {
19: if (subTreePtr == nullptr)
20: return 0;
21: else
22: return 1 + max(getHeightHelper(subTreePtr->getLeftChildPtr()),
23: getHeightHelper(subTreePtr->getRightChildPtr()));
24: } // end getHeightHelper
26: template<class ItemType>
27: BinaryNode<ItemType>* BinaryNodeTree<ItemType>::balancedAdd(BinaryNode<ItemType>* subTreePtr,
28: BinaryNode<ItemType>* newNodePtr)
29: {
30: if (subTreePtr == nullptr)
31: return newNodePtr;
32: else
33: {
34: BinaryNode<ItemType>* leftPtr = subTreePtr->getLeftChildPtr();
35: BinaryNode<ItemType>* rightPtr = subTreePtr->getRightChildPtr();
36:
37: if (getHeightHelper(leftPtr) > getHeightHelper(rightPtr))
38: {
39: rightPtr = balancedAdd(rightPtr , newNodePtr);
40: subTreePtr->setRightChildPtr(rightPtr );
41: }
42: else
43: {
44: leftPtr = balancedAdd(leftPtr, newNodePtr);
45: subTreePtr->setLeftChildPtr(leftPtr);
46: } // end if
47:
48: return subTreePtr;
49: } // end if
50: } // end balancedAdd
52: template<class ItemType>
53: BinaryNode<ItemType>* BinaryNodeTree<ItemType>::copyTree(const BinaryNode<ItemType>* treePtr) const
54: {
55: BinaryNode<ItemType>* newTreePtr = nullptr;
56:
57: // Copy tree nodes during a preorder traversal
58: if (treePtr != nullptr)
59: {
60: // Copy node
61: newTreePtr = new BinaryNode<ItemType>(treePtr->getItem(), nullptr, nullptr);
62: newTreePtr->setLeftChildPtr(copyTree(treePtr->getLeftChildPtr()));
63: newTreePtr->setRightChildPtr(copyTree(treePtr->getRightChildPtr()));
64: } // end if
65:
66: return newTreePtr;
67: } // end copyTree
69: template<class ItemType>
70: void BinaryNodeTree<ItemType>::destroyTree(BinaryNode<ItemType>* subTreePtr)
71: {
72: if (subTreePtr != nullptr)
73: {
74: destroyTree(subTreePtr->getLeftChildPtr());
75: destroyTree(subTreePtr->getRightChildPtr());
76: delete subTreePtr;
77: } // end if
78: } // end destroyTree
80: //////////////////////////////////////////////////////////////
81: // Protected Tree Traversal Sub-Section
82: //////////////////////////////////////////////////////////////
84: template<class ItemType>
85: void BinaryNodeTree<ItemType>::inorder(void visit(ItemType&), BinaryNode<ItemType>* treePtr) const
86: {
87: if (treePtr != nullptr)
88: {
89: inorder(visit, treePtr->getLeftChildPtr());
90: ItemType theItem = treePtr->getItem();
91: visit(theItem);
92: inorder(visit, treePtr->getRightChildPtr());
93: } // end if
94: } // end inorder
96: //////////////////////////////////////////////////////////////
97: // PUBLIC METHODS BEGIN HERE
98: //////////////////////////////////////////////////////////////
100: //////////////////////////////////////////////////////////////
101: // Constructor and Destructor Section
102: //////////////////////////////////////////////////////////////
104: template<class ItemType>
105: BinaryNodeTree<ItemType>::BinaryNodeTree() : rootPtr(nullptr)
106: {
107: } // end default constructor
109: template<class ItemType>
110: BinaryNodeTree<ItemType>::BinaryNodeTree(const ItemType& rootItem)
111: {
112: rootPtr = new BinaryNode<ItemType>(rootItem, nullptr, nullptr);
113: } // end constructor
115: template<class ItemType>
116: BinaryNodeTree<ItemType>::BinaryNodeTree(const ItemType& rootItem,
117: const BinaryNodeTree<ItemType>* leftTreePtr,
118: const BinaryNodeTree<ItemType>* rightTreePtr)
119: {
120: rootPtr = new BinaryNode<ItemType>(rootItem, copyTree(leftTreePtr->rootPtr),
121: copyTree(rightTreePtr->rootPtr));
122: } // end constructor
124: template<class ItemType>
125: BinaryNodeTree<ItemType>::BinaryNodeTree(const BinaryNodeTree<ItemType>& treePtr)
126: {
127: rootPtr = copyTree(treePtr.rootPtr);
128: } // end copy constructor
130: template<class ItemType>
131: BinaryNodeTree<ItemType>::~BinaryNodeTree()
132: {
133: destroyTree(rootPtr);
134: } // end destructor
136: //////////////////////////////////////////////////////////////
137: // Public BinaryTreeInterface Methods Section
138: //////////////////////////////////////////////////////////////
140: template<class ItemType>
141: bool BinaryNodeTree<ItemType>::add(const ItemType& newData)
142: {
143: BinaryNode<ItemType>* newNodePtr = new BinaryNode<ItemType>(newData);
144: rootPtr = balancedAdd(rootPtr, newNodePtr);
145: return true;
146: } // end add
148: } // end contains
150: //////////////////////////////////////////////////////////////
151: // Public Traversals Section
152: //////////////////////////////////////////////////////////////
154: template<class ItemType>
155: void BinaryNodeTree<ItemType>::inorderTraverse(void visit(ItemType&)) const
156: {
157: inorder(visit, rootPtr);
158: } // end inorderTraverse