преобразование дерева в формат newick. Джава

Question

У меня проблемы с преобразованием двоичного корневого дерева в формат newick. Полное объяснение такого формата можно найти: http://code.google.com/p/mrsrf/wiki/NewickTree

Примером формата 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. Вывод содержит слишком много узлов и фигурных скобок.

Любые комментарии для решения этой проблемы приветствуются, или даже итеративный алгоритм приветствуется

import java.util.Stack;</p> <p>public class Tree {</p> <p>....</p> <pre>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: реализовал изменение в соответствии с рекомендациями. но желаемым выходом для дерева является ((S3, (S1, S2)), (S4, S5)) где фактический результат равен (((S3, ((S3, (S1, S2)), (((S3, ((S3, (S1, S2))), (S4, S5))

Это говорит мне о наличии логических ошибок. Возможно, есть необходимость иметь флаги?

Answer 1

Возможно, у вас есть недостаток в понимании рекурсии. Вам не нужен аргумент "output". Когда вы вычисляете поддерево, вам не нужно представление предыдущих узлов. Сделай так:

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

Фиксированный код работает только для деревьев с 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;
}