二叉搜索树（BST）根节点删除异常求助：单/无子女场景

问题分析 #

1. 无效的根节点判断逻辑
   你尝试用元组保存根节点值的方式完全错误：这个操作只在delete函数第一次调用时执行，递归处理子节点时tree已经不是根节点，而且当tree为None时会直接抛出AttributeError。判断当前节点是否为根不需要额外保存，递归的返回机制会自动处理根节点的替换。

2. 叶子节点删除错误
   当根节点是叶子节点时，你设置tree.value = None，但根据代码中BST = Optional[TreeNode]的定义，空树应该是None，而非带有空值的TreeNode。这会导致树中残留无效节点，无法真正删除根。

3. 单子节点分支逻辑错误
   在处理单子节点的分支中，当节点只有右子节点时，错误地返回了tree.left，应该返回tree.right。

4. insert函数的隐性bug
   原insert函数在插入新节点后返回的是子节点，而非原树的根节点，这会导致调用insert后无法正确获取更新后的完整树结构。

修正后的代码 #

from __future__ import annotations

from typing import Any, Optional


class TreeNode:
    def __init__(self, value: Any, left: BST, right: BST):
        self.value = value
        self.left = left
        self.right = right

    def __repr__(self):
        return f"TreeNode({self.value}, {self.left}, {self.right})"

    def __eq__(self, other):
        return self.value == other.value and \
            self.right == other.right and self.left == other.left


BST = Optional[TreeNode]


def is_empty(tree: BST) -> bool:
    """Return True if the tree is empty, False otherwise."""
    return tree is None


def search(tree: BST, value: Any) -> bool:
    """Return True if value is in tree, False otherwise."""
    if tree is None:
        return False
    if tree.value == value:
        return True
    elif value < tree.value:
        return search(tree.left, value)
    else:
        return search(tree.right, value)


def insert(tree: BST, value: Any) -> BST:
    """Insert the value into the tree in the proper location."""
    if tree is None:
        return TreeNode(value, None, None)
    if value < tree.value:
        tree.left = insert(tree.left, value)
    elif value > tree.value:
        tree.right = insert(tree.right, value)
    # 忽略重复值的插入
    return tree


def delete(tree: BST, value: Any) -> BST:
    """Remove the value from the tree (if present).

    If the value is not present, this function does nothing.
    """
    if tree is None:
        return tree

    if value < tree.value:
        tree.left = delete(tree.left, value)
    elif value > tree.value:
        tree.right = delete(tree.right, value)
    else:
        # 当前节点是要删除的节点
        # 情况1：叶子节点（无子女）
        if tree.left is None and tree.right is None:
            return None
        # 情况2：只有一个子女
        elif tree.left is None:
            return tree.right
        elif tree.right is None:
            return tree.left
        # 情况3：有两个子女，找右子树最小节点替换
        else:
            # 找右子树的最左节点（最小值）
            replacement = tree.right
            while replacement.left is not None:
                replacement = replacement.left
            # 替换当前节点的值
            tree.value = replacement.value
            # 删除右子树中的那个最小值节点
            tree.right = delete(tree.right, replacement.value)
    return tree

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