Question: Convert the TreeArray C++ source code(posted below) into a BinaryTree, using this TreeNode definition: class TreeNode T data TreeNode left TreeNode right Since this TreeNode
Convert the TreeArray C++ source code(posted below) into a BinaryTree, using this TreeNode definition:
class TreeNode
T data
TreeNode
TreeNode
Since this TreeNode is a generic Template, use any data file we've used this quarter to store the data in the BinaryTree. To do this will likely require writing a compare function or operator.
Hint: Think LEFT if the index is calculate (2n+1) and RIGHT if index is (2n+2).
Source code:
#include
using namespace std;
class BinarySearchTree
{
int size;
int* array;
public:
BinarySearchTree(int s) : size(s)
{
size = reSize(size);
array = new int[size];
for (int x = 0; x < size; x++)
array[x] = NULL;
}
int reSize(int x)
{
int value = pow(2, x);
return value;
}
void insert(int x)
{
int currentIndex = 0;
cout << "insert: " << x;
while (true)
{
if (array[currentIndex] == NULL)
{
array[currentIndex] = x;
cout << " Inserted at index: " << currentIndex << endl;
break;
}
else if (x < array[currentIndex])
{
cout << " <<< Left ";
currentIndex = (2 * currentIndex + 1);
}
else
{
cout << " Right >>> ";
currentIndex = (2 * currentIndex + 2);
}
}
}
void search(int x)
{
cout << "Search: " << x << endl;
int currentIndex = 0;
while (true)
{
if (array[currentIndex] == NULL)
{
cout << "Not Found" << endl;
break;
}
if (array[currentIndex] == x)
{
cout << "Found at index: " << currentIndex << endl;
break;
}
else if (x < array[currentIndex])
{
cout << " <<< Left " << endl;
currentIndex = (2 * currentIndex + 1);
}
else
{
cout << " >>> Right " << endl;
currentIndex = (2 * currentIndex + 2);
}
}
}
void parent(int x)
{
while (x != 0)
{
x = (x - 1) / 2;
cout << "---|";
}
}
void inOrder(int currentIndex)
{
if (array[currentIndex] != NULL)
{
inOrder(2 * currentIndex + 1);
parent(currentIndex);
cout << array[currentIndex] << endl;
inOrder(2 * currentIndex + 2);
}
}
void preOrder(int currentIndex)
{
if (array[currentIndex] != NULL)
{
parent(currentIndex);
cout << array[currentIndex] << " " << endl;
preOrder(2 * currentIndex + 1);
preOrder(2 * currentIndex + 2);
}
}
void postOrder(int currentIndex)
{
if (array[currentIndex] != NULL)
{
postOrder(2 * currentIndex + 1);
postOrder(2 * currentIndex + 2);
parent(currentIndex);
cout << array[currentIndex] << " " << endl;
}
}
void printArray()
{
for (int i = 0; i < size; i++)
if (array[i])
cout << array[i] << ' ';
else
cout << '.';
cout << endl;
}
};
int main()
{
int array[] = { 42, 68, 35, 1, 70, 25, 79, 59, 63, 65 };
int size = sizeof(array) / sizeof(array[0]);
BinarySearchTree bst(size);
for (int i = 0; i < size; i++)
bst.insert(array[i]);
cout << "Inorder" << endl;
bst.inOrder(0);
cout << "Preorder" << endl;
bst.preOrder(0);
cout << "Postorder" << endl;
bst.postOrder(0);
cout << "Search" << endl;
bst.search(65);
cout << "In memory" << endl;
bst.printArray();
};
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help