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 online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,515
    Blog Entries
    7
    Rep Power
    20

    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
    cenosillicaphobia: the fear for an empty beer glass

  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 online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,515
    Blog Entries
    7
    Rep Power
    20

    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
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

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