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

Thread: Help with my Binary tree. (Node links are incorrect) Please!

  1. #1
    Junior Member
    Join Date
    Apr 2013
    Posts
    3
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Unhappy Help with my Binary tree. (Node links are incorrect) Please!

    Hey everyone. I desperately need a second set of eyes to look at my code for this binary tree I've been working on. I originally had it functioning great as a binary search tree, yet my professor is stressing that having the tree sorted isn't important only keeping it balanced when input is added to the tree. I'm getting nullPointerExceptions, or nodes other than the root aren't being added to the tree properly. I think I'm linking the nodes to the tree incorrectly. I've been at this for days and my brain feels like mush, I suspect it's something simple for you guys to understand. Any help would be more than appreciated. The binary tree contains nodes with String objects in them, frequency (for duplicate entries), and links to 2 child nodes. Search and frequency was working perfectly and somehow I screwed it up along with the insertion of new nodes when I focused on balancing it.

    Node Class:
     public class Node {
     
          String item;      // The data in this node.
          Node left;    // Pointer to left subtree.
          Node right;   // Pointer to right subtree.
          int freq = 1;
          Node(String str) {
                 // Constructor.  Make a node containing the specified string.
                 // Note that left and right pointers are initially null.
             item = str;
          }
       }  // end nested class TreeNode
     
     
    //Driver Class:
    import java.io.*;
    import java.util.Scanner;
     
    public class Driver{		
     
    	   public static void main(String[] args) {
    		BinaryTree tree = new BinaryTree(null);
    		Scanner input = new Scanner(System.in);
    		int select = 0;
    		System.out.println("Welcome to the Binary Search Tree program.");
    		select = tree.menuStart();
     
          while (select != 4) {
                // Get one string from the user, insert it into the tree,
                // and print some information about the tree.  Exit if the
                // user enters an empty string.  Note that all strings are
                // converted to lower case.
     
    //         TextIO.putln("\n\nEnter a string to be inserted, or press return to end.");
      //       TextIO.put("?  ");
     
      		 while(select == 1){
     
     
      		 System.out.print("Enter new string: ");
             String item;  // The user's input.
             item = input.nextLine();
             if (item.length() == 0)
                	System.out.println("Invalid input, please enter a string.");
             if (tree.treeContains(tree.root,item)) {
                   // Don't insert a second copy of an item that is already
                   // in the tree.
                System.out.println(item + " is already in the tree. It's frequency is now: " + tree.treeInsertFrequency(tree.root, item));
             }
             else {
                tree.treeInsert(item, tree.root);  // Add user's string to the tree.
             } System.out.println("Please enter a new command: ");
    		 select = tree.menuStart();
      		 } 
     
     
      		 while(select == 2) {
      		 	System.out.println("Please enter the string to search for: ");
      		 	String item = input.nextLine();
      		 	if (item.length() == 0)
                	System.out.println("Invalid search input, please enter a string.");
                	tree.Show();
             if (tree.treeContains(tree.root,item)) {
     
                System.out.println(item + " exists in the tree. It's frequency is " + tree.treeFrequency(tree.root, item));
             } else System.out.println("String does not exist in the Binary Tree.");
    		 select = tree.menuStart();
      		 }
     
      		 while(select == 3){
     
     
                System.out.println("The tree contains " + tree.countNodes(tree.root) + " unique strings.");
                System.out.println("Contents of tree:");
                tree.preOrderList(tree.root); 
    		 select = tree.menuStart();}
            	  } 
            // end while
    }}
     
     
    //Finally the problem, the BinaryTree class:
     
    import java.io.*;
    import java.util.Scanner;
     
    public class BinaryTree{
     
    	public static int size =1;
    	public static Node root = new Node(null);
    	public BinaryTree(String str){
    		String initStr = str;	
    	}
     
    			static int menuStart(){
    			Scanner input = new Scanner(System.in);
    			System.out.println("Enter one of the following numbers to use the tree:");
    			System.out.println("1, Add string. 2, Search Tree. 3, Display Tree. 4, Exit program.");
    			int temp = 0;
     
    			temp = input.nextInt();
     
    			while(temp!=1 && temp!=2 && temp!=3 && temp!=4){
    				 System.out.println("Invalid command, choose a number 1-4 please.");
    				 temp = input.nextInt();
    				 }
     
    			return temp; }
     
     
    public static void treeInsert(String newItem, Node r) {
     	  	 String it = newItem;
     	  	 if(r == null){
     	  	 	r = new Node(newItem);}
     	  	 	else{
     	  	 		 System.out.println(treeBalance(r));
     				 System.out.println(r);
     	  	 	  	 if(r == null){
     	  	 	   	 r = new Node(it);
     	  	 	   	System.out.println(r.item);}
     	  	 	     else{ 
     	  	 	     	if(treeBalance(r) == true)
     	  	 		 	treeInsert(newItem, r.left);
     	  	 		 	else
     	  	 		 	treeInsert(newItem, r.right);}
             } }
     
             public static void Show(){
             	System.out.println(root.item);
             }
     
    public static void setNode(String it, Node sr){
     
    		if(sr == null){
     	  	 	  	 sr = new Node(it);}
    		else{
    			 	  	if(treeBalance(sr) == true)
     	  	 		 	sr = sr.left;
     	  	 		 	else
     	  	 		 	sr = sr.right;
    			setNode(it, sr);
    		}
    }
     
    	static boolean treeBalance(Node b){
    		if((countNodes(b.left) == countNodes(b.right)) || (countNodes(b.left) < countNodes(b.right)
    			))
    		return true;
    		else
    		return false;}
     
     
       /**
        * Return true if item is one of the items in the binary
        * sort tree to which root points.   Return false if not.
        */
       static boolean treeContains( Node root, String item ) {
          if ( root == null ) {
                 // Tree is empty, so it certainly doesn't contain item.
             return false;
          }
          else if ( item.equals(root.item) ) {
                 // Yes, the item has been found in the root node.
             return true;
          }
          else if ( item != null) {
                 // If the item occurs, it must be in the left subtree.
             return treeContains( root.left, item );
          }
          else {
                 // If the item occurs, it must be in the right subtree.
             return treeContains( root.right, item );
          }
       }  // end treeContains()
     
          static int treeInsertFrequency( Node rf, String item ) {
          if ( rf == null ) {
                 // Tree is empty, so it certainly doesn't contain item.
             return 0;
          }
          else if ( item.equals(rf.item) ) {
                 // Yes, the item has been found in the rf node.
                rf.freq++;
                return rf.freq;
          }
          else if ( item.compareTo(rf.item) < 0 ) {
                 // If the item occurs, it must be in the left subtree.
     
             return treeInsertFrequency( rf.left, item );
          }
          else {
                 // If the item occurs, it must be in the right subtree.
     
             return treeInsertFrequency( rf.right, item );
          }
       }
     
             static int treeFrequency( Node f, String item ) {
          if ( f == null ) {
                 // Tree is empty, so it certainly doesn't contain item.
             return 0;
          }
          else if ( item.equals(f.item) ) {
                 // Yes, the item has been found in the f node.
     
             return f.freq;
          }
          else if ( item.compareTo(f.item) < 0 ) {
                 // If the item occurs, it must be in the left subtree.
     
             return treeFrequency( f.left, item );
          }
          else {
                 // If the item occurs, it must be in the right subtree.
     
             return treeFrequency( f.right, item );
          }
       }
     
       		static boolean rootExists(){
       			if(root == null){
       				return false;
       			} else return true;
       		}
     
       public static void preOrderList(Node node) {
     
          if ( node != null ) {
          	 System.out.println(node.item + " ");
          	 preOrderList(node.left);             // Print items in l subtree.
               // Print item in the node.
             preOrderList(node.right);            // Print items in the r subtree.
          }
       } // end preOrderList()
       /**
        * Count the nodes in the binary tree.
        * @param node A pointer to the root of the tree.  A null value indicates
        * an empty tree
        * @return the number of nodes in the tree to which node points.  For an
        * empty tree, the value is zero.
        */
       public static int countNodes(Node node) {
          if ( node == null ) {
                // Tree is empty, so it contains no nodes.
             return 0;
          }
          else {
                // Add up the root node and the nodes in its two subtrees.
             int leftCount = countNodes( node.left );
             int rightCount = countNodes( node.right );
             return  1 + leftCount + rightCount;  
          }
       } }
      // end countNodes()


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,067
    Thanks
    47
    Thanked 2,146 Times in 2,119 Posts

    Default Re: Help with my Binary tree. (Node links are incorrect) Please!

    I'm getting nullPointerExceptions
    What variable is null? Why doesn't the code test for the null value before it gets the exception?

    One problem I see is too much use of static variables and methods.
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Junior Member
    Join Date
    Apr 2013
    Posts
    3
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Help with my Binary tree. (Node links are incorrect) Please!

    I know where the nullPointerException is occurring, BinaryTree line 83 i think. It's a logic error I think, I think I may be creating a separate tree somehow by accident so when the root tree is accessed the nodes aren't there (?). The main piece of code I've been struggling with is this: (Also, the setNode method was an idea I was toying with it isn't being used at the moment because I can't even get the root.left and root.right to appear) Thank you for your help!

    public static void treeInsert(String newItem, Node r) {
     	  	 String it = newItem;
     	  	 if(r == null){
     	  	 	r = new Node(newItem);}
     	  	 	else{
     	  	 		 System.out.println(treeBalance(r));
     				 System.out.println(r);
     	  	 	  	 if(r == null){
     	  	 	   	 r = new Node(it);
     	  	 	   	System.out.println(r.item);}
     	  	 	     else{ 
     	  	 	     	if(treeBalance(r) == true)
     	  	 		 	treeInsert(newItem, r.left);
     	  	 		 	else
     	  	 		 	treeInsert(newItem, r.right);}
             } }
     
             public static void Show(){
             	System.out.println(root.item);
             }
     
    public static void setNode(String it, Node sr){
     
    		if(sr == null){
     	  	 	  	 sr = new Node(it);}
    		else{
    			 	  	if(treeBalance(sr) == true)
     	  	 		 	sr = sr.left;
     	  	 		 	else
     	  	 		 	sr = sr.right;
    			setNode(it, sr);
    		}
    }
     
    	static boolean treeBalance(Node b){
    		if((countNodes(b.left) == countNodes(b.right)) || (countNodes(b.left) < countNodes(b.right)
    			))
    		return true;
    		else
    		return false;}


    --- Update ---

    Quote Originally Posted by Norm View Post
    What variable is null? Why doesn't the code test for the null value before it gets the exception?

    One problem I see is too much use of static variables and methods.
    It throws the null exception when it tries to access any of the sub-nodes from the root. The nodes are apparently empty, and the root or parent node each has two pointers (left and right). If you call.. say root.left, but a new node hasn't been created at root.left it'll throw a null exception b/c it's not pointing to an existing node I suppose.

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,067
    Thanks
    47
    Thanked 2,146 Times in 2,119 Posts

    Default Re: Help with my Binary tree. (Node links are incorrect) Please!

    A useful technique for working with linked Nodes is to add a toString() method to the node that returns the data about the node: item, left and right. Then when a Node is printed, the toString() methods are called and the structure of the list/tree is completely displayed.

    Another technique I use for debugging code that uses the Scanner class for input is to preload the Scanner with its constructor so that the program automatically answers all questions. Here is a sample:
    		Scanner input = new Scanner("aaa\nxxx\nccc\nddd\nbb\n\n"); //System.in);
    ...
     
    	Scanner input = new Scanner("1 1 1 3 4"); //System.in);  //<<<<moved here
     
    	/*static*/ int menuStart(){
    //			Scanner input = new Scanner(System.in);


    For debugging the code I suggest that you add lots of calls to the println() method to display the execution flow and the contents of all the variables as they are used and changed.

    BTW A lot of the code is poorly formatted with improper, inconsistent indentations and hidden }s making it very hard to read and understand.
    If you don't understand my answer, don't ignore it, ask a question.

  5. The Following User Says Thank You to Norm For This Useful Post:

    Jacksla3 (April 18th, 2013)

Similar Threads

  1. Binary Tree ( Family Tree)
    By tommyacton in forum Algorithms & Recursion
    Replies: 0
    Last Post: March 23rd, 2013, 10:40 PM
  2. Binary Search Tree inorder tree traversal
    By Maukkv in forum What's Wrong With My Code?
    Replies: 17
    Last Post: January 26th, 2013, 04:28 PM
  3. Height of a node in a binary tree
    By ueg1990 in forum Algorithms & Recursion
    Replies: 2
    Last Post: November 19th, 2012, 12:17 AM
  4. [SOLVED] Finding deepest node of tree??
    By bczm8703 in forum What's Wrong With My Code?
    Replies: 5
    Last Post: April 10th, 2011, 11:48 AM
  5. 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

Tags for this Thread