insert a new node in a binary search tree

[mathon]

Hello,

im currently implementing a binary search tree means, that a greater
number than root will be added as right child and a less number as left
child. My insert function looks currently like this:

    template <class Item>
	void bag<Item>::insert(const Item& entry)
	// Header file used: bintree.h
	{
	    binary_tree_node<Item> *cursor;

	    if (root_ptr == NULL)
	    {   // Add the first node of the binary search tree:
		root_ptr = new binary_tree_node<Item>(entry);
		return;
	    }

	    else
	    {   // Move down the tree and add a new leaf:
			cursor = root_ptr;
			while(cursor != NULL)
			{
				if(cursor->data() > entry)
					cursor=cursor->right();
				else if (cursor->data() <= entry)
					cursor = cursor->left();
			}
		}
	}

So in the else-branch he should look for the right place of the entry
and then insert the new node. I tried it with a while loop and step
through the tree, but i do not know exactly if this is right
respectively how should i then insert the new node.
Has somebody here an idea...?

lg matti

 

[mathon]

something more to the implementation - if the number is higher it
should append as right child, if the number is less or equal it should
be appended as left child.

has anybody an idea if or respectively how i have to define that right,
regarding my imlementation of my function of the previous posting?

matti

 

[mathon]

I modified the function a little bit, the functions is_leaf checks if
the node is a leaf or has children.

template <class Item>
    void bag<Item>::insert(const Item& entry)
    // Header file used: bintree.h
    {
        binary_tree_node<Item> *cursor;

        if (root_ptr == NULL)
        {   // Add the first node of the binary search tree:
        root_ptr = new binary_tree_node<Item>(entry);
        return;
        }

        else
        {   // Move down the tree and add a new leaf:
            cursor = root_ptr;
            while(cursor != NULL)
            {
                if(entry <= cursor->data())
                {
                    if(cursor->is_leaf())
                    {
                        cursor->set_left(new
binary_tree_node<Item>(entry));
                    }
                    else
                        cursor=cursor->left();
                }
                else
                {
                    if(cursor->is_leaf())
                    {
                        cursor->set_right(new
binary_tree_node<Item>(entry));
                    }
                    else
                        cursor = cursor->right();
                }
            }
        }
    }

Is that the right way or are there still a error reasoning in it? :-/

matti

 

[mathon]

One more modification:

template <class Item>
	void bag<Item>::insert(const Item& entry)
	// Header file used: bintree.h
	{
	    binary_tree_node<Item> * current;
	    binary_tree_node<Item> * child;

	    if (root_ptr == NULL)
	    {   // Add the first node of the binary search tree:
			root_ptr = new binary_tree_node<Item>(entry);
			return;
	    }
	    else
	    {   // Move down the tree and add a new leaf:
			current = root_ptr;
			while(current)
			{
				if(current->data() <= entry)
				{
					child = current->right();
					if(!child)
					{
						current->set_right(new binary_tree_node<Item>(entry));
						return;
					}
				}
				else
				{
					child = current->left();
					if(!child)
					{
						current->set_left(new binary_tree_node<Item>(entry));
						return;
					}
				}
				current = child;
			}
		}
	}

 

[mathon]

i finally found the error...i manipulated a pointer in the wrong way..