Original Post
I'm trying to wrap my head around this problem conceptually, psuedo code would help the best. Right now, I'm given the task to construct a Binary Search Tree without the use of nodes or a linked list (:[[[) and i'm told just to use a dynamically allocated array. While I get the basic principal of it, the only way I can solve the problem is on a case by case basis. As in, give me the list, I will put the root in index 0, the children in 1 and 2 and so on. How can this be done without the use of the linked list? Apart from me thinking that it's just a horrible idea anyway and i'm reinventing a square wheel (who does array based BSTs?!) I just am totally lost on how to approach -Insertion -Removal -Searching My code so far: *Note: excuse the random LOLZ comments...I get bored!
//.h
//BinaryTree.cpp - Interface of the BinaryTree class
//Kesh Iyer
//CS 240
//Professor Williams
#include <iostream>
#include <string>
using namespace std;
#define DEFAULT 15
#ifndef BINARYTREE_H
#define BINARYTREE_H
typedef int Element;
typedef Element *Elements;
class binaryTree {
public:
//Default constructor
binaryTree();
//Copy constructor
binaryTree(const binaryTree & oldTree);
//Destructor
~binaryTree();
//Overloaded Assignment Operator
const binaryTree & operator=(const binaryTree & oldTree);
//Mutators
//*******************************************************************
//*****Insert - Inserts a string (str) at a given index (index) *****
//*******************************************************************
void insert(Element key);
//*******************************************************************
//*****Remove - Removes a string at a given index (index) ***********
//*******************************************************************
void remove(Element key);
//Accessors
//*******************************************************************
//*****Find - Returns a key at a given index (index) ****************
//*******************************************************************
int find (Element key);
//*******************************************************************
//*****printKey- Prints the result of the tree **********************
//*******************************************************************
void printKey();
//*******************************************************************
//*****printStr - Prints the strings in the tree in order ***********
//*******************************************************************
void printStr();
void display(ostream & out) const;
private:
Elements binaryElements;
int capacity;
int size;
};
ostream & operator<< (ostream & out, const binaryTree binarytree);
#endif
//.cpp
//BinaryTree.cpp - Implementation of the BinaryTree class
#include <iostream>
#include <new>
using namespace std;
#include "binaryTree.h"
//***Requirements for a Dynamic Array:
//Default constructor
binaryTree::binaryTree() {
binaryElements = new Element[DEFAULT];
capacity = DEFAULT;
size = 0;
}
//Copy constructor
binaryTree::binaryTree(const binaryTree & oldTree)
: capacity(oldTree.capacity), size(oldTree.size)
{
//New array:
//int binaryElements[DEFAULT];
if(binaryElements != 0)
{
for (int i = 0; i < size; i++)
binaryElements = oldTree.binaryElements;
}
else {
cout<<"No memory to allocate storage for new tree!";
exit(1);
}
}
//Destructor
binaryTree::~binaryTree()
{
delete [] binaryElements;
}
//Overloaded Assignment Operator
const binaryTree & binaryTree::operator=(const binaryTree & oldTree)
{
if (this != &oldTree)
{
if (capacity != oldTree.capacity)
{
delete[] binaryElements;
capacity = oldTree.capacity;
//string binaryElements[capacity];
if (binaryElements == 0)
{
cerr<< "Insufficient Memory";
exit(1);
}
}
size = oldTree.size;
for (int i = 0; i < capacity; i++)
binaryElements = oldTree.binaryElements;
}
return *this;
}
//Insert
void binaryTree::insert(Element key)
{
if (size == 0) { //Level 1
binaryElements[0] = key;
size++;
return;
}
if (size == capacity) {
binaryElements = new Element[capacity];
}
else {
for (int i = 0; i < capacity; i++) {
if (key < binaryElements && binaryElements[i*2+1] == 0) {
binaryElements[i*2+1] = key;
cout<<"Added left node into: "<<i<<"th spot"<<endl;
size++;
return;
}
if (key > binaryElements && binaryElements[i*2+2] == 0) {
binaryElements[i*2+2] = key;
cout<<"Added right node into: "<<i<<"th spot"<<endl;
size++;
return;
}
}
}
}
//Delete
void binaryTree::delete(Element key) {
//Find
int binaryTree::find(Element key) {
bool found = false;
int first = 0, loc;
int last = capacity-1;
while (first <= last && !found) {
loc = (first+last)/2;
if (key < binaryElements[loc])
last = loc-1;
else if (key > binaryElements[loc])
first = loc+1;
else {
found = true;
cout<<"ITEM WAS FOUND LOLZ :"<<binaryElements[loc];
}
}
if (found == false) {
cout<<"Item not found..."<<endl;
exit(1);
}
return binaryElements[loc];
}
void binaryTree::display(ostream & out) const
{
for (int i =0; i < capacity; i++) {
out<<binaryElements;
}
}
