convertir un arbre au format newick. java

Question

J'ai des problèmes pour convertir un arbre binaire enraciné au format newick. L'explication complète pour un tel format peut être trouvé: http://code.google.com/p/mrsrf/wiki/NewickTree

Un exemple d'un format Newick serait la suivante:

pour un arbre T tel que http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic8/images/completetreetwo.gif la représentation Newick serait: (((8 , 9), (10,11)), ((12,13), (14,15))

le nœud interne deviendra la virgule tandis que les feuilles seront conservées.

ces arbres ont des nœuds internes qui auront toujours 2 enfants.

J'ai un problème en utilisant la récursivité pour sortir avec ce format newick. La sortie contient beaucoup trop de nœuds et d'accolades.

Tous les commentaires pour résoudre ce problème est apprécié ou même un algorithme itératif seraient accueillis

java.util.Stack d'importation;

Arbre public class {

....

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: mis en œuvre le changement comme conseillé. mais la sortie désirée pour un arbre est ((S3, (S1, S2)), (S4, S5)) où la sortie réelle est (((S3, ((S3, (S1, S2)), (((S3, ((S3, (S1, S2)), (S4, S5))

Cela me dit qu'il ya des erreurs logiques. peut-être il est nécessaire d'avoir des drapeaux?

Answer 1

peut-être que vous avez . une faille dans récursion compréhension vous n'avez pas besoin de l'argument « de sortie » Lorsque vous calculez une sous-arborescence vous n'avez pas besoin de la représentation des noeuds précédents Faites comme ceci:..

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

Answer 2

le code fixe est ne travaillant que pour les arbres de 0 ou 2 enfants par noeud.

Cela devrait fonctionner pour le paramètre des arbres binaires arbitraires + ajoute la distance de branche:

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