10 Replies Latest reply on Mar 18, 2007 3:29 PM by JosAH

    Binary tree per levels

    807606
      I must make a method that takes the variable "item" and put it in a string, for each element of the binary tree, but per levels..for example:
                    1
         2     3               6
      5                                4
      must return this string: 1 , 2 , 3 , 6 , 5 , 4

      The tree is something like:
      public class BinTree{
            private Node root;
      
            public class Node{
                  public Node left;
                  public Node right;
                  public int item;
           }
      }
      Thank you very much :)
        • 1. Re: Binary tree per levels
          800282
          ...
          Thank you very much :)
          For what?
          You haven't asked a question!
          • 2. Re: Binary tree per levels
            807606
            Sorry, I didn't specify: I can use recursion, but in this case I don't know how to do it "per levels"..can someone help me? Also if you don't write the method, just to tell me how to go through the tree in this case. Thanks
            • 3. Re: Binary tree per levels
              800282
              Sorry, I didn't specify: I can use recursion,
              Level order traversals are normally performed using a queue.

              but in this case I don't know how to do it "per levels"..can
              someone help me?
              Sure: use a queue and try to do it first on a pice of paper.

              Also if you don't write the method,
              I won't. ; )
              What would you learn from that? Perhaps a little, but you'll learn far more by doing it yourself.

              just to tell me how to go through the tree in this
              case. Thanks
              Here's some pseudo code:
              LEVELORDER(root)
                queue.enqueue(root)
                WHILE queue not empty
                  n = queue.dequeue()
                  IF n.left  != null -> queue.enqueue(n.left )
                  IF n.right != null -> queue.enqueue(n.right)
                END WHILE
              END LEVELORDER
              And an example. Take the following tree:
                   5
                  / \
                 /   \
                3     8
              / \   / \
              1   4 6   9
              No apply that pseudo code:
              queue = new queue
              queue.enqueue(5)

              while(queue is not empty) {

                n = queue.dequeue() = 5
                n.left  != null, so queue.enqueue(3)
                n.irght != null, so queue.enqueue(8)
                (queue is now [3,8])

                n = queue.dequeue() = 3
                n.left  != null, so queue.enqueue(1)
                n.irght != null, so queue.enqueue(4)
                (queue is now [8,1,4])

                n = queue.dequeue() = 8
                n.left  != null, so queue.enqueue(6)
                n.irght != null, so queue.enqueue(9)
                (queue is now [1,4,6,9])

                n = queue.dequeue() = 1
                n.left  == null
                n.irght == null
                (queue is now [4,6,9])

                n = queue.dequeue() = 4
                n.left  == null
                n.irght == null
                (queue is now [6,9])

                n = queue.dequeue() = 6
                n.left  == null
                n.irght == null
                (queue is now [9]) 

                n = queue.dequeue() = 9
                n.left  == null
                n.irght == null
                (queue is now [])

                queue is empty, end while.
              }
              As you can see, the items are dequeued in the following order: 5, 3, 8, 1, 4, 6, 9.
              Good luck.
              • 4. Re: Binary tree per levels
                807606
                I didn't know anything about the class "Queue"...
                I don't understand why if I write "Queue queue = new Queue();" I obtain the error "queue is abstract cannot be instantiated"...so I can't make operations like queue.dequeue() !
                I searched in Internet but I didn't understand what happens. Can someone help me, please?


                Thanks prometheuzz for your big help!

                Message was edited by:
                -Marco-
                • 5. Re: Binary tree per levels
                  800282
                  A java.util.Queue is an interface:
                  http://java.sun.com/j2se/1.5.0/docs/api/java/util/Queue.html
                  so, you cannot instantiate it like this:
                  Queue queue = new Queue();
                  and a java.util.LinkedList is an implementation of that interface:
                  http://java.sun.com/j2se/1.5.0/docs/api/java/util/LinkedList.html

                  So, what you can do is this:
                  import java.util.Queue;
                  import java.util.LinkedList;
                  
                  // ...
                  
                  yourMethod() {
                    Queue<Node> queue = new LinkedList<Node>();
                    // ...
                  }
                  Now you can call all methods defined in the Queue interface on your queue reference.
                  Note that the Queue interface does not have enqueue(...) and dequeue() methods but offer(...) and poll().

                  Good luck.
                  • 6. Re: Binary tree per levels
                    807606
                    I've written this:
                     
                    public String toString(Node root){
                    
                       if (root== null)
                         return "";  // There is nothing to print in an empty tree.
                    
                        Queue queue = new LinkedList();
                        queue.offer(root);
                         while ( queue.isEmpty() == false ) {
                                  node = (Node)queue.poll();
                                 System.out.println( node.label );
                                 if ( node.left != null )              queue.offer( node.left );
                                 if ( node.right != null )           queue.offer( node.right );
                              }
                    
                              return "";
                    }
                    I'll put the memorization in the string when I'll make this part work...
                    I've 2 problems:
                    1) I used a casting operation to transform the queue.poll() result in a BinNode type, do you think it should work?
                    2) I receive the error: "MyTree.java uses unchecked or unsafe operations"..which unsafe operation have I used?

                    Message was edited by:
                    -Marco-
                    • 7. Re: Binary tree per levels
                      JosAH
                      I've 2 problems:
                      1) I used a casting operation to transform the queue.poll() result in a
                      BinNode type, do you think it should work?
                      2) I receive the error: "MyTree.java uses unchecked or unsafe
                      operations"..which unsafe operation have I used?
                      A bit of generics sprinkled in never hurt:
                      Queue<Node> queue= new LinkedList(Node);
                      ...
                      node= queue.poll(); // no cast needed anymore
                      kind regards,

                      Jos
                      • 8. Re: Binary tree per levels
                        807606
                        Great, it's working now ^^
                        I?m sorry but I thought that the <> were just to show some parameters...I didn't know it was an instruction! Now I'm going to study this thing, thanks again :)
                        • 9. Re: Binary tree per levels
                          JosAH
                          Of course I made a few typos again; I wanted to type this:
                          Queue<Node> queue= new LinkedList<Node>();
                          kind regards,

                          Jos
                          • 10. Re: Binary tree per levels
                            JosAH
                            I?m sorry but I thought that the <> were just to show
                            some parameters...
                            Those things between the angular brackets are parameters; they're
                            type parameters to be more exact. Read all about it in the generics
                            tutorials; erm ... what's that link again? Google, google, got it:

                            http://java.sun.com/j2se/1.5/pdf/generics-tutorial.pdf

                            kind regards,

                            Jos