Thread: Binary tree not inserting nodes correctly

  1. #1
    Registered User
    Join Date
    Apr 2007
    Posts
    42

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

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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...
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #4
    Registered User
    Join Date
    Apr 2007
    Posts
    42
    Generating new nodes at the end is all I needed. Thanks

  5. #5
    Registered User
    Join Date
    Apr 2007
    Posts
    42
    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.

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    You haven't posted the code for the constructor, just the prototype.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    Registered User
    Join Date
    Apr 2007
    Posts
    42
    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;                  
                               
        }

  8. #8
    Registered User
    Join Date
    Apr 2007
    Posts
    42
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. arrays vs lists? And containers in general!
    By clegs in forum C++ Programming
    Replies: 22
    Last Post: 12-03-2007, 02:02 PM
  2. Binary Tree
    By Ideswa in forum C Programming
    Replies: 12
    Last Post: 10-25-2007, 12:24 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. binary tree node structure
    By Kirsten in forum C Programming
    Replies: 2
    Last Post: 04-26-2002, 08:02 PM
  5. read records fron file into a binary tree
    By Kirsten in forum C Programming
    Replies: 1
    Last Post: 04-23-2002, 02:48 PM