二叉树，由嵌套的括号表示

Question

我是 python 的新手，我正在构建一棵树，这是我的代码：

class BinaryTree():
    def __init__(self, dado, left = None, right = None):
        self.dado = dado
        self.left = left
        self.right = right

我想做一个函数来表示二叉树，由嵌套的括号表示。此函数接收根并在一行中显示元素的结构。例如树：

显示为(1 (2 () ()) (3 () (4 () ()))).

在这棵树中，树的根由最外层的括号表示，然后是包含根的左 child (2 () ()) 的括号，然后是包含左 child (2 () ()) 的括号从根开始对 child (3 () ( 4 () ) ( )))。左边节点没有children ()()而右边节点有child(4()())，这也是叶子()().

我尝试创建该函数，但无法保留预期的输出...我的函数结果如下：

我的代码，试图创建一个函数，是这样的：

def show(node):
    string = []                                       
    if not node: 
        return      
    print(node.dado)
    show(node.left) 
    show(node.right)

Answer 1

你确实应该为此使用递归，但你的尝试没有添加任何括号，而是输出换行符。

对于基本情况——当节点为 None 时——字符串应为“()”。当节点不是None时，就是将两个子节点的递归结果与节点自身的值相结合

这是一个函数：

def serialize(node):
    if not node:
        return "()"
    return f"({node.dado} {serialize(node.left)} {serialize(node.right)})"

以下是您的使用方法：

# Create tree that's used as example in the question
root = BinaryTree(1, BinaryTree(2), BinaryTree(3, None, BinaryTree(4)))
# Create the string for it
print(serialize(root))   # (1 (2 () ()) (3 () (4 () ())))

Answer 2

您已经实现了树的 inorder 遍历，这很好。你错过了两件事：

如果节点为空，你想打印什么？ -> 空括号
你想在每一步之前和之后打印什么？ -> 括号

因此您的函数可能如下所示：

def show(node):
    if not node:
        print("()", end="")
        return
    print(f"({node.dado} ", end="")
    show(node.left)
    print(" ", end="")
    show(node.right)
    print(")", end="")

print 的 end 参数阻止它在末尾添加换行符。

Answer 3

又一个变体：

def show(node):
    print(end='(')
    if node:
        print(node.dado, end=' ')
        show(node.left)
        print(end=' ')
        show(node.right)
    print(end=')')

二叉树，由嵌套的括号表示

binary tree, represented by nested parentheses

python

tree

binary-tree

python-3.x