Results 1 to 5 of 5
  1. #1
    Get_tanked is offline Member
    Join Date
    Jan 2011
    Posts
    24
    Rep Power
    0

    Default HELP!! Binary trees

    I have to write code for a collection of values using a binary tree, one of the methods is a belongs method to see if the value the user inputs is in the collection. It returns true if the value is in the collection and false if its not. I wrote a main method to test it but every time I run it I get false even if the values in the collection. To me the code I wrote seems like it should work, but obviously that is not the case, so I decided to post it here to see if I could get some help on this. I also need help on a print method for printing the values in the binary tree, but Ill just take it one method at a time for now :D

    Thanks

    Java Code:
    public class Intcoll6 
    {
    	   private btNode c;
    	   private int how_many;
    
    	   public Intcoll6()//default constructor
    	   {
    		  c = null;
    	      how_many = 0;
    	   }
    
    	   public Intcoll6(int i)// alt constructor
    	   {
    		  c = null;
    	      how_many = 0;
    	   }
    
    	   public boolean belongs(int i)// This is where I am having trouble should return true if the values in the binary tree
    	   {
    		   btNode p = c;
    		   while((p != null) && (p.info != i))
    		   {
    			   if(i < p.info)			  
    			   {
    				   p = p.lt;
    			   }
    			   else
    			   {
    				   p = p.rt;
    			   }
    		   }
    		   return (p != null);
    	   }
    
    	   public void insert(int i)// inserts a value into the binary tree
    	   {
    		   btNode p = c, q = null;
    		   while((p != null) && (p.info != i))
    		   {
    			   q = p;
    			   if(i < p.info)
    			   {
    				   p = p.lt;
    			   }
    			   else
    			   {
    				   p = p.rt;
    			   }
    			   
    		   }
    		   
    		   if(p == null)
    		   {
    			   how_many++;
    			   p = new btNode();
    			   p.info = i;
    			   
    			   if(q != null)
    			   {
    				   if(i < q.info)
    				   {
    					   q.lt = p;
    				   }
    				   else
    				   {
    					   q.rt = p;
    				   }
    			   }
    		   }
    		   else
    		   {
    			   c = p;
    		   }
    			 
    	   }
    
    	   public int get_howmany()//counts the amount of values in the collection
    	   {
    	      return how_many;
    	   }
    
    	   public void print(btNode p)//prints out the collection, not sure how to do this yet, any help would be appreciated :)
    	   {
    			
    	   }
    	   
    	   
    	   private class btNode
    	   {
    		   private int info;
    		   private btNode lt;
    		   private btNode rt;
    		   
    		   public btNode()
    		   {
    				info = 0;
    				lt = null;
    				rt = null;
    		   }  
    	   }
    }
    I dont know if you need this, but its the main method I wrote


    Java Code:
    import java.util.Scanner;
    
    public class Intcoll6testclient
    {
    	public static final int SENTINEL = 0;
    	
    	public static void main(String[] args)
    	{
    		 int value;
    		 int val2;
    		 Scanner keyboard=new Scanner(System.in);
    	     Intcoll6 P = new Intcoll6();
    	     
    	     System.out.println("Enter an integer to be inserted or 0 to quit:"); 
    	     value=keyboard.nextInt();
    	     
    	     while(value != SENTINEL)
    	     {
    	    	 P.insert(value);
    	    	 
    	    	 System.out.println("Enter next integer to be inserted or 0 to quit:");
    	    	 value=keyboard.nextInt();
    	     }
    	     
    	     System.out.println("Type a value to see if it belongs in the collection: ");
    	     val2 = keyboard.nextInt();
    	     System.out.println("The Method returned: " + P.belongs(val2));
    
    	}
    }

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,190
    Blog Entries
    7
    Rep Power
    24

    Default

    Check your very last else-statement in your insert( ... ) method; why are your changing the root (c) of your tree when a value is already present in the tree?

    kind regards,

    Jos
    The only person who got everything done by Friday was Robinson Crusoe.

  3. #3
    Get_tanked is offline Member
    Join Date
    Jan 2011
    Posts
    24
    Rep Power
    0

    Default

    The reason why I did that is so that c would get all of p's attributes. I tried to remove the else statement, but the belongs method still isnt working right, any more suggestions?

    thanks

  4. #4
    Get_tanked is offline Member
    Join Date
    Jan 2011
    Posts
    24
    Rep Power
    0

    Default

    Never mind I figured out what I was doing wrong.

    Thanks for the help

  5. #5
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,190
    Blog Entries
    7
    Rep Power
    24

    Default

    Quote Originally Posted by Get_tanked View Post
    The reason why I did that is so that c would get all of p's attributes. I tried to remove the else statement, but the belongs method still isnt working right, any more suggestions?

    thanks
    Variable c is the root of your tree, you can't set it to any arbitrary node. About more suggestions: why don't you use a TreeSet? It is implemented as a red-black tree which is exactly what you want. Or do you have to implement your own tree?

    kind regars,

    Jos
    The only person who got everything done by Friday was Robinson Crusoe.

Similar Threads

  1. Red/Black Trees
    By f1gh in forum New To Java
    Replies: 4
    Last Post: 12-12-2010, 03:30 AM
  2. Binary trees
    By girgishf in forum Advanced Java
    Replies: 15
    Last Post: 11-20-2010, 05:29 PM
  3. Splay Trees
    By Growler in forum New To Java
    Replies: 0
    Last Post: 11-02-2010, 03:10 PM
  4. Need help with Trees...(8-puzzle)
    By ventrue in forum New To Java
    Replies: 2
    Last Post: 03-24-2009, 12:04 AM
  5. Tutorial on Binary Search Trees
    By JordashTalon in forum New To Java
    Replies: 3
    Last Post: 03-18-2009, 04:51 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •