Binary tree not inserting nodes correctly

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();    
                            }
                       }
                 }
            }
           
      }

It's doing exactly what you tell it to:

Code:

                                root_ptr->set_left(child_ptr);

Perhaps you want to utilise 'cursor' instead?

You must really be kicking yourself about now...

Not having gone through every step of your code, but I don't think you should be setting root_ptr->set_left/set_right when you are in the "not first node" setup. Rather, you should set cursor->set_left or set_right.

This will solve the problem of generating new nodes, but it won't fix the problem that you are only generating new nodes at the very end. I think you need to be able to add nodes in the middle too, since there's no guarantee that the new node isn't going to be in between two values in the tree.

--
Mats

Generating new nodes at the end is all I needed. Thanks

After replaced root_ptr->set_left(child_ptr) with cursor->set_left(child_ptr) and root_ptr->set_right(child_ptr) with cursor->set_right(child_ptr), I am able to generate
___________________root_ptr
___________________/______\
________________left1______right1
_______________/___\_______/___\
_____________left2__right2__left2__right2

However, when I tried left2->is_leaf() and right2->is_leaf() some of them return true, and some of them return false. They should all return true. When I created the child_ptr, the constructor that I have should set the left_field and right_field to NULL. I can't see what's causing this problem. Could anyone please help me out? Thanks in advance.

You haven't posted the code for the constructor, just the prototype.

--
Mats

Sorry here it is

Code:

binary_tree_node::binary_tree_node(const string& init_data, const unsigned int& init_index, binary_tree_node* init_left, binary_tree_node* init_right)
    {
         
         data_field = init_data; 
         index_field = init_index;
	 left_field = init_left; 
	 right_field = init_right;                  
                           
    }

I tried child_ptr = new binary_tree_node(entry, target, NULL, NULL); but it did not help. I still get left2->leaf() and right2->leaf() false. They are suppose to be true. I don't see where the problem is. Any help is more than welcome. Thanks in advance.