Geek Answers Handbook

Convert a tree to a new format. Java

I'm having problems converting the binary root tree to the new format. A full description of this format can be found: http://code.google.com/p/mrsrf/wiki/NewickTree

An example of a new format will look like this:

for a T tree such as http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic8/images/completetreetwo.gif the new expression would be: (((8,9), (10,11) ), ((12,13), (14,15)))

the inner node will become a comma, while the leaves will be preserved.

such trees have internal nodes that will always have 2 children.

I have a recursion problem to come up with this new format. The result contains too many nodes and braces.

Any comments to solve this problem are welcome or even an iterative algorithm is welcome

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 {
         return root.getSeq ();
     }

}

// edit: implemented the change in accordance with the recommendations. but the desired result for the tree is ((S3, (S1, S2)), (S4, S5)) (S3, S2)), (S4, S5))

(S3, S2), (S3, S2)

This tells me that there are logical errors. Perhaps there is a need to have flags?

0
source share
2 answers

You may have a lack of understanding of recursion. You do not need the argument "output". When you compute a subtree, you do not need to represent the previous nodes. Do it like this:

 public String inOrderNewick(Node root) throws ItemNotFoundException { if (root.hasChild()) { String output = ""; output += "("; output += inOrderNewick(root.child1); output += ","; output += inOrderNewick(root.child2); output += ")"; return output; } else { return root.getSeq(); } }
+1
source

Fixed code only works for trees of 0 or 2 children per node.

This should work for arbitrary binary trees + add branch distance parameter:

 BinaryTree left; BinaryTree right; double ldist; double rdist; String label; //... public String toNewick(){ if(right==null && left==null){ return label.toString(); } String output = "("; if(right!=null){ output+=right.toNewick()+":"+rdist; } if(right!=null && left!=null){ output+=","; } if(left!=null){ output+=left.toNewick()+":"+ldist; } output += ")"; return output; }
0
source

More articles:


All Articles