Solved

Need help inserting objects into binary search tree

Posted on 2011-09-04
8
392 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
 

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
Top 6 Sources for Identifying Threat Actor TTPs

Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

 
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

What Is Threat Intelligence?

Threat intelligence is often discussed, but rarely understood. Starting with a precise definition, along with clear business goals, is essential.

Join & Write a Comment

After being asked a question last year, I went into one of my moods where I did some research and code just for the fun and learning of it all.  Subsequently, from this journey, I put together this article on "Range Searching Using Visual Basic.NET …
Java functions are among the best things for programmers to work with as Java sites can be very easy to read and prepare. Java especially simplifies many processes in the coding industry as it helps integrate many forms of technology and different d…
Viewers will learn one way to get user input in Java. Introduce the Scanner object: Declare the variable that stores the user input: An example prompting the user for input: Methods you need to invoke in order to properly get  user input:
This video teaches viewers about errors in exception handling.

759 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

Need Help in Real-Time?

Connect with top rated Experts

16 Experts available now in Live!

Get 1:1 Help Now