Binary tree wont go left!!!

This is a discussion on Binary tree wont go left!!! within the C++ Programming forums, part of the General Programming Boards category; Hello, I am new to programming and cant figure out this problem. The program works fine if i use int ...

  1. #1
    Registered User
    Join Date
    Nov 2009
    Posts
    1

    Binary tree wont go left!!!

    Hello,
    I am new to programming and cant figure out this problem. The program works fine if i use int numbers but breaks when i change to names of type string.
    the total code is at
    C++ pastebin - collaborative debugging tool
    but the place i am stuck at is
    Code:
    void addNode(string name, int weight)
    	{
    		treeNode *newNode = new treeNode(name, weight);			
    		if (root == 0)									
    		{
    			root = newNode;
    			return;
    		}
    		treeNode *temp = root;							
    		while(true)
    		{
    		if (temp->left != 0 && temp->name <= name)						
    				if (temp->left == 0)					
    				{
    					temp->left = newNode;
    					break;
    				}
    				else									// move to subtree
    					temp = temp->left;
    			else if (name < temp->name)					
    					if (temp->right == 0)					
    					{
    						temp->right = newNode;
    						break;
    					}
    					else									// move to subtree
    						temp = temp->right;
    				  else if(name > temp->name)
    						temp = temp->right;
    			//else if (name == temp->name)				
    				return;
    		}
    	}
    the code always goes to the right when I debug.
    any insight would be wonderfull
    thanks

  2. #2
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    Code:
    if (temp->left != 0 && temp->name <= name)						
    				if (temp->left == 0)					
    				{
    					temp->left = newNode;
    					break;
    				}
    				else									// move to subtree
    					temp = temp->left;
    			else if (name < temp->name)					
    					if (temp->right == 0)					
    					{
    						temp->right = newNode;
    						break;
    					}
    					else									// move to subtree
    						temp = temp->right;
    				  else if(name > temp->name)
    						temp = temp->right;
    			//else if (name == temp->name)				
    				return;
    		}
    I would add curly brackets around every if/else if/else block here to ensure it is doing what you think/want it to do. Its incredibly difficult to read and trace this manually. In addition, its good practice to always have these brackets around even 1 line if/whatever blocks of code.

    I havent looked at all of the code, but heres something probably isnt what you want
    Code:
    if (temp->left != 0 && temp->name <= name)						
    				if (temp->left == 0)
    The inner if statement checks that the left is null, but its guaranteed to not be null, because the outer if checked if it was != 0. I would look around in your code for other similar logic errors like this, in addition to adding braces around every block, even for 1 line blocks. For starters, at least.

  3. #3
    Registered User
    Join Date
    Mar 2009
    Posts
    48
    Code:
    if (temp->left != 0 && temp->name <= name)
    This will fail in the second entry itself.First time the root gets allocated, next time root's left is 0 , so going by your if condition it never enters the left if block, same is the case for inserting a node in the 'right' position of the root.

    Here's the pseudo code.
    Code:
       T*temp = root;
       while (node position not determind) {
           if (name <= temp-> name)
               if (node found at left)
                   set your temp to temp->left
               else  
                   postion found.Insert node and break 
          
          else if (name > temp-> name)
                if (node found at right)
                      set temp to temp->right
                  else
                      postion found.Insert node and break 
                 
       }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Delete all from a Binary Tree
    By Silvio in forum C Programming
    Replies: 5
    Last Post: 04-25-2009, 06:23 AM
  2. Binary tree not inserting nodes correctly
    By jk1998 in forum C++ Programming
    Replies: 7
    Last Post: 09-22-2007, 12:37 PM
  3. Replies: 0
    Last Post: 11-04-2006, 10:07 AM
  4. binary tree start
    By curlious in forum C++ Programming
    Replies: 6
    Last Post: 01-01-2004, 02:47 PM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21