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 5 of 5

Thread: Binary Tree Search[HELP]

  1. #1
    Junior Member
    Join Date
    Sep 2012
    Posts
    12
    My Mood
    Confused
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Binary Tree Search[HELP]

    hello everyone!
    I'm have created a binary tree program where the tree is balanced(but not sorted). The Tree hold unique strings in each nodes. if the user enters a non unique string, the node frequency (a field of the TreeNode class) should be increased by one, but no new node is created.Also, there is an option for searching for a string and getting the frequency if the string is found. In order to do this, I need to use recursion to create a search function in the Tree class (the search should use preorder (compare items in the left subtree, then right))
    My CODE below:
    public class Tree
    {
    	private TreeNode root;
     
    	public Tree()
    	{
    		root = null;
    	}
     
    	public boolean isEmpty()
    	{
    		return root == null;
    	}
     
    	public void insert(String st)
    	{
    		if (isEmpty())
    		{
    			root = new TreeNode(st);
    		}
    		else
    		{
    			root.add(st);
    		}
    	}
     
    	public TreeNode getRoot()
    	{
    		return root;
    	}
     
    	public static TreeNode search(TreeNode root, String st)
    	{
    		if(root == null) 
    		{
    			return null;
    		}
    		else if(st.equals(root.getString()))
    		{
    			return root;
    		}
    		else 
    		{	if (root.getLeft() != null)
    				return search(root.getLeft(), st);
    			else
    				return search(root.getRight(), st); 
    		}
    	}
    	public TreeNode found(TreeNode root)
    	{
    		return root;
    	}
    	public static void preorderPrint(TreeNode root) 
    	{
       	if ( root != null )
    		{  
    	      System.out.print( root.getString() + " " );  // Print the root item.
    	      preorderPrint( root.getLeft() );   // Print items in left subtree.
    	      preorderPrint( root.getRight() );  // Print items in right subtree.
       	}
    	}
    }
    public class TreeNode
    {
    	private int freq;	//frequency of the String in the Node
    	private String stValue;
    	private TreeNode left;
    	private TreeNode right;
     
    	public TreeNode(String st)
    	{
    		stValue = st;
    		left = null;
    		right = null;
    		freq = 1;
    	}
     
    	public void add(String st)
    	{	
    		if (left == null)
    		{
    			left = new TreeNode(st);
    		}
    		else if (right == null)
    		{
    			right = new TreeNode(st);
    		}
    		else
    		{
    			if(countNodes(left) <= countNodes(right))
    			{
    				left.add(st);
    			}
    			else
    			{
    				right.add(st);
    			}
    		}
    	}
     
    	//Count the nodes in the binary tree to which root points, and
    	public static int countNodes( TreeNode root ) {
    		if ( root == null )
     
    			// The tree is empty.  It contains no nodes.
    			return 0;  
     
    		else {
     
    			// Start by counting the root.
    			int count = 1;   
     
     
    			// Add the number of nodes in the left subtree.
    			count += countNodes(root.getLeft());
     
    			// Add the number of nodes in the right subtree.
    			count += countNodes(root.getRight()); 
     
    			return count;  // Return the total.
    		}
    	}
     
    	public TreeNode getLeft(){
    		return left;
    	}
     
    	public TreeNode getRight(){
    		return right;
    	}
     
    	public String getString()
    	{
    		return stValue;
    	}
     
    	public void upFreq()
    	{
    		freq = freq + 1;
    	}
    	public int getFreq()
    	{
    		return freq;
    	}
     
    }
    import java.util.Scanner;
     
    public class TreeDriver
    {
    	public static void main(String [] args)
    	{
    		String st;
    		int option = 0;
    		Scanner keyboard = new Scanner(System.in);
    		Scanner stKeyboard = new Scanner(System.in);
    		Tree stTree = new Tree();
    		TreeNode compareNode;
     
    		while(option != -1)
    		{
    			System.out.println("1. Enter a new String.\t"+
    									"2. Search for a String.\t"+
    									"3.Display Tree.\t"+
    									"-1. To Exit.");
    			option = keyboard.nextInt();
     
     
    			switch(option)
    			{
    				case 1:
    					System.out.println("Enter the string you would like to add to the tree: ");
    					st = stKeyboard.nextLine();
     
    					compareNode = stTree.search(stTree.getRoot(), st);
     
    					if(compareNode != null)
    					{
    						compareNode.upFreq();
    						System.out.println("\tRepeated String. Frequency +1.");
    					}
    					else
    					{
    						stTree.insert(st);
    						System.out.println("\tString inserted.");
    					}
     
    					break;
     
    				case 2:	
    					System.out.println("Enter the string you would like to search for: ");
    					String searchST = stKeyboard.nextLine();
     
    					compareNode = stTree.search(stTree.getRoot(), searchST);
    					if(compareNode != null)
    					{
    						System.out.println("FOUND - "+compareNode.getFreq());
    					}
    					else
    					{
    						System.out.println("NOT FOUND.");
    					}
    					break;
     
    				case 3:	
     
    						System.out.println("Preordered Strings:");
    						stTree.preorderPrint(stTree.getRoot());
    						System.out.println();
     
     
    					break;
    			}
     
    		}
    	}
    }
    I don't have any errors compiling the code, but there is a logic error in the search method in Tree class. when inserting the values A through H, you should get this tree:
    HTML Code:
    		    A
                /                 \
    	  B                    C
          /       \             /      \
         D	       F	   E         G
        /
      H
    I noticed when searching for Items in the left subtree (A,B,D,H) the search function works, but for(F,C,E,G) the search doesn't work. Could Anyone please tell me how to fix this logic error?


  2. #2
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,320
    Thanks
    181
    Thanked 833 Times in 772 Posts
    Blog Entries
    5

    Default Re: Binary Tree Search[HELP]

    I noticed when searching for Items in the left subtree (A,B,D,H) the search function works, but for(F,C,E,G) the search doesn't work. Could Anyone please tell me how to fix this logic error?
    Think hard about what the search method posted actually does. It will search (and return the result of) the left branch if that child is not null...in affect, never searching the right child of a node if the left is not null. Think about your algorithm, write it out on paper, then translate that to code. One way would be to search the left child, if the value is found return the result, otherwise search the right.

  3. #3
    Junior Member
    Join Date
    Sep 2012
    Posts
    12
    My Mood
    Confused
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Binary Tree Search[HELP]

    Sorry, but this didn't really help. I understand where is my error, I just have no idea how to fix it. I tried making it look like the preorderPrint class, but it doesn't work because I have to return the found TreeNode which makes things complicated.
    I tired this, but with "missing return statement" error.
    public static TreeNode search(TreeNode root, String st)
    	{
    		if(root ==null)
    			return null;
    		else if(st.equals(root.getString()))
    			{	
    				return root;
    			}
    		while(root.getLeft() != null)
    		{
    				return search(root.getLeft(), st);
    		}
    		while(root.getRight() != null)
    		{
    				return search(root.getRight(), st);
    		}
    	}

    This also gave the same error!
    public static TreeNode search(TreeNode root, String st) 
    	{
       	if ( root != null )
    		{  
    	      if(st.equals(root.getString()))
    			{
    				return root;
    			}
    			search( root.getLeft(), st);
    	      search( root.getRight(), st );
       	}
    		else
    		return null;
    	}

    Can you please suggest a fix? I spent hours on this with no luck

  4. #4
    Super Moderator jps's Avatar
    Join Date
    Jul 2012
    Posts
    2,642
    My Mood
    Daring
    Thanks
    90
    Thanked 263 Times in 232 Posts

    Default Re: Binary Tree Search[HELP]

    Can you please suggest a fix?
    ...
    Think about your algorithm, write it out on paper, then translate that to code. One way would be to search the left child, if the value is found return the result, otherwise search the right.

  5. #5
    Junior Member
    Join Date
    Sep 2012
    Posts
    12
    My Mood
    Confused
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Binary Tree Search[HELP]

    I understand what you guys are saying, its just that putting it in code is is a bit tough for me
    I have to search in preorder using recursion to compare the strings, and if a match is found, I have to return its corresponding TreeNode.

    This is my last try, and it still doesn't work *surprise* . I think the problem is the "return null" in the else statement in "search", but removing it creates this error --> "missing return statement"

    public boolean compare(TreeNode root, String st)
    	{	
    		if(st.equals(root.getString()))
    		{
    			return true; 
    		}
    		else 
    			return false;
    	}
    	public TreeNode search(TreeNode root, String st)
    	{
    		if(root==null)
    		{
    			return null;
    		}
    		else if(compare(root, st) == true)
    		{
    			return root;
    		}
    		else
    		{
    			search(root.getLeft(), st);
    			search(root.getRight(), st);
    			return null;
    		}
    	}

    Please help me out guys, this is driving me crazy

Similar Threads

  1. Building a binary search tree
    By Herah in forum What's Wrong With My Code?
    Replies: 1
    Last Post: November 28th, 2011, 07:29 AM
  2. Binary Search Tree
    By lex25288 in forum Algorithms & Recursion
    Replies: 3
    Last Post: January 19th, 2011, 09:10 AM
  3. Data Structures(Binary Search Tree to AVL Tree)ASAP
    By jfAdik in forum Algorithms & Recursion
    Replies: 2
    Last Post: April 5th, 2010, 03:58 AM
  4. Binary Search Tree
    By Koren3 in forum What's Wrong With My Code?
    Replies: 9
    Last Post: November 12th, 2009, 09:27 AM
  5. Binary Search Tree implementation
    By Ceasar in forum Java Theory & Questions
    Replies: 3
    Last Post: October 9th, 2009, 12:23 AM