Thread: 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?

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)

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.

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

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.

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)

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

ahhhhhhh.... Thanks norm...