Page 1 of 2 12 LastLast
Results 1 to 20 of 24
  1. #1
    sAntA199 is offline Member
    Join Date
    Nov 2009
    Posts
    18
    Rep Power
    0

    Default making a general tree

    I was wondering if anybody here had any suggestions for making a general tree when given the preorder and postorder strings. all the data in the tree are simple characters.

    im having trouble finding a way to go through this so if anybody here has done it before please help me out

  2. #2
    xcallmejudasx's Avatar
    xcallmejudasx is offline Senior Member
    Join Date
    Oct 2008
    Location
    Houston, TX & Flint, MI
    Posts
    609
    Rep Power
    6

    Default

    Do you need help with the logic or the code right now?

    You're going to need to create a node class with parents and children so that you can link each node to each other and go from there.
    Liberty has never come from the government.
    Liberty has always come from the subjects of government.
    The history of liberty is the history of resistance.
    The history of liberty is a history of the limitation of governmental power, not the increase of it.

  3. #3
    sAntA199 is offline Member
    Join Date
    Nov 2009
    Posts
    18
    Rep Power
    0

    Default

    i have a node class and everything set up and working, i just need help with the logic for putting the tree together from the two strings

    the preorder is tambcde and post is abcdmet
    so the tree looks like:
    t
    a m e
    b c d

    if you can figure that out

  4. #4
    xcallmejudasx's Avatar
    xcallmejudasx is offline Senior Member
    Join Date
    Oct 2008
    Location
    Houston, TX & Flint, MI
    Posts
    609
    Rep Power
    6

    Default

    I don't understand what you mean with
    t
    a m e
    b c d
    you're tree is out of order.

    ----D----
    --B---M--
    A--C-E--T

    is what it should look like(unless I misunderstood your question)

    The easiest way to do it is to sort your string first and then start adding children. It will be alot simpler that way as opposed to just putting the string in verbatim and then doing branch rotations.
    Liberty has never come from the government.
    Liberty has always come from the subjects of government.
    The history of liberty is the history of resistance.
    The history of liberty is a history of the limitation of governmental power, not the increase of it.

  5. #5
    sAntA199 is offline Member
    Join Date
    Nov 2009
    Posts
    18
    Rep Power
    0

    Default

    sorry that got messed up its:

    -------T--------
    -A----M-----E-
    ----B-C-D-----

    and its not a binary tree the m has 3 children

  6. #6
    xcallmejudasx's Avatar
    xcallmejudasx is offline Senior Member
    Join Date
    Oct 2008
    Location
    Houston, TX & Flint, MI
    Posts
    609
    Rep Power
    6

    Default

    oh alright ya I know what youre talking about now. I'll have to check my notes from my algorithms course when I get home(I don't even remember what the 3child tree was called) but I know you fill up the highest order until you hit 3 then you turn one of those into a child, fill up again, spit out a child into the previous childs node, etc etc etc.

    Sorry for the poor explanation but I'll have to look into it more before I can be sure exactly how it works.
    Liberty has never come from the government.
    Liberty has always come from the subjects of government.
    The history of liberty is the history of resistance.
    The history of liberty is a history of the limitation of governmental power, not the increase of it.

  7. #7
    xcallmejudasx's Avatar
    xcallmejudasx is offline Senior Member
    Join Date
    Oct 2008
    Location
    Houston, TX & Flint, MI
    Posts
    609
    Rep Power
    6

    Default

    2-3 tree - Wikipedia, the free encyclopedia

    I'm sure you've already checked that but if you haven't give it a look.
    Liberty has never come from the government.
    Liberty has always come from the subjects of government.
    The history of liberty is the history of resistance.
    The history of liberty is a history of the limitation of governmental power, not the increase of it.

  8. #8
    sAntA199 is offline Member
    Join Date
    Nov 2009
    Posts
    18
    Rep Power
    0

    Default

    well its not a trinary tree either its a general tree meaning you dont know ahead of time how many children a tree will have.

    the only reason i know the tree looks like that is because it was given ahead of time. I already have a method that zips the tree into the preorder and postorder strings, now i need to figure out how to do it in reverse

  9. #9
    xcallmejudasx's Avatar
    xcallmejudasx is offline Senior Member
    Join Date
    Oct 2008
    Location
    Houston, TX & Flint, MI
    Posts
    609
    Rep Power
    6

    Default

    you mean unzip it? Post the code for how you zipped it. undoing it should be as simple as swapping around a few loop conditions and changing start and end positions.
    Liberty has never come from the government.
    Liberty has always come from the subjects of government.
    The history of liberty is the history of resistance.
    The history of liberty is a history of the limitation of governmental power, not the increase of it.

  10. #10
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    Post the code for how you zipped it. undoing it should be as simple as swapping around a few loop conditions and changing start and end positions.

    I doubt if it's that easy. For a couple of reasons.

    First because both the preorder and postorder sequences are necessary to reconstruct the original tree. Consequently the code for neither on their own can be "reversed".

    Secondly because this is not really a question about code. It's a question about how to come up with an algorithm.

    @OP: The usual way of attacking such a question is to ask oneself "How would I do this by hand?". In other words suppose you didn't have a computer and were just given the pre and post ordered sequences: how would you use that information to reconstruct the original tree?

    How do you know that the tree is rooted at T? (easy)
    How do you know that A is a child of T? ( just as easy)
    How do you know that M is a sibling of A and not a child?
    How can you spot the elements of the subtree rooted at M within the postordered sequence?

  11. #11
    sAntA199 is offline Member
    Join Date
    Nov 2009
    Posts
    18
    Rep Power
    0

    Default

    the parts with all the //////// are what i dont get. the first one im not sure if i can even do. I dont see how to make the different nodes without knowing how many there are ahead of time.
    the second and third are cases for recursion but i'm still having problems with that too


    Java Code:
    public Tree<E> unzip (String zippedTree)
      {
            int half = zippedTree.length() / 2;
            ArrayList top2 = new ArrayList();
            ArrayList mid2 = new ArrayList();
            ArrayList bot2 = new ArrayList();
            
            String pre = zippedTree.substring(0, half);
            String post = zippedTree.substring(half + 1);
            //System.out.println(pre + " " + post);
            
            return unzippedTree;
           
      }
      private Tree unzip(String pre, String post, Node < E > node)
      {
            for (int i = 0; i < pre.length(); i++)
                {
                    Tree<Character> (pre.charAt(i))Tree = new Tree<Character>    (pre.charAt(i));     ////////////////////////////
                }
            
            
    
            if(pre == null || post == null)
            {
                System.err.println("There is an empty tree.");
                return null;
            }
            
            if (pre.charAt(0) == post.charAt(post.length())
            {
                top2.add(root2)  ////////////////////////
                unzip(pre.substring(1), post.substring(0, post.length - 1));
            }
            if (pre.charAt(0) != post.charAt(post.length())//////////////////
            {
                unzip(pre.substring(1), post.substring(0, post.length - 1));
            }
            
            
            
            
      }

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

    Default

    Quote Originally Posted by sAntA199 View Post
    I was wondering if anybody here had any suggestions for making a general tree when given the preorder and postorder strings. all the data in the tree are simple characters.
    You can't reconstruct a tree uniquely given the preorder and postorder traversals. You need the infix and one of the other traversals to do that.

    kind regards,

    Jos

  13. #13
    sAntA199 is offline Member
    Join Date
    Nov 2009
    Posts
    18
    Rep Power
    0

    Default

    well its gotta be possible because thats what the lab is asking me to do

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

    Default

    Quote Originally Posted by sAntA199 View Post
    well its gotta be possible because thats what the lab is asking me to do
    That's not reasoning, that's religion. Here's a counter example: preorder == AB and postorder == BA. Two different trees can be constructed: A as the root and B either as a left or right child.

    I think you should reread your assignment text.

    kind regards,

    Jos

  15. #15
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    Left child/right child? These aren't binary trees.

    I do think you need the condition that the characters displayed in the pre- and post-order sequences are unique. (well, that's sufficient but not necessary)

    [Edit]

    @OP JosAH knows a helluva lot more than me about this stuff.

    However, assuming your tree nodes have a character value and a list of zero or more children nodes, I can reconstruct the tree knowing the sequences formed by
    (a) Listing the value of a node followed by those of its children (preorder)
    and
    (b) Listing the value of a node's children followed by that of the node (postorder)

    I arrived at that point by answering the questions I posed to you. Scribbling some pictures. And drinking some coffee.

    I like this question, by the way. It makes you think.
    Last edited by pbrockway2; 12-03-2009 at 08:47 PM.

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

    Default

    Quote Originally Posted by pbrockway2 View Post
    Left child/right child? These aren't binary trees.

    I do think you need the condition that the characters displayed in the pre- and post-order sequences are unique. (well, that's sufficient but not necessary)
    Even then it is not always possible to uniquely reconstruct a tree (see my example in my previous reply). It's a classic problem in linguistics that can't be solved (and in many other disciplines too ;-)

    kind regards,

    Jos

  17. #17
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    Doesn't preorder=AB postorder=BA uniquely specify the tree rooted at A with a single (childless) child B?

    Or am I missing something about this problem?

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

    Default

    Quote Originally Posted by pbrockway2 View Post
    Doesn't preorder=AB postorder=BA uniquely specify the tree rooted at A with a single (childless) child B?

    Or am I missing something about this problem?
    That's the problem exactly: B is a child of A but we can't tell which one (a left child or a right child) so in general a tree construction given the prefix (AB) and postfix (BA) traversal is not possible.

    kind regards,

    Jos

  19. #19
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    OK. Yes: if the children have other qualities (handedness, colour, etc) that is not fully described by the orderings then you're screwed and the question motivating this thread makes no sense.

    What I meant by "However, assuming your tree nodes have a character value and a list of zero or more children nodes..." in reply #17 was that this description fully described what it was to be a tree node.

    In code, my nodes were like

    Java Code:
    class Node {
        char data;
        List<Node> children;
    
        // static factory to return a node with given data and parent
        // methods to produce pre- and post-sequences for the subtree
        // rooted at this node.
    }
    Specifically if children.size()==1 then that child is just the child: it is neither left, right, puce etc.
    Last edited by pbrockway2; 12-03-2009 at 09:28 PM.

  20. #20
    xcallmejudasx's Avatar
    xcallmejudasx is offline Senior Member
    Join Date
    Oct 2008
    Location
    Houston, TX & Flint, MI
    Posts
    609
    Rep Power
    6

    Default

    In other words a node has no identity towards left/right until it obtains a sibling to compare itself too. Sorta like an incestuous family tree that never branches out and just keeps going straight down
    Liberty has never come from the government.
    Liberty has always come from the subjects of government.
    The history of liberty is the history of resistance.
    The history of liberty is a history of the limitation of governmental power, not the increase of it.

Page 1 of 2 12 LastLast

Similar Threads

  1. Replies: 4
    Last Post: 01-13-2011, 05:30 PM
  2. Creating a Tree and then saving the Tree
    By jackmatt2 in forum New To Java
    Replies: 0
    Last Post: 08-22-2009, 12:51 PM
  3. Issue with TreeViewer and JPopupMenu and components in general
    By xcallmejudasx in forum Advanced Java
    Replies: 1
    Last Post: 11-13-2008, 11:43 PM
  4. General Discussion on Abstract
    By sanjeevtarar in forum Advanced Java
    Replies: 15
    Last Post: 05-06-2008, 06:16 AM
  5. How to set General options in NetBeans IDE
    By JavaForums in forum NetBeans
    Replies: 0
    Last Post: 08-02-2007, 12:11 PM

Posting Permissions

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