binary search tree array implementation PLEASE

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

int count = 0; // count for tree

int extendSize(int);
void insertNode(int);
void display();
void parent(int);
void preOrder();
void postOrder();

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;
}

int main ()
{
BinarySearchTree tree(13);

cout << "Binary Search Tree\n\n";
cout << "Inserting nodes.\n\n";

tree.insertNode(70);
tree.insertNode(50);
tree.insertNode(100);
tree.insertNode(30);
tree.insertNode(60);
tree.insertNode(80);
tree.insertNode(110);
tree.insertNode(20);
tree.insertNode(68);
tree.insertNode(90);
tree.insertNode(120);
tree.insertNode(25);
tree.insertNode(62);

cout << "Building BST is completed.\n\n";
cout << "Values of the Binary Search tree.\n\n";
tree.display();

// Pre-Order Traversal
cout << "Pre-Order Traversal of the BST :\n\n";
tree.preOrder();

// Post-Order Traversal .
cout << "Post-Order Traversal of the BST :\n\n";
tree.postOrder();

}



Here's a sample of the output (without the preorder postorder):




Binary Search Tree By Carly Fordyce

Inserting nodes.

Building BST is completed.

Values of the Binary Search tree.

1: 70
2: 50
3: 100
4: 30
5: 60
6: 80
7: 110
8: 20
9: 0
10: 0
11: 68
12: 0
13: 90
14: 0
15: 120
16: 0
17: 25
18: 0
19: 0
20: 0
21: 0
22: 62
23: 0
24: 0
25: 0
26: 0
27: 0
28: 0
29: 0
30: 0
31: 0
> 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.
Topic archived. No new replies allowed.