为什么删除二叉搜索树的最小/最大节点后查询对应值会返回None

问题原因 #

• 删除节点的单侧子树处理逻辑存在核心错误：当待删除节点没有左子树时，你执行了self.data = self.right，这是把data字段直接赋值成了右子节点对象（如果右子节点不存在就直接赋值为None），而非右子节点存储的数值。删除最小节点时，待删除的节点本身就没有左子树，且大概率没有右子树，执行完这句后当前节点的data直接变为None。
• findMin/findMax函数没有处理self.data为None的分支，一旦data为空，函数没有显式返回值，默认返回None，完全符合你遇到的现象。
• 递归调用删除函数前没有做空判断，当目标删除值不存在于树中时，会直接触发属性不存在的报错。
• 度为2的节点删除逻辑中，dltNode = self、dltNode.data = self.data两句是无效冗余代码，不影响运行但完全多余。

修复方案 #

首先修正deleteNode函数的逻辑，最小改动适配你现有的实现模式：

def deleteNode(self,val):
    # 先处理当前节点为空、目标值不存在的场景
    if self.data is None:
        return False
    if self.data > val:
        # 递归左子树前先判断左子树是否存在
        if self.left:
            return self.left.deleteNode(val)
        return False
    elif self.data < val:
        # 递归右子树前先判断右子树是否存在
        if self.right:
            return self.right.deleteNode(val)
        return False
    else:
        # 待删除节点为当前节点
        if self.left is None:
            # 无左子树，用右子节点覆盖当前节点
            if self.right:
                self.data = self.right.data
                self.left = self.right.left
                self.right = self.right.right
            else:
                # 左右子树都为空，直接置空当前节点数值
                self.data = None
            return True
        elif self.right is None:
            # 无右子树，用左子节点覆盖当前节点
            self.data = self.left.data
            self.right = self.left.right
            self.left = self.left.left
            return True
        else:
            # 度为2的节点，取左子树最大值替换当前节点
            largest = self.left.findMax()
            self.data = largest
            self.left.deleteNode(largest)
            return True

然后修正findMin和findMax函数，补充空值分支的显式返回：

def findMin(self):
    if self.data is None:
        return None
    if self.left is None:
        return self.data
    else:
        return self.left.findMin()

def findMax(self):
    if self.data is None:
        return None
    if self.right is None:
        return self.data
    else:
        return self.right.findMax()

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