Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 14 of 14

Thread: Binary Trees:

  1. #1
    Member
    Join Date
    Apr 2014
    Location
    Germany
    Posts
    279
    Thanks
    8
    Thanked 2 Times in 2 Posts

    Default Binary Trees:

    public class InnerClass implements UsingInterface
    {
    	public class tree  //inner class
    	{
    		int number;
    		tree left;
    		tree right;
    	}
     
    	private tree root;
     
     
    	public InnerClass()
    	{
    		System.out.println("Inner Class constructer called and root is null");
    		root = null;		
    	}
     
    	private void insert(int number,tree leaf) //helper method for binary tree insert
    	{
     
    		if(number < leaf.number)
    		{
    			if(leaf.number != null)
    			{
    				insert(number,leaf.left);
    			}
    			else
    			{
    				leaf.left = new tree();
    				leaf.left.number = number;
    				leaf.left.left = null;
    				leaf.right.right=null;
    			}
     
    		}
    		else if(number > leaf.number)
    		{
    			if(leaf.number != null)
    			{
    				insert(number,leaf.right);
    			}
    			else
    			{
    				leaf.right = new tree();
    				leaf.right.number = number;
    				leaf.right.left = null; //creates new left child and sets it to null
    				leaf.right.right=null; //creates a new right child and sets it to null
    			}
    		}
     
    	}
     
    	public void insert(int key)
    	{
    		if(root!=null)
    		{
    			insert(key,root);
    		}
    		else
    		{
    			root = new tree();
    			root.number = key;
    			root.left = null;
    			root.right = null;
    		}
    	}
     
    	public void search(int key)
    	{
    		search(key,root);
    	}
     
    	private void search(int key,tree node)
    	{
    		if(node==null)
    		{
    			System.out.printf("%s ", "Tree is empty");
    		}
    		else if(key == node.number)
    		{
    			System.out.printf("%s,%i ", "The number was node.number found");
     
    		}
    		else if(node != null)
    		{
    			if(key < node.number)
    			{
    				search(key,node.left);
    			}
    			else if(key > node.number)
    			{
    				search(key,node.right);
    			}
    			else
    				System.out.println("The number was not found");
    		}
     
    	}
    }
     
    Inner Class constructer called and root is null
    Exception in thread "main" java.lang.NullPointerException
    	at InnerClass.insert(InnerClass.java:23)
    	at InnerClass.insert(InnerClass.java:42)
    	at InnerClass.insert(InnerClass.java:59)
    	at Inheritance.pushNumber(Inheritance.java:10)
    	at MainClass.main(MainClass.java:9)


    I am playing around with binary trees in Java. I am used to using pointers in C++ and wanted to see how they work in Java. However I keep getting errors, do i need to create the inner class somewhere? If so why?


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    21,979
    Thanks
    56
    Thanked 2,359 Times in 2,330 Posts

    Default Re: Binary Trees:

    I keep getting errors
    Please copy the full text of the error messages and paste it here. It has important info about the errors.
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Member
    Join Date
    Apr 2014
    Location
    Germany
    Posts
    279
    Thanks
    8
    Thanked 2 Times in 2 Posts

    Default Re: Binary Trees:

    I attached them to the end of the code in the first post.

    Inner Class constructer called and root is null
    Exception in thread "main" java.lang.NullPointerException
    	at InnerClass.insert(InnerClass.java:23)
    	at InnerClass.insert(InnerClass.java:42)
    	at InnerClass.insert(InnerClass.java:59)
    	at Inheritance.pushNumber(Inheritance.java:10)
    	at MainClass.main(MainClass.java:9)

  4. #4
    Member
    Join Date
    Apr 2014
    Location
    Germany
    Posts
    279
    Thanks
    8
    Thanked 2 Times in 2 Posts

    Default Re: Binary Trees:

    Here is something odd too, when I put in Integer instead of int I do not get any errors until I run the program. I have listed the runtime error in the above post and at the end of the first posts code.

    The error is telling me something is null, which I want, at least initially. The binary tree's root will be null until I push data into it and as I do it makes its two child nodes (leafs) and sets them to null.

    I am not work right now so I am unable to check my theory but would a error be caused initially because a number cannot be compared to a null value? For example like I am doing in my insert helper function?

    Am I creating the leaf nodes wrong in the else statements in the "helper" insert method? Whats the difference to int and Integer?

    I extended this class to class Inheritance one and made a loop inserting value 1-100 to the tree. Which is another error you can see above. However as you can see the constructor runs, it is the insert function that is failing.

  5. #5
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    21,979
    Thanks
    56
    Thanked 2,359 Times in 2,330 Posts

    Default Re: Binary Trees:

    Exception in thread "main" java.lang.NullPointerException
    at InnerClass.insert(InnerClass.java:23)
    There is a null value when line 23 is executed. Look at line 23 and find the variable with the null value and then backtrack to see why it is null and why the code tried to use a null value.
    If you don't understand my answer, don't ignore it, ask a question.

  6. #6
    Member
    Join Date
    Apr 2014
    Location
    Germany
    Posts
    279
    Thanks
    8
    Thanked 2 Times in 2 Posts

    Default Re: Binary Trees:

    Once I get home I will do that, but did you happen to read the rest of my posts questions?

  7. #7
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    21,979
    Thanks
    56
    Thanked 2,359 Times in 2,330 Posts

    Default Re: Binary Trees:

    Whats the difference to int and Integer?
    int is a primitive, Integer is a class. Only class objects can be dereferenced. You can not call a method using a primitive like an int as reference.
    If you don't understand my answer, don't ignore it, ask a question.

  8. #8
    Member
    Join Date
    Apr 2014
    Location
    Germany
    Posts
    279
    Thanks
    8
    Thanked 2 Times in 2 Posts

    Default Re: Binary Trees:

    public class InnerClass implements UsingInterface
    {
    	public class tree  //inner class
    	{
    		int number;
    		tree left;
    		tree right;
    	}
     
    	private tree root;
     
     
    	public InnerClass()
    	{
    		System.out.println("Inner Class constructer called and root is null");
    		root=null;
    	}
     
    	private void insert(int number,tree leaf) //helper method for binary tree insert
    	{
     
    		if(number < leaf.number)
    		{
    			if(leaf.left != null)
    			{
    				insert(number,leaf.left);
    			}
    			else
    			{
    				leaf.left = new tree();
    				leaf.left.number = number;
    				leaf.left.left = null;
    				leaf.right.right=null;
    			}
     
    		}
    		else if(number > leaf.number)
    		{
    			if(leaf.right != null)
    			{
    				insert(number,leaf.right);
    			}
    			else
    			{
    				leaf.right = new tree();
    				leaf.right.number = number;
    				leaf.right.left = null; //creates new left child and sets it to null
    				leaf.right.right=null; //creates a new right child and sets it to null
    			}
    		}
     
    	}
     
    	public void insert(int key)
    	{
    		if(root!=null)
    		{
    			insert(key,root);
    		}
    		else
    		{
    			root = new tree();
    			root.number = key;
    			root.left = null;
    			root.right = null;
    		}
    	}
     
    	public tree search(int key)
    	{
    		return search(key,root);
    	}
     
    	private tree search(int key,tree node)
    	{
    		if(node==null)
    		{
    			System.out.printf("%s ", "Tree is empty");
    		}
    		else if(key == node.number)
    		{
    			System.out.printf("%s,%i ", "The number was node.number found");	
    		}
    		else if(node != null)
    		{
    			if(key < node.number)
    			{
    				return search(key,node.left);
    			}
    			else if(key > node.number)
    			{
    				return search(key,node.right);
    			}
    			else
    				System.out.println("The number was not found");
    		}
     
    	}
    }

     
    Errors:
     
    at InnerClass.search(InnerClass.java:74)
    	at InnerClass.search(InnerClass.java:71)
    	at Inheritance.binarySearch(Inheritance.java:22)
    	at MainClass.main(MainClass.java:10)

    I want to return the inner class type "tree" for my binary tree search. It handles pointers for me so I am unclear what the deal is. The errors are coming from the search methods.

    I seen the error for the null number as soon as I got home and looked at it with a fresh set of eyes, it was a silly mistake.

  9. #9
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    21,979
    Thanks
    56
    Thanked 2,359 Times in 2,330 Posts

    Default Re: Binary Trees:

    at InnerClass.search(InnerClass.java:74)
    at InnerClass.search(InnerClass.java:71)
    Is that the full text? It looks like it is missing the first line(s). Look at line 74 and find what has the null value.

    I want to return the inner class type "tree"
    The inner class should be kept a secret. search() should return true or false depending on if the node is found.
    If you don't understand my answer, don't ignore it, ask a question.

  10. #10
    Member
    Join Date
    Apr 2014
    Location
    Germany
    Posts
    279
    Thanks
    8
    Thanked 2 Times in 2 Posts

    Default Re: Binary Trees:

    Sorry:

    Exception in thread "main" java.lang.Error: Unresolved compilation problem:
    This method must return a result of type InnerClass.tree

    at InnerClass.search(InnerClass.java:74)
    at InnerClass.search(InnerClass.java:71)
    at Inheritance.binarySearch(Inheritance.java:22)
    at MainClass.main(MainClass.java:10)

  11. #11
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    21,979
    Thanks
    56
    Thanked 2,359 Times in 2,330 Posts

    Default Re: Binary Trees:

    This method must return a result of type InnerClass.tree
    I suggested that the method NOT return a tree. User's should NOT have to know about tree objects.
    Either return the value in the node or true/false.
    If you don't understand my answer, don't ignore it, ask a question.

  12. #12
    Member
    Join Date
    Apr 2014
    Location
    Germany
    Posts
    279
    Thanks
    8
    Thanked 2 Times in 2 Posts

    Default Re: Binary Trees:

    Ok I did it and my compiler was very unhappy. I tried a few things and it runs but I have several run time errors now.

    Exception in thread "main" java.util.UnknownFormatConversionException: Conversion = 'i'
    at java.util.Formatter$FormatSpecifier.conversion(For matter.java:2606)
    at java.util.Formatter$FormatSpecifier.<init>(Formatt er.java:2634)
    at java.util.Formatter.parse(Formatter.java:2480)
    at java.util.Formatter.format(Formatter.java:2414)
    at java.io.PrintStream.format(PrintStream.java:920)
    at java.io.PrintStream.printf(PrintStream.java:821)
    at InnerClass.search(InnerClass.java:91)
    at InnerClass.search(InnerClass.java:87)
    at InnerClass.search(InnerClass.java:87)
    at InnerClass.search(InnerClass.java:87)
    at InnerClass.search(InnerClass.java:73)
    at Inheritance.binarySearch(Inheritance.java:22)
    at MainClass.main(MainClass.java:10)

    import java.io.*;
     
    public class InnerClass
    {
    	public class tree  //inner class
    	{
    		int number;
    		tree left;
    		tree right;
    	}
     
    	private tree root;
     
     
    	public InnerClass()
    	{
    		System.out.println("Inner Class constructer called and root is null");
    		root=null;
    	}
     
    	private void insert(int number,tree leaf) //helper method for binary tree insert
    	{
     
    		if(number < leaf.number)
    		{
    			if(leaf.left != null)
    			{
    				insert(number,leaf.left);
    			}
    			else
    			{
    				leaf.left = new tree();
    				leaf.left.number = number;
    				leaf.left.left = null;
    				leaf.right.right=null;
    			}
     
    		}
    		else if(number > leaf.number)
    		{
    			if(leaf.right != null)
    			{
    				insert(number,leaf.right);
    			}
    			else
    			{
    				leaf.right = new tree();
    				leaf.right.number = number;
    				leaf.right.left = null; //creates new left child and sets it to null
    				leaf.right.right=null; //creates a new right child and sets it to null
    			}
    		}
     
    	}
     
    	public void insert(int key)
    	{
    		if(root!=null)
    		{
    			insert(key,root);
    		}
    		else
    		{
    			root = new tree();
    			root.number = key;
    			root.left = null;
    			root.right = null;
    		}
    	}
     
    	public void search(int key)
    	{
    		search(key,root);
    	}
     
    	private boolean search(int key,tree node)
    	{
     
    		if(node != null)
    		{
    			if(key < node.number)
    			{
    				 search(key,node.left);
    			}
    			else if(key > node.number)
    			{
    				 search(key,node.right);
    			}
    			else if(node.number==key)
    			{
    				System.out.printf("%s,%i ", "The number was node.number found");
    				return true;
    			}
    		}
    		else
    			System.out.println("The number was not found");
    			return false;
    	}
    }

  13. #13
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    21,979
    Thanks
    56
    Thanked 2,359 Times in 2,330 Posts

    Default Re: Binary Trees:

    Exception in thread "main" java.util.UnknownFormatConversionException: Conversion = 'i'
    at java.util.Formatter$FormatSpecifier.conversion(For matter.java:2606)
    at java.util.Formatter$FormatSpecifier.<init>(Formatt er.java:2634)
    at java.util.Formatter.parse(Formatter.java:2480)
    at java.util.Formatter.format(Formatter.java:2414)
    at java.io.PrintStream.format(PrintStream.java:920)
    at java.io.PrintStream.printf(PrintStream.java:821)
    at InnerClass.search(InnerClass.java:91)
    Look at the printf() statement on line 91. The JVM does not like the format String: java.util.UnknownFormatConversionException: Conversion = 'i'
    If you don't understand my answer, don't ignore it, ask a question.

  14. The Following User Says Thank You to Norm For This Useful Post:

    jocdrew21 (April 23rd, 2014)

  15. #14
    Member
    Join Date
    Apr 2014
    Location
    Germany
    Posts
    279
    Thanks
    8
    Thanked 2 Times in 2 Posts

    Default Re: Binary Trees:

    ahhhhhhh.... Thanks norm...

Similar Threads

  1. Binary Search Trees theory question?
    By Scorks in forum Java Theory & Questions
    Replies: 2
    Last Post: March 15th, 2014, 06:38 PM
  2. Help with Dynamic linked list (Binary Trees)
    By Pip_Squeak in forum What's Wrong With My Code?
    Replies: 3
    Last Post: January 30th, 2014, 05:12 PM
  3. B+- Trees
    By itaymeller in forum What's Wrong With My Code?
    Replies: 1
    Last Post: May 19th, 2013, 08:10 PM
  4. binary trees
    By game06 in forum What's Wrong With My Code?
    Replies: 1
    Last Post: April 1st, 2013, 08:58 AM
  5. Replies: 7
    Last Post: January 23rd, 2013, 09:04 PM