Python二叉搜索树（BST）删除节点异常Bug求助

嘿，这个问题我之前折腾BST的时候也踩过坑！咱们来一步步捋清楚问题出在哪：

从你描述的现象——只有带两个子节点的节点能正常删除，其他情况删完还能打印出来——来看，大概率是删除叶子节点/单子女节点时，没有正确更新父节点的左/右指针，或者递归函数的返回值没被正确接收。

常见错误场景拆解 #

• 叶子节点删除失效：如果只是把当前节点的Left/Right设为None，但父节点指向这个节点的指针没修改，树的实际结构根本没变，打印时自然还能看到它。
• 单子女节点删除失效：正确操作应该是让父节点直接指向该节点的子节点，但如果你的代码只处理了当前节点，没把这个子节点返回给父节点更新引用，旧节点就会一直挂在树上。
• 递归返回值未处理：很多BST删除的递归实现里，函数需要返回更新后的子树根节点。如果你的delete_node没有返回值，或者调用时没把返回值赋值给父节点的对应指针，就会出现“删了但没完全删”的情况。

正确的递归删除逻辑参考 #

你可以对照这个示例代码，排查自己的实现差异：

class Node:
    def __init__(self, data):
        self.Left = None
        self.Right = None
        self.T_data = data

class BST:
    def __init__(self):
        self.root = None

    def delete_node(self, root, item):
        # 基准情况：没找到要删除的节点
        if root is None:
            return root
        
        # 递归定位目标节点
        if item < root.T_data:
            root.Left = self.delete_node(root.Left, item)
        elif item > root.T_data:
            root.Right = self.delete_node(root.Right, item)
        else:
            # 情况1：叶子节点，直接返回None让父节点断开引用
            if root.Left is None and root.Right is None:
                return None
            # 情况2：只有一个子节点，返回子节点让父节点直接指向它
            elif root.Left is None:
                return root.Right
            elif root.Right is None:
                return root.Left
            # 情况3：两个子节点（你说的正常工作的场景）
            else:
                # 找右子树的最小节点替代当前节点值
                min_node = self.find_min(root.Right)
                root.T_data = min_node.T_data
                # 删除那个用来替代的最小节点
                root.Right = self.delete_node(root.Right, min_node.T_data)
        return root

    def find_min(self, node):
        current = node
        while current.Left is not None:
            current = current.Left
        return current

你需要重点检查的点 #

• 你的delete_node函数是否返回了更新后的节点？如果没有返回值，或者调用时没把返回值赋值给父节点的Left/Right，父节点的引用不会更新。
• 处理叶子节点和单子女节点时，是不是直接返回了None或者子节点，而不是只修改当前节点的属性？
• 调用delete_node时，是不是用root = delete_node(root, item)这种方式更新根节点？如果只是调用delete_node(item)而不接收返回值，根节点的引用不会变化。

测试小技巧 #

你可以用中序遍历打印树的结构（BST的中序遍历是有序序列），删除前后对比序列，能直观看到节点是否真的被移除：

def inorder(self, root):
    if root:
        self.inorder(root.Left)
        print(root.T_data, end=" ")
        self.inorder(root.Right)

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