Results 1 to 9 of 9
  1. #1
    Join Date
    Sep 2011
    Posts
    14
    Rep Power
    0

    Default Building a binary Search Tree

    Hello,

    I've built a class for making a binary search tree, but I'm having troubles figuring out if it's doing what it should be doing or not. It could very well just be I'm outputting the wrong thing to the user, but I haven't been able to work that out for sure as yet.

    My method that's using the class that's building the BST looks like this:

    Java Code:
    /****************************
     * Build Binary Search Tree *
     ****************************/
    	
    /**/	private static void buildBST(CreateObject[] array, String key)
    /**/	{
    /**/		TreeNode tree;
    /**/		
    /**/		tree=new TreeNode(key, array);
    /**/		System.out.println("\nBinary Tree: "+tree);
    /**/		
    /**/		//Not sure if it's working the way it should??
    /**/	}
    And the BST class itself looks like this, with what could be a dodgy toString method at the bottom.. I'm also iffy about the empty BinarySearchTree constructor I have at the beginning..:

    Java Code:
    import java.util.*;
    
    public class BinarySearchTree
    {
    	private String key;
    	private CreateObject[] value;
    	private TreeNode leftChild, rightChild, root;
    	
    	public BinarySearchTree(String inKey, CreateObject[] inVal)
    	{
    	}
    	
    	private class TreeNode
    	{
    		public TreeNode(String inKey, CreateObject[] inVal)
    		{
    			key=inKey;
    			value=inVal;
    			rightChild=null;
    			leftChild=null;
    		}
    		
    		public String getKey()
    		{
    			return key;
    		}
    		
    		public void setKey(String inKey)
    		{
    			if (inKey==null) 
    			{
    				throw new IllegalArgumentException("Key cannot be null");
    			}
    			key=inKey;
    		}
    		
    		public CreateObject[] getValue()
    		{
    			return value;
    		}
    		
    		public void setValue(CreateObject[] inValue)
    		{
    			value=inValue;
    		}
    		
    		public TreeNode getLeft()
    		{
    			return leftChild;
    		}
    		
    		public void setLeft(TreeNode inLeft)
    		{
    			leftChild=inLeft;
    		}
    		
    		public TreeNode getRight()
    		{
    			return rightChild;
    		}
    		
    		public void setRight(TreeNode inRight)
    		{
    			rightChild=inRight;
    		}
    	}
    	
    	public BinarySearchTree()
    	{
    		root=null;
    	} 
    	
    	public Object find(String key)
    	{
    		TreeNode currNode;
    		
    		currNode=root;
    		while ((currNode!=null)&&(key.equals(currNode.getKey())==false)) 
    		{
    			if (key.compareTo(currNode.getKey())<0) 
    			{
    				currNode=currNode.getLeft();
    			}
    			else 
    			{
    				currNode=currNode.getRight();
    			}
    		}
    		if (currNode==null) 
    		{
    			throw new NoSuchElementException("Key "+key+" not found");
    		}
    		return currNode.getValue();
    	}
    	
    	public void insert(String key, CreateObject[] value)
    	{
    		TreeNode currNode, parentNode, newNode;
    		int comparison;
    		
    		currNode=root;
    		parentNode=null;
    		while (currNode!=null) 
    		{
    			parentNode=currNode;
    			comparison=key.compareTo(currNode.getKey());
    			if (comparison==0) 
    			{
    				throw new IllegalArgumentException("Duplicate key: "+key);
    			}
    			else if (comparison<0)
    			{
    				currNode=currNode.getLeft();
    			}
    			else 
    			{
    				currNode=currNode.getRight();
    			}
    		}
    		
    		newNode=new TreeNode(key, value);
    		if (parentNode==null) 
    		{
    			root=newNode;
    		}
    		else if (key.compareTo(currNode.getKey())<0)
    		{
    			parentNode.setLeft(newNode);
    		}
    		else 
    		{
    			parentNode.setRight(newNode);
    		}
    
    	}
    	
    	public void delete(String key)
    	{
    		TreeNode currNode, parentNode;
    		
    		currNode=root;
    		parentNode=null;
    		while ((currNode!=null)&&(key.equals(currNode.getKey())==false)) 
    		{
    			parentNode=currNode;
    			if (key.compareTo(currNode.getKey())<0)
    			{
    				currNode=currNode.getLeft();
    			}
    			else 
    			{
    				currNode=currNode.getRight();
    			}
    		}
    		
    		if (currNode==null) 
    		{
    			throw new NoSuchElementException("Key "+key+" not found");
    		}
    		else if ((currNode.getLeft()==null)||(currNode.getRight()==null))
    		{
    			deleteNodeWithOneOrZeroChildren(currNode, parentNode);
    		}
    		else 
    		{
    			deleteNodeWithTwoChildren(currNode, parentNode);
    		}
    	}
    				
    	public void deleteNodeWithOneOrZeroChildren(TreeNode currNode, TreeNode parentNode)
    	{
    		TreeNode promoteNode;
    		
    		if (currNode.getLeft()!=null) 
    		{
    			promoteNode=currNode.getLeft();
    		}
    		else 
    		{
    			promoteNode=currNode.getRight();
    		}
    			
    		if (parentNode==null) 
    		{
    			root=promoteNode;
    		}
    		else if (parentNode.getLeft()==currNode)
    		{
    			parentNode.setLeft(promoteNode);
    		}
    		else 
    		{
    			parentNode.setRight(promoteNode);
    		}
    	}
    		
    	public void deleteNodeWithTwoChildren(TreeNode currNode, TreeNode parentNode)
    	{
    		TreeNode successorNode, succParentNode;
    		
    		successorNode=currNode.getRight();
    		succParentNode=parentNode;
    		
    		while (successorNode.getLeft()!=null) 
    		{
    			succParentNode=successorNode;
    			successorNode=successorNode.getLeft();
    		}
    		deleteNodeWithOneOrZeroChildren(successorNode, parentNode);
    		
    			currNode.setKey(successorNode.getKey());
    			currNode.setValue(successorNode.getValue());
    	}
    		
    	/* Why are there two height methods? */
    	public int height()
    	{
    		return height(root, 0);
    	}
    	private int height(TreeNode startNode, int htSoFar)
    	{
    		int leftHt, rightHt;
    		if (startNode==null) 
    		{
    			return htSoFar;
    		}
    		else 
    		{
    			leftHt=height(startNode.getLeft(), htSoFar+1);
    			rightHt=height(startNode.getRight(), htSoFar+1);
    		
    			if (leftHt>rightHt) 
    			{
    				return leftHt;
    			}
    			else 
    			{
    				return rightHt;
    			}
    		}
    	}
    	public String toString()
    	{
    		String tree=new String("\nRoot: "+root+"\nLeft Child: "+leftChild+"\nRight Child: "+rightChild);
    		return tree;
    	}
    }
    And when I run it, it keeps outputting this:

    Binary Tree:
    Key: Couch:6
    Value: [LCreateObject;@35a8767
    Right Child: null
    Left Child: null
    I don't know where the third line came from (Value: [LCreateObject;@35a8767), I've compiled the BST class and the run class so many times, it shouldn't still be outputting it =S

    But how do I know if it's doing what I want it to do? I guess I want it to tell me the path its taken when building each element into the BST.. It looks to me as if it's giving me the key of the root and then the left and right childs of the final leaf? which of course would give me what's above. I just want to know if it works

    Thank you so much for any help :)

  2. #2
    Join Date
    Sep 2011
    Posts
    14
    Rep Power
    0

    Default Re: Building a binary Search Tree

    Oh duh, I had a TreeNode class separate, which was giving me my Value:... in the output. The TreeNode class is this:

    Java Code:
    public class TreeNode
    {
    	private String key;
    	private CreateObject[] value;
    	private TreeNode leftChild, rightChild;
    	
    	public TreeNode(String inKey, CreateObject[] inVal)
    	{
    		key=inKey;
    		value=inVal;
    		rightChild=null;
    		leftChild=null;
    	}
    	
    	public String getKey()
    	{
    		return key;
    	}
    	
    	public void setKey(String inKey)
    	{
    		if (inKey==null) 
    		{
    			throw new IllegalArgumentException("Key cannot be null");
    		}
    		key=inKey;
    	}
    	
    	public CreateObject[] getValue()
    	{
    		return value;
    	}
    	
    	public void setValue(CreateObject[] inValue)
    	{
    		value=inValue;
    	}
    	
    	public TreeNode getLeft()
    	{
    		return leftChild;
    	}
    	
    	public void setLeft(TreeNode inLeft)
    	{
    		leftChild=inLeft;
    	}
    	
    	public TreeNode getRight()
    	{
    		return rightChild;
    	}
    	
    	public void setRight(TreeNode inRight)
    	{
    		rightChild=inRight;
    	}
    	public String toString()
    	{
    		String tree=new String("\nKey: "+key+"\nValue: "+value+"\nRight Child: "+rightChild+"\nLeft Child: "+leftChild);
    		return tree;
    	}
    }
    and I've commented out the TreeNode method in my BST, but it hasn't made any difference.. I also tried not initializing rightChild and leftChild, but that still didn't change anything

  3. #3
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,306
    Rep Power
    25

    Default Re: Building a binary Search Tree

    I don't know where the third line came from (Value: [LCreateObject;@35a8767)
    That looks like the String returned by the toString() method for an array.
    Somewhere you are calling an array's toString() method for an array of CreateObject class objects.
    If you want to see the contents of the array you could use the Arrays class's toString() method.

  4. #4
    Join Date
    Sep 2011
    Posts
    14
    Rep Power
    0

    Default Re: Building a binary Search Tree

    Ah yes, thank you that helped that one.

    Any advice about what's happening with the..?:

    rightChild:null
    leftChild:null
    and how to tell if my code is doing the right thing? I now know "root" is being set correctly, and "value" has the same value as "root"

  5. #5
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,306
    Rep Power
    25

    Default Re: Building a binary Search Tree

    and how to tell if my code is doing the right thing?
    For these kind of problems, you need to spend some time debugging. If you have an interactive debugger, use that.
    Otherwise add lots of printlns to show the values of variables and the execution flow.

  6. #6
    Join Date
    Sep 2011
    Posts
    14
    Rep Power
    0

    Default Re: Building a binary Search Tree

    Lucky me..

    Cheers

  7. #7
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,306
    Rep Power
    25

    Default Re: Building a binary Search Tree

    That's how its done. No magic, just a lot of debugging, looking at values and seeing where the code does something that you didn't intend or forgot would happen. You fix that bug and/or add more printlns and continue until it does what you want.

  8. #8
    Join Date
    Sep 2011
    Posts
    14
    Rep Power
    0

    Default Re: Building a binary Search Tree

    I've made a number of changes to my code, and at one point thought I had it working. Then I tried to search my tree, and it didn't work. So it's back to the drawing board..

    My method now looks like this:

    Java Code:
    /****************************
     * Build Binary Search Tree *
     ****************************/
    	
    	private static BinarySearchTree buildBST(CreateObject[] array)
    	{
    		BinarySearchTree tree=new BinarySearchTree();
    		//Will this reset tree when I don't want it to??
    		
    		for (int j=0; j<array.length; j++) 
    		{			
    			System.out.println("\nj = "+j+"\nArray length = "+array.length);
    			
    			String tempKey=array[j].getKey();
    			//Gets key relating to each element of the array
    			
    			System.out.println("tempKey: "+tempKey);
    			
    			tree.insert(tempKey, array[j]);
    			//inserts tempKey and corresponding array into tree
    			//Wont let me output to user, says I'm outputting type void
    
    			System.out.println("Binary Tree: "+tree);
    		}
    		return tree;
    	}
    And my BinarySearchTree class looks like this:

    Java Code:
    import java.util.*;
    
    public class BinarySearchTree
    {
    	private TreeNode leftChild, rightChild, root, currNode, parentNode, newNode;
    	
    		
    	public BinarySearchTree()
    	{
    		root=null;
    	}
    	
    		
    	public void insert(String key, CreateObject value)
    	{
    		int comparison;
    		
    		//System.out.println("\nBST insert method key: "+key+" and value: "+value);
    		
    		currNode=root;
    		//System.out.println("\nBST insert method currNode=root: "+currNode.getValue());
    		
    		parentNode=null;
    		while (currNode!=null) 
    		{
    			parentNode=currNode;
    			//System.out.println("\nBST insert method while parentNode: "+parentNode);
    			
    			comparison=key.compareTo(currNode.getKey());
    			//System.out.println("\nBST insert method while comparison: "+comparison);
    			
    			if (comparison==0) 
    			{
    				throw new IllegalArgumentException("Duplicate key: "+key);
    			}
    			else if (comparison<0)
    			{
    				currNode=currNode.getLeft();
    				//System.out.println("\nBST insert method while else if currNode: "+currNode);
    			}
    			else 
    			{
    				currNode=currNode.getRight();
    				//System.out.println("\nBST insert method while else currNode: "+currNode);
    			}
    		}
    		
    		newNode=new TreeNode(key, value);
    		//System.out.println("\nBST insert method newNode: "+newNode);
    		
    		if (parentNode==null) 
    		{
    			root=newNode;
    			//System.out.println("\nBST insert method if root: "+root);
    		}
    		else if (key.compareTo(currNode.getKey())<0)
    		{
    			parentNode.setLeft(newNode);
    			//System.out.println("\nBST insert method else if parentNode: "+parentNode);
    		}
    		else 
    		{
    			parentNode.setRight(newNode);
    			//System.out.println("\nBST insert method else parentNode: "+parentNode);
    		}
    	}
    
    	public CreateObject find(String key)
    	{
    		TreeNode currNode;
    
    		currNode = root;
    		while((currNode != null) && (key.equals(currNode.getKey()) == false))
    		{
    			if (key.compareTo(currNode.getKey()) < 0)
    			{
    				currNode = currNode.getLeft();
    			}
    			else
    			{
    				currNode = currNode.getRight();
    			}
    		}
    		if (currNode == null)
    			throw new NoSuchElementException("Key "+key+" not found");
    		return currNode.getValue();
    	}
    	
    	/*public void toString(CreateObject value)
    	{
    		System.out.println("Key: "+value.getKey()+"Brand: "+value.getBrand()+"Model: "+value.getModel()+"Weight: "+value.getWeight()+"Price: "+value.getPrice());
    	}*/
    }
    and my user outputs now look like this:

    j = 0
    Array length = 5
    tempKey: Couch:6
    Binary Tree: BinarySearchTree@4b71bbc9

    j = 1
    Array length = 5
    tempKey: Chair:8
    Exception in thread "main" java.lang.NullPointerException
    at BinarySearchTree.insert(BinarySearchTree.java:56)
    at Assignment.buildBST(Assignment.java:208)
    at Assignment.MakeChoiceAgain(Assignment.java:55)
    at Assignment.MakeChoice(Assignment.java:26)
    at Assignment.main(Assignment.java:14)
    For some reason it seems as if it's putting the first element through, starts to do the second but comes across an error somewhere along the way. I think because it has to compare 2 elements, but I can't quite figure out why it has trouble with that. To me it looks like it should work =S

    Again, many thanks for any help

  9. #9
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,306
    Rep Power
    25

    Default Re: Building a binary Search Tree

    "main" java.lang.NullPointerException
    at BinarySearchTree.insert(BinarySearchTree.java:56)
    You have a variable with a null value at line 56 in BinarySearchTree. Look at the variables used on that line and see which variable is null and then backtrack in the code to see why that variable does not have a valid value.

Similar Threads

  1. Binary search tree
    By hansmoolman in forum New To Java
    Replies: 2
    Last Post: 10-28-2010, 01:59 PM
  2. Replies: 0
    Last Post: 04-04-2010, 07:40 AM
  3. Binary search tree search method
    By chopo1980 in forum New To Java
    Replies: 2
    Last Post: 12-10-2009, 01:42 AM
  4. Binary Search Tree
    By anmadie in forum New To Java
    Replies: 5
    Last Post: 11-17-2009, 02:39 AM
  5. Binary Search Tree
    By michael_mke in forum New To Java
    Replies: 3
    Last Post: 12-04-2008, 02:03 AM

Tags for this Thread

Posting Permissions

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