删除二叉搜索树（BST）根节点失败问题排查求助

核心问题点 #

• 未更新根节点引用：delete函数返回操作后的根节点，但调用BST.delete(1)时没有把返回值重新赋值给BST。删除根节点时，原根节点会被替换，必须用返回值更新根引用，否则原变量仍指向旧根。
• 属性名拼写错误：delete函数里写了self.value = min_larger_node.val，但Node类的属性是value，不是val，这会导致根节点值无法被正确替换。
• 空对象判断不规范（非致命）：if self == None: 不符合Python编码习惯，建议改为if self is None。

修复后的完整代码 #

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

    def insert(self, value):
        if not self.value:
            self.value = value
            return
        if value < self.value:
            if self.left:
                self.left.insert(value)
                return
            self.left = Node(value)
            return
        if value > self.value:
            if self.right:
                self.right.insert(value)
                return
            self.right = Node(value)

    def pre_order(self, values):
        if self.value is not None:
            values.append(self.value)
        if self.left is not None:
            self.left.pre_order(values)
        if self.right is not None:
            self.right.pre_order(values)
        return values

    def delete(self, value):
        if self is None:
            return self
        if value < self.value:
            self.left = self.left.delete(value)
            return self
        if value > self.value:
            self.right = self.right.delete(value)
            return self
        # 处理叶子节点或仅有单侧子节点的情况
        if self.right is None:
            return self.left
        if self.left is None:
            return self.right
        # 查找右子树中最小的节点，用于替换当前节点
        min_larger_node = self.right
        while min_larger_node.left:
            min_larger_node = min_larger_node.left
        self.value = min_larger_node.value  # 修正属性名拼写错误
        self.right = self.right.delete(min_larger_node.value)
        return self

l = [1, 2, 3, 4, 5, 6]
BST = Node()
for i in l:
    BST.insert(i)

before_deleting = []
print(BST.pre_order(before_deleting))  # 输出: [1, 2, 3, 4, 5, 6]

# 关键：接收删除操作后的新根节点
BST = BST.delete(1)

after_deleting = []
print(BST.pre_order(after_deleting))  # 输出: [2, 3, 4, 5, 6]

修复效果说明 #

1. 修正属性名后，根节点的值能被右子树最小节点的值正确替换
2. 赋值返回值给BST，确保根节点引用更新为删除后的新根
3. 规范空判断写法，符合Python编码规范

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