Convert the TreeArray C++ source code (SEE BELOW into a BinaryTree, using this T
ID: 3840217 • Letter: C
Question
Convert the TreeArray C++ source code (SEE BELOW into a BinaryTree, using this TreeNode definition:
class TreeNode<T>
T data
TreeNode<T> left
TreeNode<T> right
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)
Additional Specification: Implement a function to delete a selected node from the tree. Output the tree after the deletion to ensure the node has been deleted. Note: deleting the "root" node does not have to be a consideration of your algorithm.
#include <iostream>
#include "ConsoleColor.h"
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 << red << " -->insert: " << x << endl;
while (true)
{
if (array[currentIndex] == NULL)
{
array[currentIndex] = x;
cout << blue << "Inserted @ index: " << currentIndex << endl;
break;
}
else if (x < array[currentIndex])
{
currentIndex = (2 * currentIndex + 1);
cout << green << " <<< Left " << currentIndex << endl;
}
else
{
currentIndex = (2 * currentIndex + 2);
cout << yellow << " Right >>> " << currentIndex << endl;
}
}
}
void search(int x)
{
cout << red << "Search: " << x << endl;
int currentIndex = 0;
while (true)
{
if (array[currentIndex] == NULL)
{
cout << red << "Not Found" << endl;
break;
}
if (array[currentIndex] == x)
{
cout << blue << "Found at index: " << currentIndex << endl;
break;
}
else if (x < array[currentIndex])
{
cout << green << " <<< Left " << endl;
currentIndex = (2 * currentIndex + 1);
}
else
{
cout << yellow << " >>> 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 << endl;
cout << blue << "Inorder" << yellow << endl;
bst.inOrder(0);
cout << blue << "Preorder" << yellow << endl;
bst.preOrder(0);
cout << blue << "Postorder" << yellow << endl;
bst.postOrder(0);
cout << blue << " Search" << yellow << endl;
bst.search(65);
cout << " In memory" << endl;
bst.printArray();
}
Any help would be absolutely appreciated, even if the whole questionn doesn't get answered; I'd honestly prefer to have an answer with some pseudo-code and detailed instructions on how specific parts work together than a straight answer, especially since the last few times I've used this Q&A, I've gotten answers that aren't really correct.
Thanks for your time!!
Explanation / Answer
i make changes to the above program and re run it:
#include <iostream>
#include "ConsoleColor.h"
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 << red << " -->insert: " << x << endl;
while (true)
{
if (array[currentIndex] == NULL)
{
array[currentIndex] = x;
cout << blue << "Inserted @ index: " << currentIndex << endl;
break;
}
else if (x < array[currentIndex])
{
currentIndex = (2 * currentIndex + 1);
cout << green << " <<< Left " << currentIndex << endl;
}
else
{
currentIndex = (2 * currentIndex + 2);
cout << yellow << " Right >>> " << currentIndex << endl;
}
}
}
void search(int x)
{
cout << red << "Search: " << x << endl;
int currentIndex = 0;
while (true)
{
if (array[currentIndex] == NULL)
{
cout << red << "Not Found" << endl;
break;
}
if (array[currentIndex] == x)
{
cout << blue << "Found at index: " << currentIndex << endl;
break;
}
else if (x < array[currentIndex])
{
cout << green << " <<< Left " << endl;
currentIndex = (2 * currentIndex + 1);
}
else
{
cout << yellow << " >>> 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 << endl;
cout << blue << "Inorder" << yellow << endl;
bst.inOrder(0);
cout << blue << "Preorder" << yellow << endl;
bst.preOrder(0);
cout << blue << "Postorder" << yellow << endl;
bst.postOrder(0);
cout << blue << " Search" << yellow << endl;
bst.search(65);
cout << " In memory" << endl;
bst.printArray();
}