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
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
|
#pragma once
#include <fstream>
#include <string>
#include "BinaryNode.h"
#include "LinkedQueue.h"
template <class T>
class MyBinarySearchTree
{
private:
BinaryNode<T>* _root;//A pointer to a BinaryNode<T> that is the root of our tree.
int _size;//Track of the size of our tree.
BinaryNode<T>* _insert(BinaryNode<T>* cur, T data);//Methord to add to tree.
void _preorder(std::string* ord, BinaryNode<T>* cur);//Pre order treversal methord.
void _inorder(std::string* ord, BinaryNode<T>* cur);//In order treversal methord.
void _postorder(std::string* ord, BinaryNode<T>* cur);//Post order treversal methord.
void _levelorder(std::string* ord, BinaryNode<T>* cur);//Level order treversal methord.
bool _binarySearch(BinaryNode<T>* cur, T data);//Search methord.
void _deleteTree(BinaryNode<T>* cur);//Delete methord that the deconstructor calls.
public:
MyBinarySearchTree();//Default Constructor
MyBinarySearchTree(std::string fName);//Constructor
MyBinarySearchTree(const MyBinarySearchTree<T>& obj);//Copy constructor
~MyBinarySearchTree();//Deconstructor
void insert(T data);//Adding helper methord.
std::string preorder();//Treversal helper methord.
std::string inorder();//Treversal helper methord.
std::string postorder();//Treversal helper methord.
std::string levelorder();//Treversal helper methord.
bool contains(T data);//Search helper methord.
int size();//Methord returning the size.
bool is_empty();//Methord to check if the tree is empty.
};
template <class T>
MyBinarySearchTree<T>::MyBinarySearchTree()//Default Constructor
{
_root=nullptr;//Because no nodes in the tree.
_size=0;//No nodes in the tree.
}
template <class T>
MyBinarySearchTree<T>::MyBinarySearchTree(std::string fName)//Constructor
{
std::ifstream nameFile;//Stream class to read from nameFile
nameFile.open(fName);//Open the file.
std::string peoplenames;//Defining string variable peoplenames.
while (getline(nameFile, peoplenames))//Read through the file.
{
insert(peoplenames);//Add peoplenames to the tree.
}
nameFile.close();//Close file.
}
template <class T>
MyBinarySearchTree<T>::MyBinarySearchTree(const MyBinarySearchTree<T>& obj)//Copy constructor
{
LinkedQueue<BinaryNode<T>*>* q = new LinkedQueue<BinaryNode<T>*>();//Creating a new linked queue holding pointers to nodes.
BinaryNode<T>* cn;//Node pointer variable.
MyBinarySearchTree<T>* cur=obj._root;//Copying the root node pointer to the tree pointer object cur.
q->enqueue(cur);//Enqueue the root.
while (!q->is_empty())//While the queue is not empty.
{
cn = q->dequeue();//Dequeue a node pointer object which cn points to now.
_insert(cn);//add the node pointer object to the tree.
if (cn->getLeft() != nullptr)
{
q->enqueue(cn->getLeft());//Enqueue the left child (if it exists).
}
if (cn->getRight() != nullptr)
{
q->enqueue(cn->getRight());//Enqueue the right child (if it exists).
}
}
delete q;//Delete the queue.
//Ripping off the idea used for a level order traversal, but instead of adding the contents to a string, just inserting the things into the tree.
}
template <class T>
MyBinarySearchTree<T>::~MyBinarySearchTree()//Deconstructor
{
_deleteTree(_root);//Calling the delete mothord.
}
template <class T>
void MyBinarySearchTree<T>::insert(T data)//Adding helper methord.
{
_root = _insert(_root, data);//calling the actual adding method with a node pointer variable and data transferred to the current method as parameters and setting it equal to the root.
_size++;//incresing the size of the tree.
}
template <class T>
BinaryNode<T>* MyBinarySearchTree<T>::_insert(BinaryNode<T>* cur, T data)//Methord to add to tree.
{
// Base case
if (cur == nullptr)// The pointer tranfered points to nothing.
{
return new BinaryNode<T>(data);//Create a new node with the data passed.
}
// Insert Left
if (data < cur->getData())//If the poiter's data is greater than the data passed.
{
cur->setLeft(_insert(cur->getLeft(), data));//Call the add methord again to create a node to the left of the current node holding the data tranfred.
}
// Insert Right
else
{
cur->setRight(_insert(cur->getRight(), data));//Call the add methord again to create a node to the right of the current node holding the data tranfred.
}
return cur;//Return root of the tree.
}
template <class T>
std::string MyBinarySearchTree<T>::preorder()//Treversal helper methord.
{
std::string order;//String variable
_preorder(&order,_root);//Call the actual treversal.
return order;//Returning string variable.
}
template <class T>
void MyBinarySearchTree<T>::_preorder(std::string* ord, BinaryNode<T>* cur)
{
if (cur != nullptr)//If the tree is not empty
{
*ord = *ord + cur->getData() + ", ";//Visit the root node of the tree (print?).
_preorder(ord,cur->getLeft());//Do a preorder traversal on the left subtree
_preorder(ord,cur->getRight());//Do a preorder traversal on the right subtree
}
}
template <class T>
std::string MyBinarySearchTree<T>::inorder()//Treversal helper methord.
{
std::string order;//String variable
_inorder(&order, _root);//Call the actual treversal.
return order;//Returning string variable.
}
template <class T>
void MyBinarySearchTree<T>::_inorder(std::string* ord, BinaryNode<T>* cur)
{
if (cur != nullptr)//If the tree is not empty
{
_inorder(ord, cur->getLeft());//Do a inorder traverrsal on the left subtree
*ord = *ord + cur->getData() + ", ";//Visit the root node of the tree (print?)
_inorder(ord, cur->getRight());//Do a inordr traverrsal on the right subtree
}
}
template <class T>
std::string MyBinarySearchTree<T>::postorder()//Treversal helper methord.
{
std::string order;//String variable
_postorder(&order, _root);//Call the actual treversal.
return order;//Returning string variable.
}
template<class T>
void MyBinarySearchTree<T>::_postorder(std::string* ord, BinaryNode<T>* cur)
{
if (cur != nullptr)//If the tree is not empty
{
_postorder(ord, cur->getLeft());//Do a postorder traverrsal on the left subtree
_postorder(ord, cur->getRight());// Do a inordr traverrsal on the right subtree
*ord = *ord + cur->getData() + ", ";//Visit the root node of the tree (print?)
}
}
template <class T>
std::string MyBinarySearchTree<T>::levelorder()//Treversal helper methord.
{
std::string order;//String variable
_levelorder(&order, _root);//Call the actual treversal.
return order;//Returning string variable.
}
template <class T>
void MyBinarySearchTree<T>::_levelorder(std::string* ord, BinaryNode<T>* cur)
{
LinkedQueue<BinaryNode<T>*>* q = new LinkedQueue<BinaryNode<T>*>();//Creating a new linked queue holding pointers to nodes.
BinaryNode<T>* cn;//Node pointer variable.
q->enqueue(cur);//Enqueue the cur node pointer passed.
while (!q->is_empty())//While the queue is not empty.
{
cn = q->dequeue();//Dequeue a node pointer object which cn points to now.
*ord = *ord + cn->getData() + ", ";//Adding the contents to a string.
if (cn->getLeft() != nullptr)
{
q->enqueue(cn->getLeft());//Enqueue the left child (if it exists).
}
if (cn->getRight() != nullptr)
{
q->enqueue(cn->getRight());//Enqueue the right child (if it exists).
}
}
delete q;//Delete the queue.
}
template <class T>
bool MyBinarySearchTree<T>::contains(T data)//Search helper methord.
{
return _binarySearch(_root, data);//Return the status of the search.
}
template <class T>
bool MyBinarySearchTree<T>::_binarySearch(BinaryNode<T>* cur, T data)
{
if (cur == nullptr)//If the passes node pointer points to nothing
{
return false;//Return not found.
}
if (data == cur->getData())//If the passes node pointer points to the data passes
{
return true;//Return found.
}
if (data < cur->getData())//If the data passes is less than the node pointer's data
{
return _binarySearch(cur->getLeft(), data);//Do a binary search on the left.
}
else
{
return _binarySearch(cur->getRight(), data);//Do a binary search on the right.
}
}
|
