Imitating binary search trees with array

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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.
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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
Last edited on
Topic archived. No new replies allowed.