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

Thread: Need help fixing Binary Search Tree code

  1. #1
    Junior Member
    Join Date
    Dec 2010
    Posts
    4
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Need help fixing Binary Search Tree code

    I am having a bit of trouble with this binary search tree program. What I have to do is this:

    Write a main program that allows the user to choose among the following options:
    - enter a new string into the tree
    - find if a string is already in the tree
    - print an alphabetical list of all strings in the tree

    I have the code mostly done and it is:

    public class BTNode {
     public String data;
     public BTNode left;
     public BTNode right;
     
     public BTNode(String data, BTNode l, BTNode r) {
      this.data = data;
      this.left = l;
      this.right = r;
     }
     
     public BTNode(String data) {
      this.data = data;
     }
    }

    public class BTree {
     public BTNode root;
     
      public BTree(){
     
      }
     
      public BTree(BTree t){
       CopyNodes(t.root, this);
      }
     
      public void CopyNodes(BTNode node, BTree tree){
       if(node == null){
        return;
       }
       tree.insert(node.data);
       CopyNodes(node.left, tree);
       CopyNodes(node.right, tree);
      }
     
      public void insert(String newData){
       root = insert2(newData, root);
      }
     
      public BTNode insert2(String s, BTNode n){
       if(n == null){
        return new BTNode(s);
       }
     
       if(s.compareTo(n.data) < 0){
        n.left = insert2(s, n.left);
       }else if(s.compareTo(n.data) > 0){
        n.right = insert2(s, n.right);
       }
     
       return n;
      }
     
      public BTNode find(String s){
       BTNode node = root;
       while(node != null){
        if(s.equals(node.data)){
         return node;
        }
        if(s.compareTo(node.data) < 0){
         node = node.left;
        }else{
         node = node.right;
        }
       }
       return null;
      }
     
      public void printInOrder(){
       printInOrder2(root);
      }
     
     public void printInOrder2(BTNode n){
        if(n == null) return;            
        printInOrder2(n.left);                
    	 System.out.println(n.data);    
        printInOrder2(n.right);              
        }
    }

    and the driver program

    import java.util.*;
     public class TreeDriver
     {
     
     public static void main(String args[])
     {
     
    BTree t = new BTree();
    Scanner scan = new Scanner(System.in);
    do{
    	System.out.println("Please select one of the following.");
    	System.out.println("To insert something into the Tree press 1.");
    	System.out.println("To check if something is already in the tree press 2.");
    	System.out.println("To print the tree in alphabetic order press 3.");
    	System.out.println("To exit press 4.");
     
    if (scan.nextInt() ==1)
    	{	System.out.println("Please enter a word");
    		t.insert(scan.next());
    		System.out.println("Press 1 to return to selections");
    		}
     
     
     
    	 else
    	 if (scan.nextInt() ==2)
    	{	System.out.println("Enter the word to check");
    		t.find(scan.next());}
     
     
     
    	else
    	 if (scan.nextInt() ==3)
    	{	System.out.println("The tree in alphabetic order is: ");
    		t.printInOrder();}
     
     
     
    		else 
    		if	(scan.nextInt()==4)
    		System.out.println("program ending");
     
    }		
     
    while(scan.nextInt()!=4);		
     
    }
    }

    my problem is that I am unsure how to get a message to come up if you try to insert something in the tree that is already there, and for my driver program It works but it only works if you enter the commands several times. I know it is a problem with how I set up my loop but I can't think of a better way to do this.


  2. #2
    Junior Member
    Join Date
    Dec 2010
    Posts
    4
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Need help fixing Binary Search Tree code

    can anyone help me with this?

  3. #3
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Need help fixing Binary Search Tree code

    What's in the tree? If Strings, you could always use .equals.

  4. #4
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Need help fixing Binary Search Tree code

     if(s.compareTo(n.data) < 0){
        n.left = insert2(s, n.left);
       }else if(s.compareTo(n.data) > 0){
        n.right = insert2(s, n.right);
       }
     
       return n;
      }

    What if compareTo() = 0?

  5. #5
    Junior Member
    Join Date
    Dec 2010
    Posts
    4
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Need help fixing Binary Search Tree code

    What should I do to fix my loop?

  6. #6
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Need help fixing Binary Search Tree code

    Take JavaPenguin's last advice and account for compareTo() == 0. This is the case where you have two objects which are equal. For properly designed compareTo() methods compareTo() == 0 means that the two objects should be equal. In most implementations this usually results in not adding the new value and returning some indication that the add failed (probably as a boolean return result).

  7. #7
    Junior Member
    Join Date
    Dec 2010
    Posts
    4
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Need help fixing Binary Search Tree code

    for some reason I am not following you that well. could you show what you mean? what i am trying to do atm is fix the loop in the driver program
    Last edited by fistpunch; December 6th, 2010 at 11:26 AM.

Similar Threads

  1. Polymorphic Binary Search Tree Question
    By MJS139115 in forum What's Wrong With My Code?
    Replies: 5
    Last Post: November 9th, 2010, 06:08 PM
  2. need help with binary tree
    By vash0047 in forum Java Theory & Questions
    Replies: 5
    Last Post: July 12th, 2010, 08:23 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