insert a new node in a binary search tree

Discussion in 'C++' started by mathon@gmx.at, Nov 22, 2006.

  1. Guest

    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:

    Code:
        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
     
    , Nov 22, 2006
    #1
    1. Advertising

  2. Guest

    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
     
    , Nov 22, 2006
    #2
    1. Advertising

  3. Guest

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

    Code:
    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
     
    , Nov 22, 2006
    #3
  4. Guest

    One more modification:

    Code:
    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;
    			}
    		}
    	}
    
     
    , Nov 22, 2006
    #4
  5. Guest

    i finally found the error...i manipulated a pointer in the wrong way..:)
     
    , Nov 22, 2006
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    0
    Views:
    1,620
  2. John Harrison

    Re: binary search tree insert()

    John Harrison, Jul 28, 2003, in forum: C++
    Replies:
    0
    Views:
    512
    John Harrison
    Jul 28, 2003
  3. Peter Mueller
    Replies:
    6
    Views:
    4,665
    Stefan Ram
    Jan 13, 2008
  4. yogi_bear_79
    Replies:
    1
    Views:
    735
  5. Bogdan

    Binary tree search vs Binary search

    Bogdan, Oct 18, 2010, in forum: C Programming
    Replies:
    22
    Views:
    3,190
    Michael Angelo Ravera
    Oct 21, 2010
Loading...

Share This Page