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

Thread: Implementing a binary search tree using recursion?

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

    Default Implementing a binary search tree using recursion?

    Hello everyone,

    I am trying to implement this binary search tree using recursion.

    On the first iteration of the loop within the driver class, the first record gets added as root just as I expected, but now on the second iteration within the driver class the root is overwritten with the second record before it even steps in to the insert method. Why is this happening?

    Here is my code:

    Main Driver Class:
    import java.io.BufferedReader;
    import java.io.DataInputStream;
    import java.io.FileInputStream;
    import java.io.IOException;
    import java.io.InputStreamReader;
     
    public class GolfCourseDriver {
     
    	public static void main(String[] args) throws IOException {
     
    		FileInputStream fstream = new FileInputStream("GolfCourseData.txt");
    		DataInputStream in = new DataInputStream(fstream);
    		BufferedReader br = new BufferedReader(new InputStreamReader(in));
    		Tree searchTree = new Tree();
    		GolfCourse gcRec = new GolfCourse();
    		String strLine;
    		int count = 1;
    		String totalRecs = br.readLine();  // get total num of records
     
    		// build each node from each golfCourseObject
    		while((strLine = br.readLine()) != null){
     
    			switch(count){			
    			case 1:  gcRec.setCourseName(strLine); break;
    			case 2:  gcRec.setLocation(strLine); break;
    			case 3:  gcRec.setGreensFee(Double.valueOf(strLine)); break;
    			case 4:  gcRec.setPar(Integer.valueOf(strLine)); break;
    			case 5:  gcRec.setDesigner(strLine); break;
    			case 6:  gcRec.setYearBuilt(Integer.valueOf(strLine)); break;
    			case 7:  gcRec.setYards(Integer.valueOf(strLine)); break;			
    			default: System.out.println("Error! invalid item found."); break;		
    			}
    			// reset count 
    			if(count == 7){
    				searchTree.insert(gcRec);
    				count = 1;
    			}
    			else{
    				count++;
    			}
    		}	
    		in.close();
      }
    }

    Tree Class
    public class Tree {
     
      private TreeNode root;
     
      public Tree() {
        root = null;
      }
     
      public void insert(GolfCourse object) {
    	root = insert(object, root);
      }
     
      private TreeNode insert(GolfCourse newObject, TreeNode  node) {
    	if (node == null) {
    	    return new TreeNode(newObject);
    	}
    	if (newObject.greensFee == node.object.greensFee) {
    	    // replace the value in this node with a new value
    	    node.object = newObject;
    	    // alternative code creates new node, leaves old node unchanged:
    	    //return new BinaryNode<T>(value, node.left, node.right);
    	} else {
    	    if (newObject.greensFee < node.object.greensFee) {	// add to left subtree
    		node.lPtr = insert(newObject, node.lPtr);
    	    } else {		// add to right subtree
    		node.rPtr = insert(newObject, node.rPtr);
    	    }
    	}
    	return node;
      }
    }

    Tree Node Class:
    public class TreeNode {
     
    	GolfCourse object;
    	TreeNode lPtr;
    	TreeNode rPtr;
     
    	public TreeNode() {
    	}
     
    	public TreeNode(GolfCourse data){
    	object = data;
    	}
    }

    First few records of text Data passed in "GolfCourseData.txt:
    22
    Abacoa Golf Club
    Jupiter
    45
    72
    Joe Lee
    1999
    7200
    Eastpointe Country Club
    PB Gardens
    50
    72
    George and Tom Fazio
    1974
    6890


    Thanks


  2. #2
    Super Moderator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,104
    Thanks
    169
    Thanked 780 Times in 726 Posts
    Blog Entries
    5

    Default Re: Implementing a binary search tree using recursion?

    You are inserting the same object at each position. First you insert the object as the root, then when you read the next values change the values of that same object. Create new instances of your user data object to prevent overwriting of previous


    And please be forthright when cross-posting

    This thread has been cross posted here:

    http://www.java-forums.org/new-java/57812-implementing-binary-search-tree.html

    Although cross posting is allowed, for everyone's benefit, please read:

    Java Programming Forums Cross Posting Rules

    The Problems With Cross Posting


  3. #3
    Junior Member
    Join Date
    Aug 2010
    Posts
    4
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Implementing a binary search tree using recursion?

    Quote Originally Posted by copeg View Post
    You are inserting the same object at each position. First you insert the object as the root, then when you read the next values change the values of that same object. Create new instances of your user data object to prevent overwriting of previous


    And please be forthright when cross-posting

    This thread has been cross posted here:

    http://www.java-forums.org/new-java/57812-implementing-binary-search-tree.html

    Although cross posting is allowed, for everyone's benefit, please read:

    Java Programming Forums Cross Posting Rules

    The Problems With Cross Posting

    Sorry about the cross posting, this was driving me crazy. Anyways, I appreciate the help you were right. I created a new instance after each insert in the driver class and it worked. Again, thanks for the information.

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, 06:29 AM
  2. Binary Search Tree
    By lex25288 in forum Algorithms & Recursion
    Replies: 3
    Last Post: January 19th, 2011, 08: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, 08:27 AM
  5. Binary Search Tree implementation
    By Ceasar in forum Java Theory & Questions
    Replies: 3
    Last Post: October 9th, 2009, 12:23 AM