Python二叉搜索树实现Bug排查：节点删除与显示异常问题

问题现象 #

• 删除右子树中带单个子节点的节点时出现异常
• 值为-1的节点实际存在两个子节点，但在删除值为-7/2的节点前，第二个子节点未正常显示

代码核心错误分析 #

1. 节点添加逻辑完全颠倒（直接导致子节点显示异常） #

BST的核心规则是小于当前节点值的元素挂左子树，大于的挂右子树，但你的addTreeNode方法完全搞反了左右关系：

# 错误代码片段
if treeNode.val < current.val:
    current = current.rightChild  # 小于本应走左子树，错误走了右
elif treeNode.val > current.val:
    current = current.leftChild  # 大于本应走右子树，错误走了左

# 节点挂载也同步错误
if treeNode.val < prev.val:
    prev.rightChild = treeNode  # 小于应挂左子节点，错误挂右
elif treeNode.val > prev.val:
    prev.leftChild = treeNode  # 大于应挂右子节点，错误挂左

这种颠倒直接导致-1节点的子节点被挂到了错误位置，遍历自然无法正常显示。

2. 遍历顺序不符合BST验证逻辑 #

print_tree使用的是根→右→左的遍历顺序，既不是标准的前/中/后序，再加上添加逻辑的错误，进一步放大了子节点显示异常的问题。建议改为左→根→右的中序遍历，能直观体现BST的有序性：

def print_tree(self):
    def dfs(node):
        if node:
            dfs(node.leftChild)  # 先遍历左子树
            print(" ", node.val)
            dfs(node.rightChild) # 再遍历右子树
    dfs(self.baseNode)

3. 删除节点方法的多处逻辑漏洞（导致删除异常） #

deleteNode存在多个致命问题：

• 节点查找逻辑不完整：如果目标节点是根节点，循环不会触发；如果目标节点不存在，current会变为None，后续操作直接崩溃。
• 单节点删除的判断逻辑错误：用current.val > self.baseNode.val判断左右子树完全不合理，应该根据prev与current的父子关系（是prev的左/右子节点）来处理。
• 双子节点删除逻辑错误：BST删除双子节点的正确做法是用右子树的最小节点（或左子树的最大节点）替换当前节点，而不是直接把左子树挂到右子树的右节点，这会彻底破坏BST结构。

修正后的核心代码示例 #

修正的节点添加方法 #

def addTreeNode(self, treeNode):
    current = self.baseNode
    prev = None
    while current:
        prev = current
        if treeNode.val < current.val:
            current = current.leftChild  # 小于走左子树
        elif treeNode.val > current.val:
            current = current.rightChild # 大于走右子树
        else:
            return  # BST通常不允许重复值，直接返回
    if treeNode.val < prev.val:
        prev.leftChild = treeNode  # 小于挂左子节点
    elif treeNode.val > prev.val:
        prev.rightChild = treeNode # 大于挂右子节点

修正的节点删除方法（按值查找，更符合实用场景） #

def deleteNode(self, target_val):
    current = self.baseNode
    prev = None
    # 先定位目标节点及其父节点
    while current and current.val != target_val:
        prev = current
        if target_val < current.val:
            current = current.leftChild
        else:
            current = current.rightChild
    if not current:
        return  # 节点不存在，直接返回
    
    # 情况1：叶子节点
    if not current.leftChild and not current.rightChild:
        if not prev:
            self.baseNode = None  # 删除根节点
        elif prev.leftChild == current:
            prev.leftChild = None
        else:
            prev.rightChild = None
    # 情况2：只有左子节点
    elif not current.rightChild:
        if not prev:
            self.baseNode = current.leftChild
        elif prev.leftChild == current:
            prev.leftChild = current.leftChild
        else:
            prev.rightChild = current.leftChild
    # 情况3：只有右子节点
    elif not current.leftChild:
        if not prev:
            self.baseNode = current.rightChild
        elif prev.leftChild == current:
            prev.leftChild = current.rightChild
        else:
            prev.rightChild = current.rightChild
    # 情况4：有两个子节点
    else:
        # 找右子树的最小节点
        min_node_parent = current
        min_node = current.rightChild
        while min_node.leftChild:
            min_node_parent = min_node
            min_node = min_node.leftChild
        # 替换当前节点的值
        current.val = min_node.val
        # 删除最小节点
        if min_node_parent.leftChild == min_node:
            min_node_parent.leftChild = min_node.rightChild
        else:
            min_node_parent.rightChild = min_node.rightChild

总结 #

你遇到的所有问题根源都是BST左右子树的规则完全搞反，导致节点添加位置错误，进而引发遍历显示异常和删除逻辑混乱。先修正节点添加逻辑，再调整遍历和删除的逻辑，就能解决所有问题。

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