converting a Tree to newick format. java
- by Esmond
I'm having problems converting a binary rooted tree to newick format.
The full explanation for such a format can be found: http://code.google.com/p/mrsrf/wiki/NewickTree
An example of a newick format would be as follows:
for a tree T such as http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic8/images/completetreetwo.gif
the newick representation would be: (((8,9),(10,11)),((12,13),(14,15)))
the internal node will become the commas while the leaves will be retained.
such trees have internal nodes which will always have 2 children.
I have a problem using recursion to come out with this newick format.
The output contains far too many nodes and braces.
Any comments to resolve this problem is appreciated or even an iterative algorithm would be welcomed
import java.util.Stack;
public class Tree {
....
public String inOrderNewick(Node root, String output) throws ItemNotFoundException {
if (root.hasChild()) {
output += "(";
output += inOrderNewick(root.child1, output);
output += ",";
output += inOrderNewick(root.child2, output);
output += ")";
return output;
} else {
output += root.getSeq();
return output;
}
}
}
