如何实现二叉树show_node函数使最后一个断言生效？

你的问题出在show_node函数的else分支没有实现递归处理运算符节点的逻辑，导致无法生成嵌套的表达式字符串。我们只需要在else块里递归遍历左右子树，然后按照表达式格式拼接即可。

完整的show_node函数实现 #

from tree import Node, leaf

def is_var(tree: Node) -> bool:
    if type(tree.mark) == str:
        return True
    elif tree.mark == "+" or tree.mark == "*":
        return False

def is_val(tree: Node) -> bool:
    if type(tree.mark) == int:
        return True

def show_node(tree: Node) -> str:
    if is_var(tree) or is_val(tree):
        return str(tree.mark)
    else:
        # 填充的递归逻辑
        left_expr = show_node(tree.left)
        right_expr = show_node(tree.right)
        return f"({left_expr} {tree.mark} {right_expr})"

example = Node("+", Node("*", leaf(2), leaf("x")), leaf(5))
# 树结构：
#     +
#    / \
#   *   5
#  / \
# 2   x

assert show_node(leaf("x")) == "x"
assert show_node(leaf(2)) == "2"
assert show_node(example) == "((2 * x) + 5)"

逻辑解释 #

1. 当节点是变量或数值时，直接返回其字符串形式，这部分你已经实现了。
2. 当节点是运算符（+或*）时：
   • 递归调用show_node处理左子树，得到左子树的表达式字符串
   • 递归调用show_node处理右子树，得到右子树的表达式字符串
   • 按照(左表达式 运算符 右表达式)的格式拼接成新的字符串并返回

这样处理后，示例中的树会先递归处理最底层的*节点，生成(2 * x)，然后再被上层的+节点包裹，最终生成((2 * x) + 5)，完美匹配最后一个断言的要求。

内容的提问来源于stack exchange，提问作者user14771462