-
Notifications
You must be signed in to change notification settings - Fork 0
/
Tree.cpp
192 lines (160 loc) · 4.4 KB
/
Tree.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
/** @file Tree.cpp */
#include "Tree.h"
#include "Node.h"
#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>
using namespace std;
//////////////////////////////////////////////////////////////
// Constructor and Destructor Section
//////////////////////////////////////////////////////////////
Tree::Tree() : theWord(" "), rootPtr(nullptr)
{
} //end default constructor
Tree::Tree(const string& str)
{
rootPtr = nullptr;
theWord = str;
convertStrToTree();
} //end constructor
Tree::~Tree()
{
destroyTree(rootPtr);
rootPtr = nullptr;
} //end destructor
//////////////////////////////////////////////////////////////
// Protected Utility Methods Section
//////////////////////////////////////////////////////////////
/*
Recursively searches for target value in the tree by using
a preorder traversal.
*/
bool Tree::containsHelper(Node* subTreePtr, const char& target) const
{
if (subTreePtr == nullptr) // base case
return false;
if (subTreePtr->getItem() == target) // found it
{
return true;
}
else
{
bool isFound = containsHelper(subTreePtr->getLeftChildPtr(), target);
if (!isFound) // no need to search right subTree if already found
{
isFound = containsHelper(subTreePtr->getRightChildPtr(), target);
} // end if
return isFound;
} // end if
} // end containsHelper
//inserts a new item into the binary search tree to which subTreePtr point
Node* Tree::addHelper(Node* subTreePtr, Node* newNodePtr)
{
if (subTreePtr == nullptr)
return newNodePtr;
else if (subTreePtr->getItem() > newNodePtr->getItem())
{
//insert into the left subtree
Node* tempPtr = addHelper(subTreePtr->getLeftChildPtr(), newNodePtr);
subTreePtr->setLeftChildPtr(tempPtr);
}
else
{
//insert into the right subtree
Node* tempPtr = addHelper(subTreePtr->getRightChildPtr(), newNodePtr);
subTreePtr->setRightChildPtr(tempPtr);
}
return subTreePtr;
} //end addHelper
// swaps chars passed in by reference
void Tree::swapper (char &x, char &y)
{
char temp;
temp = x;
x = y;
y = temp;
} //end swapper
//sorts string using Bubble sort
void Tree::stringSort(string &str)
{
bool swapped; //sets swapped true if any swap occurs
do {
swapped = false;
for (int i=0; i < str.length() - 1; i++)
{
if (str[i] > str[i+1])
{
swapper(str[i], str[i+1]);
swapped = true;
}
}
} while (swapped);
} //end stringSort
int Tree::findMidpoint(int length)
{
int mid;
if (length % 2 == 0) //even
mid = length/2;
else //odd
mid = 1 + (length-1)/2;
return mid;
} //end findMidpoint
/*
add every char of the Secret Word to the tree in order to have a Balanced Binary Search Tree.
By sorting the string then adding its midpoint to the tree each time
*/
void Tree::convertStrToTree()
{
int midpoint;
char midCharacter;
string str = theWord;
if (str != " ") //valid word
{
stringSort(str); //sorts string
while (str.length() != 0) //base case
{
midpoint = findMidpoint(str.length()); //midpoint of string
midCharacter = str[midpoint-1]; //character at midpoint of string
add(midCharacter);
str.erase(midpoint-1, 1); //removes the char from the string
}
}
else
cout << "The Word wasn't successfully converted to a Tree. \n";
} //end convertStrToTree
void Tree::destroyTree(Node* subTreePtr)
{
if (subTreePtr != nullptr)
{
destroyTree(subTreePtr->getLeftChildPtr());
destroyTree(subTreePtr->getRightChildPtr());
delete subTreePtr;
} // end if
} // end destroyTree
//////////////////////////////////////////////////////////////
// PUBLIC METHODS BEGIN HERE
//////////////////////////////////////////////////////////////
void Tree::add(const char& newData)
{
Node* newNodePtr = new Node(newData);
rootPtr = addHelper(rootPtr, newNodePtr);
} //end add
//use of containsHelper for a recursive search
bool Tree::contains(const char& anEntry) const
{
return containsHelper(rootPtr, anEntry);
} //end contains
//makes a new tree with the word
void Tree::setWord(const string& str)
{
destroyTree(rootPtr);
rootPtr = nullptr;
theWord = str;
convertStrToTree();
} //end setWord
string Tree::getWord() const
{
return theWord;
} //end getWord
//end Tree.cpp