Results 1 to 9 of 9
  1. #1
    RllyNew2Java is offline Member
    Join Date
    Dec 2009
    Posts
    1
    Rep Power
    0

    Default Ttp

    Java Code:
    [color=white]000000000[/color]9
    [color=white]00000000[/color]/[color=white]0[/color]\
    [color=white]0000000[/color]11[color=white]0[/color]34
    [color=white]0000000[/color]/[color=white]000[/color]/[color=white]0[/color]\
    [color=white]000000[/color]12[color=white]00[/color]32[color=white]0[/color]23
    [color=white]0000000[/color]\
    [color=white]0000000[/color]13
    Last edited by RllyNew2Java; 12-25-2009 at 04:26 PM.

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,541
    Blog Entries
    7
    Rep Power
    20

    Default

    Can you please tell in ordinary words what exactly that transformation is about? I, for one, don't understand it from your example.

    kind regards,

    Jos

  3. #3
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,541
    Blog Entries
    7
    Rep Power
    20

    Default

    Correct me if I'm wrong:

    - you don't change the structure of the (binary?) tree, you just swap the payload of the nodes;
    - you reverse every path (the payload of the nodes) starting from the rightmost path.

    Am I correct?

    kind regards,

    Jos

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,541
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by RllyNew2Java View Post
    Yes Exactly !! Structure is the same, only values of the nodes changes.
    Ok, lemme think ... use an ordinary depth first traversal but pass a list of some sort to store the current path from the root to a leaf; when a leaf is reached reverse the payloads in all the nodes in the list; something like this:

    (warning: untested code ahead)

    Java Code:
    public void traverse(Node node, List<Node> path) {
       if (node != null) { // if we haven't fallen off the tree
          list.add(node);
          if (node.left == null && node.right == null) // it's a leaf
             swapPayloads(path);
          else {
             traverse(node.right, path); // right first, left last
             traverse(node.left, path);
          }
          list.remove(list.size()-1); // remove last node from the path
       }
    }
    The swap method looks like this:

    Java Code:
    public void swapPayloads(List<Node> path) {
       for (int i= 0, j= path.size(); i < --j; i++) {
          T payload= path.get(i).payload;
          path.get(i).payload= path.get(j).payload;
          path.get(j).payload= payload;
       }
    }
    I think this should do it (give or take a few typos ;-) You start the entire shebang like this:

    Java Code:
    traverse(root, new ArrayList<Node>());
    Note that we don't (and can't) use that list afterwards anymore (it is empty again anyway).

    kind regards,

    Jos

  5. #5
    tim's Avatar
    tim
    tim is offline Senior Member
    Join Date
    Dec 2007
    Posts
    435
    Rep Power
    7

    Default

    Hi RllyNew2Java. ;)

    I've created a solution for your problem by implementing simple binary tree and using a stack to do the reversals.
    The example program
    Java Code:
    package trees;
    
    public class Main {
        public static void main(String[] args) {
            Node root = new Node(23);
            root.setLeft(new Node(12)); 		
            root.setRight(new Node(34)); 		
            root.getLeft().setLeft(new Node(11)); 		
            root.getLeft().getLeft().setRight(new Node(9)); 				
            root.getRight().setLeft(new Node(13)); 		
            root.getRight().setRight(new Node(32));
            [COLOR="Navy"]Stack<Node> leaves = new Stack<Node>();
            root.leavesRightToLeft(leaves);
            for (Node next : leaves) {
                next.reverse();
            }[/COLOR]
            root.inOrder();
        }
        
    }
    The binary tree
    Java Code:
    package trees;
    
    public class Node<T> {
        protected Node<T> left = null;
        protected Node<T> right = null;
        protected Node<T> parent = null;
        protected T value;
        protected int level = 0;
        
        public Node() {
            
        }
        
        public Node(Node<T> left, Node<T> right, T value) {
            this.setLeft(left);
            this.setRight(right);
            this.setValue(value);
        }
        
        public Node(T value) {
            this.setValue(value);
        }
        
        public void inOrder() {
            if (getLeft() != null) getLeft().inOrder();
            for (int i = 1; i <= level; i++) System.out.print(" ");
            System.out.println(getValue());
            if (getRight() != null) getRight().inOrder();
        }
        
    [COLOR="Navy"]    public void leavesRightToLeft(Stack<Node<T>> stack) {
            if (right != null) right.leavesRightToLeft(stack);
            if (left != null) left.leavesRightToLeft(stack);
            if (left == null && right == null) stack.push(this);
        }
        
        public void reverse() {
            // we'll use a stack for reversing
            Stack<T> stack = new Stack<T>();
            // traverse to the root and push all values onto the stack
            Node<T> finger = this;
            while (finger != null) {
                stack.push(finger.value);
                finger = finger.parent;
            }
            // traverse to the root and pop all values from the stack
            finger = this;
            while (finger != null) {
                finger.value = stack.pop();
                finger = finger.parent;
            }
        }[/COLOR]
    
        public Node getLeft() {
            return left;
        }
    
        public void setLeft(Node<T> left) {
            this.left = left;
            left.setParent(this);
            left.level = level + 1;
        }
    
        public Node getRight() {
            return right;
        }
    
        public void setRight(Node<T> right) {
            this.right = right;
            right.setParent(this);
            right.level = level + 1;
        }
    
        public Node getParent() {
            return parent;
        }
    
        public void setParent(Node<T> parent) {
            this.parent = parent;
        }
    
        public T getValue() {
            return value;
        }
    
        public void setValue(T value) {
            this.value = value;
        }
        
        public String toString() {
            return value.toString();
        }
    }
    A simple stack
    Java Code:
    package trees;
    
    import java.util.*;
    
    public class Stack<T> extends Vector<T> {
        public Stack() {
        }
        
        public void push(T value) {
            add(value);
        }
        
        public T pop() {
            return remove(size() - 1);
        }
        
        public T peek() {
            return get(size() - 1);
        }
    }
    Use this opportunity to learn. This is the purpose of studying algorithms and data structures. Plagiarize at own loss.
    Last edited by tim; 12-22-2009 at 11:15 PM.
    Eyes dwelling into the past are blind to what lies in the future. Step carefully.

  6. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,541
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by RllyNew2Java View Post
    I'm having problems with the swap method, I don't understand the To-Do part in the for loop.... What is
    Java Code:
     T payload= path.get(i).payload;
    and the .payload ??
    A node has a left and right pointer and a field named 'payload' which has a type T (I don't know anything about its type). That little method reverses the payloads for all the nodes in that list. So if the payloads were A, B, C (in that order), the payloads will be C, B, A after the reversal.

    kind regards,

    Jos

  7. #7
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,541
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by tim View Post
    I've created a solution for your problem by implementing simple binary tree and using a stack to do the reversals.
    You algorithm fills a stack from scratch each time you reach a leaf node; that is quite inefficient for, say, neighbouring leafs (the stack will be the same except for the last entry). My version simply adjusts a stack when necessary (it is passed as an additional parameter to the recursive traversal method). Your version also needs a parent pointer per node.

    kind regarards,

    Jos

  8. #8
    tim's Avatar
    tim
    tim is offline Senior Member
    Join Date
    Dec 2007
    Posts
    435
    Rep Power
    7

    Default

    Quote Originally Posted by JosAH View Post
    You algorithm fills a stack from scratch each time you reach a leaf node; that is quite inefficient for, say, neighbouring leafs (the stack will be the same except for the last entry). My version simply adjusts a stack when necessary (it is passed as an additional parameter to the recursive traversal method). Your version also needs a parent pointer per node.

    kind regarards,

    Jos
    I see. :) Didn't read your solution before hand. Was still fun to solve! :p
    Eyes dwelling into the past are blind to what lies in the future. Step carefully.

  9. #9
    tim's Avatar
    tim
    tim is offline Senior Member
    Join Date
    Dec 2007
    Posts
    435
    Rep Power
    7

    Default

    Quote Originally Posted by RllyNew2Java View Post
    Thanks alot for your help, I learned alot from both solutions :) ...
    It's our pleasure RllyNew2Java. ;)
    Eyes dwelling into the past are blind to what lies in the future. Step carefully.

Similar Threads

  1. Need help with Trees...(8-puzzle)
    By ventrue in forum New To Java
    Replies: 2
    Last Post: 03-23-2009, 11:04 PM
  2. Traversing a JTabbedPane
    By Inks in forum AWT / Swing
    Replies: 12
    Last Post: 03-11-2009, 05:15 AM
  3. Help With Tournament Trees
    By wiggsfly in forum New To Java
    Replies: 2
    Last Post: 10-26-2008, 09:38 PM
  4. Replies: 1
    Last Post: 03-25-2008, 05:06 AM
  5. Traversing a directory
    By Java Tip in forum Java Tip
    Replies: 0
    Last Post: 01-14-2008, 09:33 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •