Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 2 of 2
  1. #1
    New to the CF scene
    Join Date
    Oct 2011
    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Problems creating a new BinarySearchTree class object

    Hi,

    My java program keeps giving me an error when I try to do what I've listed below. Any help on the matter would be greatly appreciated.

    Code:
    private static void buildBST(CreateObject[] array, String key)
    {
    	BinarySearchTree tree;
    	tree=new BinarySearchTree(key, array);
    }
    this is the error I keep getting:

    cannot find symbol
    symbol : constructor BinarySearchTree(java.lang.String,CreateObject[])
    location: class BinarySearchTree
    tree=new BinarySearchTree(key, array);
    ^
    and this is my BinarySearchTree class:

    Code:
    import java.util.*;
    
    public class BinarySearchTree
    {
    	private 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;
    		}
    	}
    	
    	private TreeNode root;
    	
    	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();
    	}
    		
    	/******************************************************************
    	 ************************ Recursive option ************************
    	public Object find(String key)
    	{
    		return findRecursive(key, root);
    	}
    	private Object findRecursive(String key, TreeNode currNode)
    	{
    		Object val;
    		currNode=root;
    		if (currNode==null) 
    		{
    			throw new ItemNotFoundException("Key "+key+" not found");
    		}
    		else if (key.equals(currNode.getKey())==true) 
    		{
    			val=currNode.getValue();
    		}
    		else if (key.compare(currNode.getKey())<0) 
    		{
    			val=findRecursive(key, currNode.getLeft());
    		}
    		else 
    		{
    			val=findRecursive(key, currNode.getRight());
    		}
    		return val;
    	}
    	 ******************************************************************/
    
    	
    	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 leftHt;
    			}
    		}
    	}
    }
    Thank you for any insight

  • #2
    God Emperor Fou-Lu's Avatar
    Join Date
    Sep 2002
    Location
    Saskatoon, Saskatchewan
    Posts
    16,979
    Thanks
    4
    Thanked 2,659 Times in 2,628 Posts
    The problem is quite simple (without going through everything in here). There is no constructor for BinarySearchTree that accepts the parameters String, T[]. You'll either need to write this constructor for it, or only use the default and deal with the provided key/value pairs after.

    The use of the key in a BST is a little unusual too. Since the collection works in a way that it can only move left or right based on the comparator to the current node, the key becomes rather useless overall. Such behaviour is more useful in a HashTree or similar type of object.


  •  

    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
    •