将Tree转换为newick格式。 java

我在将二进制固定树转换为newick格式时遇到了问题。为这样的格式的完整的说明，可以发现：http://code.google.com/p/mrsrf/wiki/NewickTree 将Tree转换为newick格式。 java

一个newick格式的一个例子是如下：

用于树T如http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic8/images/completetreetwo.gif 的newick表示为：（（（8- ，（9），（10,11）），（（12,13），（14,15）））

内部节点将成为逗号，而树叶将被保留。

这样的树有内部节点，总是有2个孩子。

我有一个问题，使用递归出来这个newick格式。输出包含太多节点和大括号。

解决这个问题的任何意见表示赞赏，甚至迭代算法将受到欢迎

进口java.util.Stack中;

 公共类树{
 ....

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

}

//编辑：实现的变化通知。（（S3，（S1，S2）），（S4，S5））其中实际输出为（（S3，（S1，S2）），（S3，（（S3，（S1，S2）），（S4，S5））

这告诉我，有逻辑错误。或许有必要有标志？

来源

2010-04-10 Esmond

也许你有在理解递归的一个漏洞不需要“输出”的说法当你计算一个子树，你不需要先前节点的代表作出这样的：。

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

来源

2010-04-10 08:24:53

感谢，这并采取额外的焦炭下来的数量，但仍然有一些逻辑错误。（S3，（S1，S2）），（（（（S1，S2）），（S4，S5））的树的输出结果为。 S3，（（S3，（S1，S2）），（S4，S5））我需要一些标记来处理这个问题吗？ – Esmond 2010-04-10 08:54:54

你确定树被正确构建吗？ – 2010-04-10 09:06:27

是一个调用树的大小返回9有5个叶子和4个内部节点一个序列遍历返回S3 r2 S1 r2 S2 r4 S4 r3 S5 – Esmond 2010-04-10 09:13:45

固定代码仅适用于0的树或每个节点2个孩子。

这应该任意的二进制树+工作增加了分支距离参数：

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

来源

2017-02-14 17:33:12

将Tree转换为newick格式。 java

回答

相关问题