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 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();

};