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

Thread: Binary Search Tree inorder tree traversal

  1. #1
    Junior Member
    Join Date
    Jan 2013
    Posts
    16
    My Mood
    Tolerant
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Binary Search Tree inorder tree traversal

    Hi I'm very new to Java and I'm trying to write some code to create a Binary Search Tree with the goal of outputting a list of integers using the inorder tree traversal method.
    I've got as far as this:
    public class BinarySearchTree {
     
     public class Node {
            private int value;
            private Node right;
            private Node left;
            //construct node
            //set current left and right vertices of root to null
            public Node(int value){
                this.value = value;
                left = null;
                right = null;
     
            }
            public Node leftNode() {
           return left;
       }
            public Node rightNode() {
           return right;
       }
            public int getNodeValue(){
                return value;
            }
     
        private Node root;
        //construct binary search tree
        public void BinarySearchTree() {
            root = null;
                }
        //Establish that if the tree is empty, then the value of the root is null
        public boolean ifEmpty()
        { 
            if (root == null) {
                return true;
        }
            else { return false;
                    }
        }
        //Develop ability to add values into the binary search tree
        public boolean insert(int value)
        { if (root == null) {
            root = new Node(value);
            return true;
        }
        else { if  (value == this.value)
                { return false; }
                else if (value <this.value) {
                      if (left == null) {
                            left = new Node(value);
                            return true;
                      } else {
                        return left.insert(value);
                    }
                } else if (value > this.value) {
                      if (right == null) {
                            right = new Node(value);
                            return true;
                      } else {
                        return right.insert(value);
                    }
                }
                return false;
     
           }
        }
     
        public void sortedList(){
            sortedList(root);
            }      
        private void sortedList(Node root){
            if (root == null) 
                return;
            sortedList( root.leftNode() );
            System.out.println(root.value + " ");
            sortedList ( root.rightNode() );
     
     
     
        }
     }
     
        public static void main(final String[] args){
     
     
        }
    }

    I've been following a tutorial and have been looking at some code on the internet, I'm not quite sure how I'm supposed to know if the sortedList method is sufficient to output, in order, a list of integers that has been put into the tree. Specifically the sortedList method I wrote with help of someone elses BST code and so I don't if it is written correctly in relation to the tree I have and the fields/objects that I have defined.
    Also how would I go about entering some numbers into the code to see the tree in action? Sorry If I'm coming across as quite dense but I've only been working with Java for the past couple of weeks.


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Binary Search Tree inorder tree traversal

    how would I go about entering some numbers into the code to see the tree in action?
    Create an instance of the class in the main() method and call some of its methods.


    It looks like the definitions of the Node class and the BST class are mixed together. The Node class shouldn't have classes for doing BST things like insert. The Node class should hold the pointer(s) and the data and provide access to them.
    The BST class looks at what is in the tree and controls adding/deleting Nodes from the tree.
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Junior Member
    Join Date
    Jan 2013
    Posts
    16
    My Mood
    Tolerant
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Re: Binary Search Tree inorder tree traversal

    Quote Originally Posted by Norm View Post
    Create an instance of the class in the main() method and call some of its methods.
    I have tried writing this:

      public static void main(final String[] args){
          int[] anArray = { 7, 3, 1, 6, 9, 0, 4, 5, 2, 8};
          value = anArray[0];
          Node firstnode = new Node(value);
          firstnode.insert(value);
        }

    However I get a "non-static variable cannot be referenced from a static context" for lines 2-4, is there any obvious reason why this is occurring?

    It looks like the definitions of the Node class and the BST class are mixed together.
    So should my Node class be in a separate file that the Binary Search File then calls methods from? Is this a cosmetic issue or will it end in complications in the final code?

    Thanks for the help, it's much appreciated!

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Binary Search Tree inorder tree traversal

    The Node class can be an inner class in the BST class or it could be outside the BST class. It would not have to be in a separate file(unless you want it to be public).

    "non-static variable cannot be referenced from a static context"
    Please post the full text of the error messages that show the source lines where the error happens.
    The main() method should NOT be trying to access any variables in the BST class. It should use BST methods to access anything.
    If you don't understand my answer, don't ignore it, ask a question.

  5. #5
    Junior Member
    Join Date
    Jan 2013
    Posts
    16
    My Mood
    Tolerant
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Re: Binary Search Tree inorder tree traversal

    BinarySearchTree.java:96: error: non-static variable value cannot be referenced
    from a static context
    value = anArray[0];
    ^
    BinarySearchTree.java:97: error: non-static variable value cannot be referenced
    from a static context
    Node firstnode = new Node(value);
    ^
    BinarySearchTree.java:98: error: non-static variable value cannot be referenced
    from a static context
    firstnode.insert(value);
    That's what I get from the cmd window.

  6. #6
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Binary Search Tree inorder tree traversal

    value should be a local variable in the main() method
    main() should NOT be creating Node objects. That should be done in the BST class's insert() method.

    In post#2 I said:

    Create an instance of the BST class in the main() method and call some of its methods.
    If you don't understand my answer, don't ignore it, ask a question.

  7. #7
    Junior Member
    Join Date
    Jan 2013
    Posts
    16
    My Mood
    Tolerant
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Re: Binary Search Tree inorder tree traversal

    Okay right, I understand that more clearly now. I also see the problem with the node class interfering with insert. However when I define the Node class as an inner class it looks like the fields defined in the Node class (root, left, right etc.) no longer know where to point to when they're used in the insert method?

  8. #8
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Binary Search Tree inorder tree traversal

    The Node class is passive. It holds the pointers and value.
    BST class has the logic for maintaining the tree and accessing the Node objects for chaining the nodes together and traversing the tree.
    root should be in BST not in Node
    If you don't understand my answer, don't ignore it, ask a question.

  9. #9
    Junior Member
    Join Date
    Jan 2013
    Posts
    16
    My Mood
    Tolerant
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Re: Binary Search Tree inorder tree traversal

    Okay I understand what you're saying, I currently have this code:

    public class BinarySearchTree {
     
     
      public static class Node {
            private int value;
            private Node right;
            private Node left;
            //construct node
            //set current left and right vertices of root to null
            public Node(int value){
                this.value = value;
                left = null;
                right = null;
     
            }
            public Node leftNode() {
           return left;
       }
            public Node rightNode() {
           return right;
       }
            public int getNodeValue(){
                return value;
            }
     
        private Node root;
      }
          //construct binary search tree
        public void BinarySearchTree() {
            root = null;
                }
        //Establish that if the tree is empty, then the value of the root is null
        public boolean ifEmpty()
        { 
            if (root == null) {
                return true;
        }
            else { return false;
                    }
        }
        //Develop ability to add values into the binary search tree
        public boolean insert(int value)
        { if (root == null) {
            root = new Node(value);
            return true;
        }
        else { if  (value == this.value)
                { return false; }
                else if (value <this.value) {
                      if (left == null) {
                            left = new Node(value);
                            return true;
                      } else {
                        return left.insert(value);
                    }
                } else if (value > this.value) {
                      if (right == null) {
                            right = new Node(value);
                            return true;
                      } else {
                        return right.insert(value);
                    }
                }
                return false;
     
           }
        }
     
        public void sortedList(){
            sortedList(root);
            }      
        private void sortedList(Node root){
            if (root == null) 
                return;
            sortedList( root.leftNode() );
            System.out.println(root.value + " ");
            sortedList ( root.rightNode() );
     
        }
     
     
     
     
      public static void main(final String[] args, int value){
          int[] anArray = { 7, 3, 1, 6, 9, 0, 4, 5, 2, 8};
          value = anArray[0];
          BinarySearchTree bst = new BinarySearchTree();
          boolean aVal = bst.insert(value);
     
        }
    }

    When I implement it I get the following 14 errors:

    BinarySearchTree.java:41: error: cannot find symbol
    root = null;
    ^
    symbol: variable root
    location: class BinarySearchTree
    BinarySearchTree.java:46: error: cannot find symbol
    if (root == null) {
    ^
    symbol: variable root
    location: class BinarySearchTree
    BinarySearchTree.java:54: error: cannot find symbol
    { if (root == null) {
    ^
    symbol: variable root
    location: class BinarySearchTree
    BinarySearchTree.java:55: error: cannot find symbol
    root = new Node(value);
    ^
    symbol: variable root
    location: class BinarySearchTree
    BinarySearchTree.java:58: error: cannot find symbol
    else { if (value == this.value)
    ^
    symbol: variable value
    BinarySearchTree.java:60: error: cannot find symbol
    else if (value <this.value) {
    ^
    symbol: variable value
    BinarySearchTree.java:61: error: cannot find symbol
    if (left == null) {
    ^
    symbol: variable left
    location: class BinarySearchTree
    BinarySearchTree.java:62: error: cannot find symbol
    left = new Node(value);
    ^
    symbol: variable left
    location: class BinarySearchTree
    BinarySearchTree.java:65: error: cannot find symbol
    return left.insert(value);
    ^
    symbol: variable left
    location: class BinarySearchTree
    BinarySearchTree.java:67: error: cannot find symbol
    } else if (value > this.value) {
    ^
    symbol: variable value
    BinarySearchTree.java:68: error: cannot find symbol
    if (right == null) {
    ^
    symbol: variable right
    location: class BinarySearchTree
    BinarySearchTree.java:69: error: cannot find symbol
    right = new Node(value);
    ^
    symbol: variable right
    location: class BinarySearchTree
    BinarySearchTree.java:72: error: cannot find symbol
    return right.insert(value);
    ^
    symbol: variable right
    location: class BinarySearchTree
    BinarySearchTree.java:81: error: cannot find symbol
    sortedList(root);
    ^
    symbol: variable root
    location: class BinarySearchTree
    14 errors
    At the risk of you wasting too much of your own time, and also so I can learn Java better myself, are there any hints you could give as to how I could implement the logic required in the BST class so that the fields recognise that they originate from the Node class?

    Thanks

  10. #10
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Binary Search Tree inorder tree traversal

    Did you see this in post#8
    root should be in BST not in Node

    Where is the constructor for the BST class. Hint: constructors don't return void.


    Most of the errors for "cannnot find symbol" are because all those variables are in the Node class not in the BST class.
    You need to use a reference to a class to access its variables. For example root is a reference to a Node class. Then root.value gets the value of the root node.
    If you don't understand my answer, don't ignore it, ask a question.

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

    Maukkv (January 23rd, 2013)

  12. #11
    Junior Member
    Join Date
    Jan 2013
    Posts
    16
    My Mood
    Tolerant
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Re: Binary Search Tree inorder tree traversal

    I'm not sure how I can solve the problem I now have, I've tried replacing the left and right in the insert method with Node.left/Node.right but I now get an error saying that they can't be referenced from a static context.

  13. #12
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Binary Search Tree inorder tree traversal

    Use a reference to a node to get to the values in a node. For example: root.value would access value in the instance of Node referred to by toot.
    Node.left is how it would be coded if left was static.
    If you don't understand my answer, don't ignore it, ask a question.

  14. #13
    Junior Member
    Join Date
    Jan 2013
    Posts
    16
    My Mood
    Tolerant
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Re: Binary Search Tree inorder tree traversal

    I've changed my code quite substantially, and now I have seem to have got a working bit of code, however now when I run it in the command window I get the following error which I can't seem to make sense of:

    Exception in thread "main" java.lang.NoClassDefFoundError: BinarySearchTree (wro
    ng name: binary/search/tree/BinarySearchTree)
    at java.lang.ClassLoader.defineClass1(Native Method)
    at java.lang.ClassLoader.defineClass(ClassLoader.java :791)
    at java.security.SecureClassLoader.defineClass(Secure ClassLoader.java:14
    2)
    at java.net.URLClassLoader.defineClass(URLClassLoader .java:449)
    at java.net.URLClassLoader.access$100(URLClassLoader. java:71)
    at java.net.URLClassLoader$1.run(URLClassLoader.java: 361)
    at java.net.URLClassLoader$1.run(URLClassLoader.java: 355)
    at java.security.AccessController.doPrivileged(Native Method)
    at java.net.URLClassLoader.findClass(URLClassLoader.j ava:354)
    at java.lang.ClassLoader.loadClass(ClassLoader.java:4 23)
    at sun.misc.Launcher$AppClassLoader.loadClass(Launche r.java:308)
    at java.lang.ClassLoader.loadClass(ClassLoader.java:3 56)
    at sun.launcher.LauncherHelper.checkAndLoadMain(Launc herHelper.java:482)

    My code now looks like:
    public class BinarySearchTree {
     
        //set up node with fields 
        //determining the node's 
        //placement in the tree 
        //relative to the nodes around it
     
      public class Node {
           public Node parent;
           public Node left;
           public Node right;
     
           private int value;
     
           public Node(int value){
               this.parent = null;
               this.left = null;
               this.right = null;
               this.value = value;                  
           }
     
           public int getValue(){
              return this.value;
          }
           public void setValue(int value){
               this.value = value;
           }
     
      }
     
      private Node root;
     
      //Construct the Binary Search Tree with current root = null
     
      public BinarySearchTree(){
          this.root = null;
      }
      public Node returnRoot(){
          return root;
      }
      public void insertNode(int id)
      {
          Node newNode = new Node(id);
          newNode.value = id;
          if (root == null){
              root = newNode;
          }
          else {
              Node current = root;
              Node parent;
              while(true)
              {
                  parent = current;
                  if(id < current.value)
                  {
                      current = current.left;
                      if(current==null){
                          parent.left = newNode;
                          return;
                          }
                        }
                  else {
                      if(current==null){
                          parent.right = newNode;
                          return;
                      }
                  }
              }
     
          }
      }
     
      public void sortedList(Node node){
            if (root != null) {
            sortedList( node.left );
            System.out.println(node.value + " ");
            sortedList( node.right );
               }
    }                  
     
      public static void main(final String[] args) 
      {
          int value;
          BinarySearchTree tree1 = new BinarySearchTree();
          tree1.insertNode(7);
          tree1.insertNode(1);
          tree1.insertNode(0);
          tree1.insertNode(9);
          tree1.insertNode(3);
          tree1.insertNode(6);
          tree1.insertNode(2);
          tree1.insertNode(4);
          tree1.insertNode(5);
          tree1.insertNode(8);
     
          System.out.println("Sorted list of integers from tree: ");
                  tree1.sortedList(tree1.returnRoot());
     
        }
    }
    and when I have it written in Netbeans it doesn't flag up any errors.

    Thanks for the help.

  15. #14
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Binary Search Tree inorder tree traversal

    Exception in thread "main" java.lang.NoClassDefFoundError: BinarySearchTree (wro
    ng name: binary/search/tree/BinarySearchTree)
    That long name is for the case where the class is in the package: binary.search.tree

    The full package.classname must be specified with the java command when trying to execute the class.
    The IDE hides all that.
    If you don't understand my answer, don't ignore it, ask a question.

  16. #15
    Junior Member
    Join Date
    Jan 2013
    Posts
    16
    My Mood
    Tolerant
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Re: Binary Search Tree inorder tree traversal

    When I try to run it in Netbeans, it just seems to run forever, I left it going for over 20 mins and it didn't complete the running process?

  17. #16
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Binary Search Tree inorder tree traversal

    Sounds like an infinite loop. Add some printlns to show where the code is executing and what the values of the variables are as they are used. The print out will show you where the loop is.
    If you don't understand my answer, don't ignore it, ask a question.

  18. #17
    Junior Member
    Join Date
    Jan 2013
    Posts
    16
    My Mood
    Tolerant
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Re: Binary Search Tree inorder tree traversal

    I've narrowed it down to the while section in my code I've tried implementing a count system so that it acts while the count is below a certain number.

    public static int count = 1;
    .
    .
    .
    while(count < 10)
              {
                  parent = current;
                  if(id < current.value)
                  {
                      current = current.left;
                      if(current==null){
                          parent.left = newNode;
                          count++;
                          return;
                          }
                        }
                  else {
                      if(current==null){
                          parent.right = newNode;
                          count++;
                          return;
                      }
                  }
              }

    I'm entering 10 numbers into the tree so I assumed if I started the count at 1 and said for count < 10 it would have to stop. However it still seems to be an infinite loop and no matter how low I make the while expression it doesn't stop running. If I take away the while statement it runs the iteration once and stops.

    --- Update ---

    Update: for count < 3 it works but only produces the first three integers from my main method. For any more it seems to become infinite

    --- Update ---

    Update: I've finally managed to get it to work but for some reason I need to set the count to be less than an arbitrarily high number. Right now 100 suffices, but is there any way I could set the count to be less than a number that would work for any number of integers added?

  19. #18
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Binary Search Tree inorder tree traversal

    I need to set the count
    What is the count? Is it used when debugging the code to keep the output down to a reasonable size?
    Once the bug is fixed the debug count can be commented out of the source.
    If you don't understand my answer, don't ignore it, ask a question.

Similar Threads

  1. Binary Tree Traversal help please
    By sim18 in forum What's Wrong With My Code?
    Replies: 0
    Last Post: November 27th, 2012, 08:01 AM
  2. Binary Tree Search[HELP]
    By husain2213 in forum What's Wrong With My Code?
    Replies: 4
    Last Post: November 13th, 2012, 11:33 PM
  3. Binary Search Tree
    By lex25288 in forum Algorithms & Recursion
    Replies: 3
    Last Post: January 19th, 2011, 09:10 AM
  4. 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
  5. Binary Search Tree
    By Koren3 in forum What's Wrong With My Code?
    Replies: 9
    Last Post: November 12th, 2009, 09:27 AM