1 2 Previous Next 22 Replies Latest reply: Dec 6, 2007 11:47 AM by 807601 RSS

    BINARY TREE & RECURSIVE INSERT METHOD

    807600
      PLEASE HELP ME!
      I hav a final assignment for my second year at uni and i can't get it to work!
      The assignment involves this code:
      public class BST 
      {
           private BSTNode root;
           public BST () 
                 {
                       // Construct an empty BST.
                root = null;
           }
           
           public class BSTNode 
                  {
                      // BSTNode constructor, sets up Node containing elem and two null links
                protected Comparable element;
                protected BSTNode left, right;
                protected BSTNode (Comparable elem) 
                              {
                     element = elem;
                     left = null;  right = null;
                }
           } 
           
           public BSTNode getRoot() 
                 {
                       // return the root of the tree
                return root;
           }
           
           public void insert (Comparable elem) 
                 {
                       // insert an elem into the tree
                int direction = 0;
                BSTNode parent = null, curr = root;
                for (;;) 
                             {
                     if (curr == null) 
                                         {
                          BSTNode ins = new BSTNode(elem);
                          if (root == null)  root = ins;
                          else if (direction < 0)
                               parent.left = ins;
                          else  parent.right = ins;
                          return;
                     } 
                     direction = elem.compareTo(curr.element);
                     if (direction == 0)  return;
                     parent = curr;
                     if (direction < 0)  curr = curr.left;
                     else  curr = curr.right;
                }
           } 
      
           public void printInOrder (BSTNode root) 
                 {
                // Print, in ascending order, all the elements in the BST subtree 
                // whose topmost node is root.
                if (root != null) 
                             {
                     printInOrder(root.left);
                     System.out.println(root.element);
                     printInOrder(root.right);
                }
           } 
      }
      THE QUESTION IS: Turn the insert method in class BST into a recursive one. You should pass the root to the method as follows.

      public void insertR (BSTNode root, Comparable elem)

      You would insert at the root if the tree is empty, otherwise you would insert in the left subtree if the element is smaller than the root element and in the right subtree if the element is larger than the root element.


      HAND IN DATE IS THURSDAY 6th December, please help! thank you for your time :)
        • 1. Re: BINARY TREE & RECURSIVE INSERT METHOD
          800282
          kt21blonde wrote:
          PLEASE HELP ME!
          I hav a final assignment for my second year at uni and i can't get it to work!
          ...
          Okay, that is just an almost exact copy of the code from:
          http://forum.java.sun.com/thread.jspa?threadID=5241109
          which was poor to begin with.

          Do you have some code of your own? If so, do you have a specific question other than "I can't get it to work", which isn't even a question.

          Show some effort please! Right now you seem like just a lazy student and there are more than enough of those around here.
          • 2. Re: BINARY TREE & RECURSIVE INSERT METHOD
            807600
            I've been trying this for the last six hours and a few hours yesterday, I'm far from a lazy student,I'm a good, hard worker who only struggles with java on my course :( yet i enjoy it... Ok, the code i completed in a seminar is as follows:
            public class BST 
            {
                 private BSTNode root;
                 
                 public static void main (String args[])
                 {
                      BST myTree = new BST ();
                      myTree.insert("lion"); // INSERTING ELEMENTS INTO THE TREE
                      myTree.insert("Fox");
                      myTree.insert("rat");  
                      myTree.printInOrder(myTree.getRoot());// PRINTS THE ELEMENTS OF THE TREE
                }                                                    // IN ALPHABETICAL ORDER.
                 
                 
                 public BST () 
                     {
                             // Construct an empty BST.
                            root = null; // STARTING THE ROOT OFF WITH A NULL VALUE
                        }
                 
                 public class BSTNode 
                    {
                            // BSTNode constructor, sets up Node containing elem and two null links
                           protected Comparable element;
                           protected BSTNode left, right;
                           protected BSTNode (Comparable elem) 
                           
                         {
                                element = elem;
                                left = null;  right = null;
                           }
                 } 
                 
                 public BSTNode getRoot() 
                
                {
                     // return the root of the tree
                      return root;
                 }
                 
                 public void insert (Comparable elem) 
                  
                  {
                     // insert an elem into the tree
                      int direction = 0;
                      BSTNode parent = null, curr = root;
                      
                      for (;;) 
                       
                       {
                                if (curr == null) 
                                               {
                                BSTNode ins = new BSTNode(elem);
                                
                                if (root == null)  root = ins;
                                
                                else if (direction < 0)
                                parent.left = ins;
                                
                                else  parent.right = ins;
                                return;
                         } 
                           direction = elem.compareTo(curr.element);
                           if (direction == 0)  return;
                           parent = curr;
                           if (direction < 0)  curr = curr.left;
                           else  curr = curr.right;
                      }
                 } 
            
                 public void printInOrder (BSTNode root) 
                       {
                      // Print, in ascending order, all the elements in the BST subtree 
                      // whose topmost node is root.
                      if (root != null) 
                                   {
                           printInOrder(root.left);
                           System.out.println(root.element);
                           printInOrder(root.right);
                      }
                 } 
            }
            We have then been asked to turn the insert method into a recursive one as part of our homework assignment. Passing the root to the method as follows:

            public void insertR (BSTNode root, Comparable elem)

            Then insert at the root if the tree is empty, otherwise insert in the left subtree if the element is smaller than the root element and in the right subtree if the element is larger than the root element.

            Thank you for your time.
            • 3. Re: BINARY TREE & RECURSIVE INSERT METHOD
              807600
              pseudocode
              public void insertR (BSTNode root, Comparable elem)
              {
                  if(mainroot is null)
                  {
                       set mainroot as root 
                       return;
                  }
              
                  if(elem < root.elem)
                         if root.left is null
                              set root.left as elem
                              return;
                         else
                              insertR(root.left, elem)
                  else
                         if root.right is null
                              set root.right as elem
                              return
                        else
                              insertR(root.right, elem)
              } 
              • 4. Re: BINARY TREE & RECURSIVE INSERT METHOD
                807600
                Thanks very much for your reply, however that method is coming up with error

                U:\DATA_STRUCTURES_YEAR_TWO\Homework3_BST\BST\BST.java:8: insertR(BST.BSTNode,java.lang.Comparable) in BST cannot be applied to (java.lang.String)
                *          myTree.insertR("lion"); // INSERTING ELEMENTS INTO THE TREE*

                Any suggestions? x
                • 5. Re: BINARY TREE & RECURSIVE INSERT METHOD
                  800282
                  kt21blonde wrote:
                  Thanks very much for your reply, however that method is coming up with error

                  U:\DATA_STRUCTURES_YEAR_TWO\Homework3_BST\BST\BST.java:8: insertR(BST.BSTNode,java.lang.Comparable) in BST cannot be applied to (java.lang.String)
                  *          myTree.insertR("lion"); // INSERTING ELEMENTS INTO THE TREE*

                  Any suggestions? x
                  You are providing one parameter while there are two needed.
                  This is what you get when copy and pasting other people's code.
                  • 6. Re: BINARY TREE & RECURSIVE INSERT METHOD
                    800282
                    kt21blonde wrote:
                    ... I'm far from a lazy student,I'm a good, hard worker ...
                    How can you say that while it is obvious that you copied the code from someone else*?
                    Christ, no, you are not lazy, you are an utter mor&#111;n!

                    * User jyswit posted this a couple of days before you in this thread: http://forum.java.sun.com/thread.jspa?threadID=5241109
                    • 7. Re: BINARY TREE & RECURSIVE INSERT METHOD
                      807600
                      A moron?? just because I wasnt born with the ability to do java from the top of my head! I came on here for help, not to be insulted! If you didn't know the answer, you only had to say! If anyone other than an asshole has any help for my problem, it would be much appreciated! The code is copied directly from my assignment which has obviously been used at various universities! :D xx
                      • 8. Re: BINARY TREE & RECURSIVE INSERT METHOD
                        800282
                        kt21blonde wrote:
                        A moron?? just because I wasnt born with the ability to do java from the top of my head!
                        No one is born with that ability. You are an utter mor&#111;n, because you stole the code from someone else. This is called plagiarism and is a serious offense!
                        \\
                        \\
                        ...
                        If anyone other than an asshole has any help for my problem, it would be much appreciated! The code is copied directly from my assignment which has obviously been used at various universities! :D xx
                        I don't believe that such a bad implementation is handed out by a teacher. I do believe the skeleton might be the same, but it is obvious that you copy and pasted it from the link I posted earlier. You even posted in that same thread you stole the code from!
                        • 9. Re: BINARY TREE & RECURSIVE INSERT METHOD
                          807600
                          OK, here is the code I completed myself after being given a skeleton by our tutor:
                          public class BST 
                          {
                               private BSTNode root;
                               
                               public static void main (String args[])
                               {
                                    BST myTree = new BST ();
                                    myTree.insert("lion"); // INSERTING ELEMENTS INTO THE TREE
                                    myTree.insert("Fox");
                                    myTree.insert("rat");  
                                    myTree.printInOrder(myTree.getRoot());// PRINTS THE ELEMENTS OF THE TREE
                              }                                                    // IN ALPHABETICAL ORDER.
                               
                               
                               public BST () 
                                   {
                                           // Construct an empty BST.
                                          root = null; // STARTING THE ROOT OFF WITH A NULL VALUE
                                      }
                               
                               public class BSTNode 
                                  {
                                          // BSTNode constructor, sets up Node containing elem and two null links
                                         protected Comparable element;
                                         protected BSTNode left, right;
                                         protected BSTNode (Comparable elem) 
                                         
                                       {
                                              element = elem;
                                              left = null;  right = null;
                                         }
                               } 
                               
                               public BSTNode getRoot() 
                              
                              {
                                   // return the root of the tree
                                    return root;
                               }
                               
                               public void insert (Comparable elem) 
                                
                                {
                                   // insert an elem into the tree
                                    int direction = 0;
                                    BSTNode parent = null, curr = root;
                                    
                                    for (;;) 
                                     
                                     {
                                              if (curr == null) 
                                                             {
                                              BSTNode ins = new BSTNode(elem);
                                              
                                              if (root == null)  root = ins;
                                              
                                              else if (direction < 0)
                                              parent.left = ins;
                                              
                                              else  parent.right = ins;
                                              return;
                                       } 
                                         direction = elem.compareTo(curr.element);
                                         if (direction == 0)  return;
                                         parent = curr;
                                         if (direction < 0)  curr = curr.left;
                                         else  curr = curr.right;
                                    }
                               } 
                           
                               public void printInOrder (BSTNode root) 
                                     {
                                    // Print, in ascending order, all the elements in the BST subtree 
                                    // whose topmost node is root.
                                    if (root != null) 
                                                 {
                                         printInOrder(root.left);
                                         System.out.println(root.element);
                                         printInOrder(root.right);
                                    }
                               } 
                          }
                          This works and returns values in alphabetical order... all I'm after is code for the insertR method. I have struggled with this the last two days and I havent come on here to argue, just seeking answers!
                          • 10. Re: BINARY TREE & RECURSIVE INSERT METHOD
                            807600
                            It would help if you followed good coding practice. For a start look in your insert(), infinite loops are a bad idea. The code underneath it will never be executed and your program will never exit without intervention. Also, use proper indentation and have only one command per line.
                            left = null;
                            right = null;
                            not
                            left = null;  right = null;
                            Read through the pseudo code above carefully, think about how best to implement it and test it before posting again. I just hope for your sake you don't have to submit a plagerism report, any detection service would pick this up.
                            • 11. Re: BINARY TREE & RECURSIVE INSERT METHOD
                              807600
                              Thanks very much for your reply, however that method is coming up with error
                              That's because it's pseudocode...
                              java:8: insertR(BST.BSTNode,java.lang.Comparable) in BST cannot be applied to (java.lang.String)
                              THIS is the error that you get from using my code verbatim?! Pretty damn strange.
                              • 12. Re: BINARY TREE & RECURSIVE INSERT METHOD
                                807600
                                here is the code I completed myself after being given a skeleton by our tutor:
                                So you wrote 4 lines of a main method, and made no attempt to implement the recursive insert?
                                all I'm after is code for the insertR
                                That's your homework assignment, though... why don't you just try to implement the pseudocode I gave you?

                                If you understand at all what I tried to get across in that post, it should be fairly straightforward.

                                If you didn't understand it at all... maybe you should have studied more this quarter.
                                • 13. Re: BINARY TREE & RECURSIVE INSERT METHOD
                                  807600
                                  I appreciate your help with the pseudocode yet it didnt work after implementation and kept returning the same error each time I tried. I CAN NOT try any more in this module, I, like all of my other students in my group, am struggling with the intensity of data structures and algorithms at university. Not that I have to explain myself to anyone on this forum, I was simply seeking a kind hearted soul to assist me with the one method I found difficult and all I got in return was nagging and insults!

                                  I'll know in future to avoid this forum to avoid intimidation and textual abuse, from what I have seen it is not only me who has been a victim to it!

                                  Maybe you should get out more and meet REAL friends not those displayed on a LCD screen??
                                  Maybe then you'l realise the importance of assistance and constructive advice.

                                  Thank you.
                                  • 14. Re: BINARY TREE & RECURSIVE INSERT METHOD
                                    807600
                                    Dont think our uni tought us about recursive methods. Anyway I got the program working. Post the recursive method with public void insertR (BSTNode root, Comparable elem) and I'll have a look.

                                    Later.
                                    1 2 Previous Next