Solved

Need help inserting objects into binary search tree

Posted on 2011-09-04
8
400 Views
Last Modified: 2013-11-23
I am having trouble inserting more than one object into a binary search tree.
I have attached the code for both classes that I am working with. If someone can please explain
to me what it is I am doing wrong that would be great.
import java.util.*;
   public class ClubMember {
      String memberName;
      int memberId;

      public ClubMember() {}

      public ClubMember(int id, String name) {
         memberId = id;
         memberName = name;
         }
      public int getId() {
         return memberId;
         }
      public String getName() {
         return memberName;
         }
      public String toString() {
         return String.valueOf(memberId) + ": " + memberName;
         }
   
      public static void main(String[] args) {
         new ClubMember().run();
      
         }
      public void run() {
         ClubMember newMember;
         int tempId, counter = 10;
         Scanner input = new Scanner(System.in);
         String userDecision, tempName;
         BinaryTree.Node node = null;
         BinaryTree tree = new BinaryTree();
         for(int i = 0; i < counter; counter--) {
            System.out.println("Enter Club member id: ");
            tempId = input.nextInt();
            System.out.println("Enter Club member name: ");
            tempName = input.next();
            newMember = new ClubMember(tempId, tempName);
            node = new BinaryTree.Node(newMember);
            tree.insert(node, newMember);
            tree.printInOrder(node);
         }
      
      }
}

Open in new window

public class BinaryTree {

	static class Node {
		Node left, right;
		ClubMember value;
		public Node(ClubMember value) {
			this.value = value;
		}
	}
	public void insert(Node node, ClubMember value) {
		if(value.getId() < node.value.getId()) {
			if(node.left != null) {
				insert(node.left, value);
			}else{
				System.out.println("Inserted " + value +
					" to left of " + node.value);
				node.left = new Node(value);
			}
		}else if (value.getId() > node.value.getId()) {
			if(node.right != null) {
				insert(node.right, value);
			}else{
				System.out.println("Inserted " + value +
					" to right of " + node.value);
				node.right = new Node(value);
			}
		}
	}
	public void printInOrder(Node node) {
		if(node != null) {
			printInOrder(node.left);
			System.out.println(node.value);
			printInOrder(node.right);
		}
	}
}

Open in new window

0
Comment
Question by:TIUI
  • 5
  • 3
8 Comments
 
LVL 47

Expert Comment

by:for_yan
ID: 36482260
So what is it you are trying to do?
It asks id and name and then again id and name, etc.
What should happen then?
0
 

Author Comment

by:TIUI
ID: 36482287
Sorry about that I should have put that in the original question.

The app should allow a user to enter in a person's name and an id and store them based on the id in a binary search tree. It should also be able to print out the names with their ids in order. There is no specified number of people to be stored, so I just made it loop through 10 times.
0
 
LVL 47

Expert Comment

by:for_yan
ID: 36482296
for the firast memeber  both conditions are not satisfied:

value.getId() < node.value.getId())

and

value.getId() > node.value.getId())

so it was not inserting anything

0
Live: Real-Time Solutions, Start Here

Receive instant 1:1 support from technology experts, using our real-time conversation and whiteboard interface. Your first 5 minutes are always free.

 

Author Comment

by:TIUI
ID: 36482309
And that is where I am having the problem. I am new to trees and I really am not sure how to fix this. Any suggestions?
0
 
LVL 47

Expert Comment

by:for_yan
ID: 36482365


This code from http://www.daniweb.com/software-development/java/threads/353400
is working (see output).

Study it and you'll udenrstandt how to correct yours

One thing - it seem like root node should be inserted in a different way
form all the others

public class BinaryTreeTest {

  public static void main(String[] args) {
    new BinaryTreeTest().run();
  }

  static class Node {
    Node left;

    Node right;

    int value;

    public Node(int value) {
      this.value = value;
    }
  }

  public void run() {
    // build the simple <strong class="highlight">tree</strong> from chapter 11.
    Node root = new Node(5);
   // System.out.println("<strong class=\"highlight">Binary</strong> <strong class="highlight">Tree</strong> Example");
    System.out.println("Building with root value " + root.value);
    insert(root, 1);
    insert(root, 8);
    insert(root, 6);
    insert(root, 3);
    insert(root, 9);
    System.out.println("Traversing on order");
    printInOrder(root);
    System.out.println("Traversing front-to-back from location 7");
    printFrontToBack(root, 7);
  }

