Home.... | log in.... | Pub my question! | Sign-up....
Java-index >> Other Topics >> Algorithms

Reconstruction of a non-binary tree from preorder traversal

I have a non-binary tree and I have its pre-order traversal. I can distinguish between leaf and non-leaf nodes. How can I reconstruct the tree only from the pre-order traversal?
[198 byte] By [javafora@gmail.coma] at [2007-11-26 21:53:50]
«« Unit Testing in J2me application
»» How to apply patch 118833-36 on a containerized server?
# 1

> ...

> How can I reconstruct the tree only from the

> pre-order traversal?

You can't.

Let's say you have this preorder traversal = [A, B, C]

Both A

/ \

BCand

A

/

B

/

Care valid trees for that particular traversal.

prometheuzza at 2007-7-10 3:48:25 > top of Java-index,Other Topics,Algorithms...
# 2

I concur that it can't be done though I disagree with the choice of counterexample that was offered since it used B as an internal node in one case and as a leaf in the other case.

A different counterexample also showing that it can't be done. Using upper case for internal nodes and lower case for leaf.

ABcd is either

A(Bcd) - where A has arity 1 and B has arity 2

or A(Bc)d - where A has arity 2 and B has arity 1

If you know the arity of your internal nodes, then you can crack a preorder list.

marlin314a at 2007-7-10 3:48:25 > top of Java-index,Other Topics,Algorithms...
# 3
> I concur that it can't be done though I disagree with> the choice of counterexample that was offered since> it used B as an internal node in one case and as a> leaf in the other case.> > ...Yes, my example was a poor one.
prometheuzza at 2007-7-10 3:48:25 > top of Java-index,Other Topics,Algorithms...
# 4

> If you know the arity of your internal nodes, then

> you can crack a preorder list.

In fact I have the non-binary tree and I want to

find a fast and efficient way of persisting it. So,

while persisting it, I can store the arity of the

non-leaf nodes along with the pre-order traversal.

Would pre-order be the right way of doing this?

javafora@gmail.coma at 2007-7-10 3:48:25 > top of Java-index,Other Topics,Algorithms...
# 5
> > If you know the arity of your internal nodes, then> > you can crack a preorder list.> > In fact I have the non-binary tree and I want to > find a fast and efficient way of persisting it. Perhaps serialization is an option?
prometheuzza at 2007-7-10 3:48:25 > top of Java-index,Other Topics,Algorithms...
# 6

I typically use post-order traversal for serialization of trees.

If the list is kept in this format, children before parent, then the reconstruction is simplified because you have already read in and reconstructed the children before you work on assembling the parent.

Reading back a serialization works basically like this:

Create an empty stack.

Read a node from the stream (the node will typically have some value as well as its arity)

fill in the value of the node and create the slot to hold the children of this node based on its arity.

Now that you know how many children this node has, pop that many elements off the stack to fill in the child slots (fill them in from right to left if you ouput them originally from left to right)

PUSH the node you just created onto the stack.

If your output was originally a single tree, you should find that when you exhaust the input while reading it back in you will have a single node, the tree root, sitting in your stack.

so for example the expression 2+3

in post order is 2 3 +

You read in 2 and push it (arity is 0 so no children to fill in)

You read in 3 and push it (arity is 0)

You read in +,(arity is 2) create two child slots, pop 3 into the rightmost child slot, pop 2 into left most child slot, push the + node which is now a proper tree with children onto the stack.

marlin314a at 2007-7-10 3:48:25 > top of Java-index,Other Topics,Algorithms...
# 7

Thanks guys

Here I tried it with stack and recursive it see running

import java.util.Stack;

public class BinTree {

// binary tree single node class

// holding a char type

private class BTNode {

private char data;// data

private BTNode left; // left child

private BTNode right; // right child

// precondition: none

// postcondition: a single node is created with

// inData content and links to L and R

public BTNode(char inData,BTNode L,BTNode R)

{ data = inData;

left = L;

right = R;

}

}

public BTNode root; // root of the tree

// postcondition: empty BinTree is created.

public BinTree() {root = null;}

// postcondition: a single node tree is created.

public BinTree(char inData)

{ root = new BTNode(inData,null,null);}

// postcondition: a new binary tree is created

// with the specified root content and with the

// links to the given left and right subtrees

public BinTree(char inData,BinTree A,BinTree B)

{ root = new BTNode(inData,A.root,B.root); }

publicBinTree buildTree(String in){

Stack<Character> temp= new Stack<Character>();

int k=0;

System.out.println(in.length());

for(int i=1;(i<in.length());i++)

{

if ((in.charAt(i)=='(')){temp.push('(');}

if (in.charAt(i)==')'){

temp.pop();

if (temp.isEmpty()==true){break;}

}

k=i+1;

}

int b=1;

if (in.length()>0){

BinTree A = new BinTree(in.charAt(b),buildTree(in.substring(2,k)),buildTree(in.substring(k+1,(in.length()-1))));

return A;}

else{

return null;}

}}

dima7amdolilaha at 2007-7-10 3:48:25 > top of Java-index,Other Topics,Algorithms...
# 8
The reconstruction you want is all based on the string format that you input. By adding a more complex string structure, you can reform and type tree. Code is here (look for my post - near the bottom currently): http://forum.java.sun.com/thread.jspa?threadID=5169403&tstart=0
ArikArikArika at 2007-7-10 3:48:25 > top of Java-index,Other Topics,Algorithms...
Other Topics
Algorithms

Other Topics New Topic

Other Topics Hot Topic

Other Topics

All Classified