I have an assignment for my c++ class that is requiring an array implementation of a binary search tree. I have been given the main so it has to remain the same, meaning there can be no parameters in the functions unfortunately. I am having the most trouble with the pre-order and post-order functions.
I am lost! Any help would be greatly appreciated!
#include <iomanip>
#include <iostream>
using namespace std;
class BinarySearchTree
{
public:
int size; // size of the array
int* array; // array to hold elements
BinarySearchTree(int size) // constructor for size
{
int newSize = extendSize(size);
array = new int[newSize];
for (int x = 0; x < size; x++)
{
array[x] = NULL;
}
}
};
//****************************************************************************
// extendSize - function that extends the size of the array
//
// x - size value
//****************************************************************************
int BinarySearchTree::extendSize(int x)
{
int value = 0;
for (int y = 0; y < x + 1; y++)
{
value = (2 * value) + 2;
}
return value;
}
//****************************************************************************
// insertNode - function that inserts element into array
//
// x - element to be inserted into array
//****************************************************************************
void BinarySearchTree::insertNode(int x)
{
int index = 0;
while (true)
{
if (array[index] == NULL)
{
array[index] = x;
count++;
break;
}
else if (array[index] <= x)
{
index = (2 * index + 2);
count++;
}
else if (array[index] >= x)
{
index = (2 * index + 1);
count++;
}
}
}
//****************************************************************************
// display - function that displays the binary search tree elements
//****************************************************************************
void BinarySearchTree::display()
{
for (int i = 0; i < size; i++)
{
cout << i+1 << ": " << array[i] << endl;
}
cout << endl;
}
//****************************************************************************
// parent - function that finds the parent of an element
//
// x - element to find parent of
//****************************************************************************
void BinarySearchTree::parent(int x)
{
while (x != 0)
{
x = (x-1) / 2;
}
}
//****************************************************************************
// preOrder - function that displays the elements in pre order
//****************************************************************************
void BinarySearchTree::preOrder()
{
int i =0;
do
{
cout << array[i] << endl;
while ()
{
int left = 2*i+1;
cout << array[left] << endl;
}
while ()
{
int right = 2*i+2;
cout << array[right] << endl;
}
} while (array[i] != NULL);
cout << endl;
}
> meaning there can be no parameters in the functions unfortunately
just create another function, hidden from the client code, that takes whatever parameters you want.