I am writing a insert function that will insert nodes into the binary tree according to their index. For example, if the tree is NULL, it will insert into the root_ptr, if the index is less than the root_ptr, it will move to the left node, if the index is greater, it will move to the right node. However, my insert function will only insert a root_ptr, a left children and a right chirldren. I can't see what's wrong with my function. Could anyone please help me out? Thanks in advance.
_______________root_ptr
______________/_______\
____________left1_____right1
___________/___\_____/____\
_________left__right__left___right
My insert function will only generate upto left1 and right1.
Code:
class binary_tree_node
{
public:
// CONSTRUCTOR
binary_tree_node(const std::string& init_data = std::string( ), const unsigned int& init_index = 0, binary_tree_node* init_left = NULL, binary_tree_node* init_right = NULL);
// MODIFICATION MEMBER FUNCTIONS
std::string& data( ) { return data_field; }
unsigned int& index() { return index_field; }
binary_tree_node* left( ) { return left_field; }
binary_tree_node* right( ) { return right_field; }
void set_data(const std::string& new_data) { data_field = new_data; }
void set_index(const unsigned int& new_index) { index_field = new_index;}
void set_left(binary_tree_node* new_left) { left_field = new_left; }
void set_right(binary_tree_node* new_right) { right_field = new_right; }
// CONST MEMBER FUNCTIONS
const std::string& data( ) const { return data_field; }
const unsigned int& index() const {return index_field; }
const binary_tree_node* left( ) const { return left_field; }
const binary_tree_node* right( ) const { return right_field; }
bool is_leaf( ) const
{ return (left_field == NULL) && (right_field == NULL); }
private:
std::string data_field;
unsigned int index_field;
binary_tree_node *left_field;
binary_tree_node *right_field;
};
void insert(const string& entry, const unsigned int& target)
{
binary_tree_node *cursor;
binary_tree_node *child_ptr;
if (root_ptr == NULL)
{ // Add the first node of the binary search tree:
root_ptr = new binary_tree_node(entry, target);
return;
}
else
{ // Move down the tree and add a new leaf:
cursor = root_ptr;
bool done = false;
while(!done)
{
if(target <= cursor->index())
{
if(cursor->left() == NULL)
{
child_ptr = new binary_tree_node(entry, target);
root_ptr->set_left(child_ptr);
done = true;
}
else
{
cursor = cursor->left();
}
}
else
{
if(cursor->right() == NULL)
{
child_ptr = new binary_tree_node(entry, target);
root_ptr->set_right(child_ptr);
done = true;
}
else
{
cursor = cursor->right();
}
}
}
}
}