Binary Search Tree In Basic Array Format

Question

I am trying to read in a bunch of integers into an array, then use a function that takes that array as an input element by element and creates a binary search tree. the bst is in the form of an array and will have smaller elements at the (2n+1) array spot and larger elements at the 2n+2 array spot. I think I have most of it working but for some reason, the loop in my function wont work. Any solutions?? I think I am simply just not seeing something.

Code::

#include <iostream>
#include <fstream>
using namespace std;


void sortArray(int arr[], int size)
{   
    int bst[50];
    bst[0] = arr[0];

    for(int b = 1; b < size - 1; b++)
    {
        int c = 0;
        do{
            if(arr[b] < bst[c])
                {
                    c = ((2 * c) + 1);
                }
            if(arr[b] > bst[c])
                {
                    c = ((2 * c) + 2);
                }
        }while(bst[c] != 0);
        bst[c] = arr[b];
    }

    for(int p = 0; p < 25; p++){
        cout << bst[p];
    }   
}    



int main(int argc, char** argv) {
int myArray[50];
int i = 0;

ifstream myfile ("tree_nodes.txt");
if (myfile.is_open())
{
    while (! myfile.eof() )
    {
        myfile >> myArray[i];
        i++;
    }
    myfile.close();
}
else cout << "Unable to open file";

for(int p = 0; p < (i); p++){
        cout << myArray[p];
    }

sortArray(myArray,i);


return 0;
}

Captain Giraffe · Accepted Answer · 2014-12-17 07:07:09Z

1

There are quite a few problems with your code.

You are creating an unbalanced BST, potentially requiring 2^N space to store the tree. I.e to "sort" 32 elements you might need 4GB of memory. Your 50 element array can only reliably sort 4 integers.
You are relying on the integer 0 to indicate "no value". 0 can't be a part of the initial data.
int bst[50] is not initialized. The contents are unknown, not zero. int bst[50] = {};, see e.g. http://www.cplusplus.com/doc/tutorial/arrays/
Your method can't handle two integers with the same value.
I'm under the impression you expect the last for-statment to output the integers sorted. This is also not the case.

In short: This approach won't work. Creating a BST is tricky. I would suggest you study an already existing balanced BST implementation.

To solve 5. you can use something like:

void visitAndPrintOddBST(int bst[], int index = 0){
    if (bst[index] == 0 ) return;
    visitAndPrintOddBST(bst, index*2 + 1);
    std::cout << bst[index] << std::endl;
    visitAndPrintOddBST(bst, index*2 + 2);
}

You need some sort of stack to keep track of the movement in the tree. In this approach this is the recursive call stack. Also the size of the array is unspecified and is quite likely to go out of bounds. This is not good code. Only use it for this experiment.

edited Dec 17, 2014 at 7:07

answered Dec 17, 2014 at 6:45

Captain Giraffe

14.8k7 gold badges42 silver badges69 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Not_NSA_I_Swear Over a year ago

Exactly. 1)I want an unbalanced BST. I dont care about memory usage for sorting. 2) I understand 0 can't be part of the initial data and I am assuming 0 means empty. 3) Can I do int bst[50] = 0;? 4) I won't have integers of the same value. 5) sorry that was code just to see if the integers from the file would be correctly put into the initial array. I will take it out later

Captain Giraffe Over a year ago

@Not_NSA_I_Swear 1) Means you can only reliably sort 5 integers in a 50 element array, are you ok with that? 3) See cplusplus.com/doc/tutorial/arrays . 5) I'll edit in a suggestion in my answer.

Collectives™ on Stack Overflow

Binary Search Tree In Basic Array Format

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related