  public void insert(Node node, int value) {
    if (value < node.value) {
      if (node.left != null) {
        insert(node.left, value);
      } else {
        System.out.println("  Inserted " + value + " to left of "
            + node.value);
        node.left = new Node(value);
      }
    } else if (value > node.value) {
      if (node.right != null) {
        insert(node.right, value);
      } else {
        System.out.println("  Inserted " + value + " to right of "
            + node.value);
        node.right = new Node(value);
      }
    }
  }

  public void printInOrder(Node node) {
    if (node != null) {
      printInOrder(node.left);
      System.out.println("  Traversed " + node.value);
      printInOrder(node.right);
    }
  }

  /**
   * uses in-order traversal when the origin is less than the node's value
   *
   * uses reverse-order traversal when the origin is greater than the node's
   * order
   */
  public void printFrontToBack(Node node, int camera) {
    if (node == null)
      return;
    if (node.value > camera) {
      // print <strong class="highlight">in</strong> order
      printFrontToBack(node.left, camera);
      System.out.println("  Traversed " + node.value);
      printFrontToBack(node.right, camera);
    } else if (node.value < camera) {
      // print reverse order
      printFrontToBack(node.right, camera);
      System.out.println("  Traversed " + node.value);
      printFrontToBack(node.left, camera);
    } else {
      // order doesn't matter
      printFrontToBack(node.left, camera);
      printFrontToBack(node.right, camera);
    }
  }

}

Open in new window


Output:
Building with root value 5
  Inserted 1 to left of 5
  Inserted 8 to right of 5
  Inserted 6 to left of 8
  Inserted 3 to right of 1
  Inserted 9 to right of 8
Traversing on order
  Traversed 1
  Traversed 3
  Traversed 5
  Traversed 6
  Traversed 8
  Traversed 9
Traversing front-to-back from location 7
  Traversed 6
  Traversed 8
  Traversed 9
  Traversed 5
  Traversed 3
  Traversed 1

Open in new window


0
 
LVL 47

Assisted Solution

by:for_yan
for_yan earned 500 total points
ID: 36482418


This by analogy with the above example your code
with some correctionsseems to be working
(only ClubMember is changed):


import java.util.*;
   public class ClubMember {
      String memberName;
      int memberId;

      public ClubMember() {}

      public ClubMember(int id, String name) {
         memberId = id;
         memberName = name;
         }
      public int getId() {
         return memberId;
         }
      public String getName() {
         return memberName;
         }
      public String toString() {
         return String.valueOf(memberId) + ": " + memberName;
         }

      public static void main(String[] args) {
         new ClubMember().run();

         }
      public void run() {
         ClubMember newMember;
        BinaryTree.Node  node1 = new BinaryTree.Node(new ClubMember(5,"ttt"));
         int tempId, counter = 10;
         Scanner input = new Scanner(System.in);

         String userDecision, tempName;
         BinaryTree.Node node = null;
         BinaryTree tree = new BinaryTree();
           System.out.println("Enter Club member id: ");
            tempId = input.nextInt();
            System.out.println("Enter Club member name: ");
            tempName = input.next();
            newMember = new ClubMember(tempId, tempName);
          node = new BinaryTree.Node(newMember);


         for(int i = 0; i < counter; counter++) {
            System.out.println("Enter Club member id: ");
            tempId = input.nextInt();
            System.out.println("Enter Club member name: ");
            tempName = input.next();
            newMember = new ClubMember(tempId, tempName);
          //  node = new BinaryTree.Node(newMember);
            tree.insert(node, newMember);
            tree.printInOrder(node);
         }

      }
}

Open in new window



Enter Club member id: 
5
Enter Club member name: 
ttt
Enter Club member id: 
6
Enter Club member name: 
ttt
Inserted 6: ttt to right of 5: ttt
5: ttt
6: ttt
Enter Club member id: 
3
Enter Club member name: 
yyyy
Inserted 3: yyyy to left of 5: ttt
3: yyyy
5: ttt
6: ttt
Enter Club member id: 
8
Enter Club member name: 
yuiyu
Inserted 8: yuiyu to right of 6: ttt
3: yyyy
5: ttt
6: ttt
8: yuiyu
Enter Club member id: 

