python-3.x - 如何使用 Python 将二叉树转换为 Newick 树？

Question

我创建了一个具有以下结构的 Tree 对象：

class Tree:

    def __init__(self, data=None):
        self.data = data
        self.left_child = None
        self.right_child = None

该对象的一个​​实例是：

tree = Tree("A")
tree.left_child = Tree("B")
tree.right_child = Tree("C")
tree.left_child.left_child = Tree("D")
tree.left_child.right_child = Tree("E")
tree.right_child.left_child = Tree("F")
tree.right_child.right_child = Tree("G")

它的Newick 格式应该是((G,F)C,(E,D)B)A;

如何将 Tree 对象的任何实例转换为其 Newick 格式？

标签： python-3.xalgorithmbinary-tree

Answer 1

感谢 Blckknght 的提示。

def to_newick(tree):
    newick = ""
    newick = traverse(tree, newick)
    newick = f"{newick};"
    return newick

def traverse(tree, newick):
    if tree.left_child and not tree.right_child:
        newick = f"(,{traverse(tree.left_child, newick)}){tree.data}"
    elif not tree.left_child and tree.right_child:
        newick = f"({traverse(tree.right_child, newick)},){tree.data}"
    elif tree.left_child and tree.right_child:
        newick = f"({traverse(tree.right_child, newick)},{traverse(tree.left_child, newick)}){tree.data}"
    elif not tree.left_child and not tree.right_child:
        newick = f"{tree.data}"
    else:
        pass
    return newick