making a general tree

[sAntA199]

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

[xcallmejudasx]

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.

[sAntA199]

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

[xcallmejudasx]

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.

[sAntA199]

sorry that got messed up its:

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

and its not a binary tree the m has 3 children

[xcallmejudasx]

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.

[xcallmejudasx]

2-3 tree - Wikipedia, the free encyclopedia

I'm sure you've already checked that but if you haven't give it a look.

[sAntA199]

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

[xcallmejudasx]

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.

[pbrockway2]

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?

[sAntA199]

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

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));
        }
        
        
        
        
  }

[JosAH]

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

[sAntA199]

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

[JosAH]

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

[pbrockway2]

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.

[JosAH]

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

[pbrockway2]

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?

[JosAH]

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

[pbrockway2]

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

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.

[xcallmejudasx]

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