基于OOP与递归的Python前缀表达式二叉树构建问题求助

代码中的核心错误与缺失 #

• Node类初始化逻辑错误：原代码中每个Node存储整个表达式列表lst，但二叉树的每个节点只需要存储自身的值（运算符或数字），不需要持有整个表达式。
• 递归调用参数错误：递归时传入lst[i+1]是单个元素（如"2"），不是子表达式列表，导致递归无法正确解析子结构。
• 列表修改逻辑混乱：直接对原列表执行remove操作，会破坏表达式的结构，且递归过程中修改全局列表会导致索引错位。
• 节点赋值逻辑错误：self.parent被赋值为字符串类型的运算符，而非Node对象；left/right接收的是create_tree返回的列表，而非Node实例，完全不符合二叉树的结构要求。
• 数字节点处理缺失：原代码创建数字节点后没有返回，递归链断裂，无法构建完整的树结构。
• 递归逻辑不符合前缀规则：前缀表达式的结构是「运算符 + 左子表达式 + 右子表达式」，原代码用循环遍历列表的方式，没有遵循递归消耗元素的正确逻辑。

修正后的代码实现 #

class Node:
    def __init__(self, value):
        self.value = value  # 存储当前节点的值（运算符/数字）
        self.left = None    # 左子节点
        self.right = None   # 右子节点
        self.parent = None  # 父节点引用

    @classmethod
    def create_tree(cls, expr, index=[0]):
        # 用可变对象index跟踪当前处理位置，避免全局变量
        current_val = expr[index[0]]
        index[0] += 1

        if current_val.isdigit():
            # 数字节点直接返回
            return cls(current_val)
        else:
            # 运算符节点：先创建自身，再递归生成左、右子树
            op_node = cls(current_val)
            op_node.left = cls.create_tree(expr, index)
            op_node.right = cls.create_tree(expr, index)
            # 设置子节点的父引用
            op_node.left.parent = op_node
            op_node.right.parent = op_node
            return op_node

# 测试示例
expr = ["+", "2", "3"]
root = Node.create_tree(expr)
# 验证树结构
print(f"根节点值: {root.value}")
print(f"左子节点值: {root.left.value}")
print(f"右子节点值: {root.right.value}")

修正说明 #

1. Node类职责明确：每个节点只管理自身值和子节点引用，符合OOP的单一职责原则。
2. 递归逻辑合规：严格遵循前缀表达式的结构，遇到运算符则递归生成左、右子树，遇到数字直接返回节点，通过index跟踪处理进度，不修改原表达式。
3. 正确构建树结构：每个节点的left/right都指向Node实例，parent引用正确关联父节点，形成完整的二叉树结构。

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