Как преобразовать двоичное дерево в дерево Ньюика, используя Python?

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?

Answer 1

Я просто подумал, что вам может понадобиться что-то нерекурсивное, итеративные реализации обычно работают быстрее.

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

Answer 2

Спасибо 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