Imitating binary search trees with array

[Wuten]

I've been having logic issues with this code; for some reason whenever I reach a leaf on the tree, it skips ahead and the input doesn't come out correctly. I feel like it's something very simple I'm just overlooking, and I'm going to feel very stupid if that's the case... but I'm completely lost at this point.

#include <iostream>

using namespace std;


tree[100];


void insert(int n)
{
	int index = 1;
	if (tree[index] == -1)		//insert the value into the current index
	{
		tree[index] = n;
	}
	else if (tree[index] != -1)		//if index is already filled
	{
		if (n < tree[index])		//value is less than root value
		{
			while (tree[index] != -1)
				{
					index *= 2;
				}
			if (tree[index] == -1)
				tree[index] = n;
			else
			{
				
				tree[index] = n;
			}
		}
		else if (n > tree[index])		//value is greater than root value
		{
			while(tree[index] != -1)
				{
					index *= 2;
					index += 1;
				}
			if (tree[index] == -1)
				tree[index] = n;
			else
			{
				
				tree[index] = n;
			}
		}
	}
}

This is the input in the main function:

int main()
{

//-1 = NULL
for (int i = 0; i <= 100; i++)
		tree[i] = -1;

	insert(5);	
	insert(8);
	insert(3);	
	insert(1);
	insert(4);
	insert(9);
	insert(18);
	insert(20);
	insert(19);
	insert(2);

	cout << "Tree Output: [ ";
	for (int j= 0; j< 100; j++)
		cout << tree[j] << " ";
	cout << "]" << endl << endl;

return 0;
}

The output looks something like this:

Tree Output: [ -1 5 3 8 1 -1 -1 9 4 -1 -1 -1 -1 -1 -1 18 2 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 20 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 19 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ]

Press any key to continue . . .

The output is close, but the 4, 2 and 19 are off; the 4 should be in index 5, the 2 should be in index 9, and the 19 should be in index 62. Everything else is properly placed.

[o3hC5Di1]

Hi there,

Unfortunately I'm not immediately able to pinpoint the issue as I have never implemented a binary search tree myself. Nonetheless I want to point out one or two things in your code:

if (tree[index] == -1)		//insert the value into the current index
	{
		tree[index] = n;
	}
	else if (tree[index] != -1)	 //Just use regular else, intent is clearer
	{
		if (n < tree[index])		//value is less than root value
		{
			while (tree[index] != -1)
				{
					index *= 2;
				}
			if (tree[index] == -1)   //this if and else do exactly the same 
				tree[index] = n;
			else
				tree[index] = n;
		}
		else if (n > tree[index])		
		{
			while(tree[index] != -1)
				{
					index *= 2;
					index += 1;
				}
			if (tree[index] == -1)  //this if and else do exactly the same 
				tree[index] = n;
			else
				tree[index] = n;
		}
                //you have defined a case for n>, n<, but what if n==tree[index]?
	}

Now, I don't know if this is for an assignment or how advanced your c++ knowledge is, but if I were to implement one the least I would do is to create a Node-struct. I don't think I would use an array either, because at some point these lines index *= 2; are going to go out of the bounds of the array (causing a segfault), especially if your tree is unbalanced (or whatever the official term for that is).

As a quick mock up:

template <typename T>
struct node
{
    node* left_child;
    node* right_child;
    node* parent;
    T value;
};

template <typename T>
class binary_search_tree
{
    public:
        void insert(const T element)
        {
                insert_recursively(element, root)
        }

    private:
        node<T> root;

        void insert_recursively(const T& element, node* node_ptr)
        {
                if (node_ptr.value < element)
                {
                        insert_recursively(element, node_ptr->left_child);
                }
                else if (node_ptr.value > element)
                {
                        insert_recursively(element, node_ptr->right_child);
                }
                else
                {
                        node* n = new node();
                        n.value = element;
                        //make n's parent the node_ptr's parent
                        //make node_ptr's parent n
                }
        }
};

Again, this is just a quick mock-up, I haven't put much thought into it and it probably won't compile. I just wanted to make my point clear about using a node-struct and making inserting recursive.

Hopefully that helps a little, otherwise just say so and I'm sure one of the exerts on this forum will be happy to give you some better feedback.

All the best,
NwN