Solved

Need help inserting objects into binary search tree

Posted on 2011-09-04
8
406 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
MS Dynamics Made Instantly Simpler

Make Your Microsoft Dynamics Investment Count  & Drastically Decrease Training Time by Providing Intuitive Step-By-Step WalkThru Tutorials.

 

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

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

Are you developing a Java application and want to create Excel Spreadsheets? You have come to the right place, this article will describe how you can create Excel Spreadsheets from a Java Application. For the purposes of this article, I will be u…
Introduction This article is the first of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article explains our test automation goals. Then rationale is given for the tools we use to a…
Viewers will learn about arithmetic and Boolean expressions in Java and the logical operators used to create Boolean expressions. We will cover the symbols used for arithmetic expressions and define each logical operator and how to use them in Boole…
This theoretical tutorial explains exceptions, reasons for exceptions, different categories of exception and exception hierarchy.

733 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