將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

回答

相關問題