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

how can i construct the shape of a binary tree from its preOrder traversal

can someone give me the algorithms on constructing the shape of a binary tree from its preOrder traversal.
[113 byte] By [ybbesta] at [2007-10-2 3:14:06]
«« how to compile servlets
»» How to input a string?
# 1
You can't; you need at least two out of three of the pre/in/post ordertraversals to be able to reconstruct a tree. Or additional information(like the 'arity' of some node types) must be available.kind regards,Jos
JosAHa at 2007-7-15 21:41:13 > top of Java-index,Other Topics,Algorithms...
# 2

You could do a very easy HTML output.

The following is linear output.

/**

* Outputs an HTML file representation of a binary tree.

*/

public class PreOrderTraversalBinTree {

private String expression;

public PreOrderTraversalBinTree(String expression) {

this.expression = expression;

System.out.println("<html><head><title>" + expression + "</title></head><body>");

System.out.println("<h2>" + expression + "</h2>");

represent(expression);

System.out.println("</body></html>");

}

/**

* @return the number of consumed characters.

*/

private int represent(String expression) {

if (expression.length() == 0)

return 0;

String node = expression.substring(0, 1);

if ("+*-/".indexOf(node) == -1) {

// Constant:

System.out.println(node);

return 1;

}

// Binary operator:

expression = expression.substring(1);

System.out.println("<table border=\"0\">");

System.out.println("<tr><th colspan=\"2\">" + node + "</th></tr>");

System.out.println("<tr><th>");

int lhs = represent(expression);

expression = expression.substring(lhs);

System.out.println("</th><th>");

int rhs = represent(expression);

System.out.println("</th></tr>");

System.out.println("</table>");

return 1 + lhs + rhs;

}

public static void main(String[] args) {

new PreOrderTraversalBinTree("+*34+/567");

}

}

joop_eggena at 2007-7-15 21:41:13 > top of Java-index,Other Topics,Algorithms...
Other Topics
Algorithms

Other Topics New Topic

Other Topics Hot Topic

Other Topics

All Classified