为二叉表达式树节点添加父指针时遇问题求解决方案

你的问题核心是重复创建了Node实例：先初始化N = Node(value)，后续又return一个全新的Node(...)，导致parent参数指向的是废弃的N实例，而实际返回的节点和N完全是两个独立对象，父指针自然无效，连root都会指向错误的节点。

错误点拆解 #

• N = Node(value) 创建了一个临时节点实例
• return Node(value, NL, NR, parent=N) 又创建了第二个实例，此时parent指向的是第一个临时实例，而非当前返回的节点本身，逻辑完全混乱

修正方案 #

只创建一次Node实例，先构建当前节点，递归生成子节点后，反向给子节点设置父指针（因为父节点此时已经存在，可以直接引用）：

class Node:
    def __init__(self, value, left=None, right=None, parent=None):
        self.value = value
        self.left = left
        self.right = right
        self.parent = parent


class Tree:
    def __init__(self, lst):
        self.it = iter(lst)
        self.lst = lst
        self.root = None

    def create_tree(self):
        value = next(self.it, None)
        if value is None:
            return None
        
        # 仅创建当前节点的唯一实例
        node = Node(value)
        if self.root is None:
            self.root = node
        
        if not value.isdigit():
            # 递归生成左右子节点
            left_child = self.create_tree()
            right_child = self.create_tree()
            # 绑定当前节点与子节点的关系
            node.left = left_child
            node.right = right_child
            # 给子节点设置父指针
            if left_child:
                left_child.parent = node
            if right_child:
                right_child.parent = node
        
        return node

# 测试代码
lst = ["+", "*", "2", "6", "/", "10", "2"]
t = Tree(lst)
t.create_tree()

# 验证父指针有效性
print(t.root.left.parent.value)  # 输出 '+'
print(t.root.left.left.parent.value)  # 输出 '*'
print(t.root.right.right.parent.value)  # 输出 '/'

关键修改说明 #

1. 每个逻辑节点仅对应一个Node实例，避免重复创建导致的对象混乱
2. 子节点创建完成后，通过left_child.parent = node直接关联父节点，逻辑清晰且无冗余
3. 修复了root指向错误实例的问题，现在root指向的是树的真实根节点

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