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>
usingnamespace std;
tree[100];
void insert(int n)
{
int index = 1;
if (tree[index] == -1) //insert the value into the current index
{
tree[index] = n;
}
elseif (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;
}
}
elseif (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;
}
}
}
}
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.
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;
}
elseif (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;
}
elseif (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).
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);
}
elseif (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.