Open in new window

0
 
LVL 47

Accepted Solution

by:
for_yan earned 500 total points
ID: 36482485


I suggest that you use this code based
on MyBinaryTree object below which I modeled
on explanation here:

http://cslibrary.stanford.edu/110/BinaryTrees.html#java

go to section

Section 4 -- Java Binary Trees and Solutions

Seems understandable to me.
Just combine it with your ClubMember class
like below and it is all working and printing the tree

The good point they are making that they have public method
insert(data)
and all recursive stuff traversing the branches is private(root, data)
where it will actually find it place in the tree

import java.util.*;
   public class ClubMember {
      String memberName;
      int memberId;

      public ClubMember() {}

      public ClubMember(int id, String name) {
         memberId = id;
         memberName = name;
         }
      public int getId() {
         return memberId;
         }
      public String getName() {
         return memberName;
         }
      public String toString() {
         return String.valueOf(memberId) + ": " + memberName;
         }

      public static void main(String[] args) {
         new ClubMember().run();

         }
      public void run() {
         ClubMember newMember;

         int tempId, counter = 10;
         Scanner input = new Scanner(System.in);

         String userDecision, tempName;
         BinaryTree.Node node = null;
         MyBinaryTree tree = new MyBinaryTree();



         for(int i = 0; i < counter; counter++) {
            System.out.println("Enter Club member id: ");
            tempId = input.nextInt();
            System.out.println("Enter Club member name: ");
            tempName = input.next();
            newMember = new ClubMember(tempId, tempName);
          //  node = new BinaryTree.Node(newMember);
            tree.insert(newMember);
           // tree.printInOrder(node);
             tree.printTree();
         }

      }
}

Open in new window



public class MyBinaryTree {

    private Node root;

    private static class Node {
        Node left;
        Node right;
        ClubMember data;


    Node (ClubMember c){
        left = null;
         right = null;
        data = c;
    }


}
   public MyBinaryTree(){
         root = null;
   }

       public void insert(ClubMember c){
           root = insert(root, c);
       }
     private Node insert(Node node, ClubMember c) {
    if (node==null) {
      node = new Node(c);
    }
    else {
      if (c.getId() <= node.data.getId()) {
        node.left = insert(node.left, c);
      }
      else {
        node.right = insert(node.right, c);
      }
    }

    return(node); // in any case, return the new pointer to the caller
  }


    public void printTree() {
 printTree(root);
 System.out.println();
}

private void printTree(Node node) {
 if (node == null) return;

 // left, node itself, right
 printTree(node.left);
 System.out.print(node.data + "  ");
 printTree(node.right);
} 

}

Open in new window


Output:

Enter Club member id: 
5
Enter Club member name: 
ertert
5: ertert  
Enter Club member id: 
7
Enter Club member name: 
gdfg
5: ertert  7: gdfg  
Enter Club member id: 
2
Enter Club member name: 
sdfsd
2: sdfsd  5: ertert  7: gdfg  
Enter Club member id: 
1
Enter Club member name: 
iopio
1: iopio  2: sdfsd  5: ertert  7: gdfg  
Enter Club member id: 

Open in new window

0
 

Author Closing Comment

by:TIUI
ID: 36482523
Thank you so much, I was able to make the app. work using both solutions. I really appreciate the help.
0

Featured Post

Live: Real-Time Solutions, Start Here

Receive instant 1:1 support from technology experts, using our real-time conversation and whiteboard interface. Your first 5 minutes are always free.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

INTRODUCTION Working with files is a moderately common task in Java.  For most projects hard coding the file names, using parameters in configuration files, or using command-line arguments is sufficient.   However, when your application has vi…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
Viewers learn about the “while” loop and how to utilize it correctly in Java. Additionally, viewers begin exploring how to include conditional statements within a while loop and avoid an endless loop. Define While Loop: Basic Example: Explanatio…
This theoretical tutorial explains exceptions, reasons for exceptions, different categories of exception and exception hierarchy.

776 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question