感谢Blckknight的提示。

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

字符串

我只是想你可能想要一些不是递归的东西，迭代实现通常运行得更快。

from typing import List

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

    def newick(self) -> str:
        # Recursive version
        # Practically a postorder tree traversal
        if not self.left_child and not self.right_child:
            return self.data
        left_child = self.left_child.newick() if self.left_child else ""
        right_child = self.right_child.newick() if self.right_child else ""
        return f"({right_child},{left_child}){self.data}"

    def newick_iter(self) -> str:
        # Iterative version
        # https://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/
        res: str = ""
        traverse_stack: List[Tree] = []
        curr: Tree = self
        while True:
            while curr:
                if curr.left_child:
                    traverse_stack.append(curr.left_child)
                    res += '('

                traverse_stack.append(curr)
                curr = curr.right_child

            curr = traverse_stack.pop()
            if curr.left_child and (traverse_stack and curr.left_child == traverse_stack[-1]):
                tmp = traverse_stack.pop()
                traverse_stack.append(curr)
                curr = tmp
                if res[-1] == ')':
                    res = res[:-1]
                res += ','
            else:
                res += curr.data + ')'
                curr = None

            if not traverse_stack:
                break
        res = res[:-1]

        return res

def main():
    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")

    print(tree.newick_iter())
    print(tree.newick())

if __name__ == '__main__':
    main()

字符串

有一个Python库bigtree可以为你做这件事。这可以用两行代码来完成-一行是创建树，另一行是将树导出为Newick树表示法。

from bigtree import list_to_tree, tree_to_newick

# Create the tree (using any method you want, for simplicity I will use list)
root = list_to_tree(["A/B/D", "A/B/E", "A/C/F", "A/C/G"])

root.show()
# A
# ├── B
# │   ├── D
# │   └── E
# └── C
#     ├── F
#     └── G

# Export to Newick
tree_to_newick(root)
# ((D,E)B,(F,G)C)A

字符串
但是，这与((G,F)C,(E,D)B)A;的结果略有不同，因为左子项应该出现在左侧，右子项应该出现在右侧。
免责声明：我是bigtree的作者：）