二叉搜索树(BST)节点删除报错：删除50时提示‘not found’求助

你遇到的问题核心在于deleteNode方法的逻辑错误，尤其是递归处理的部分，另外代码里还有一些拼写错误也会导致潜在问题。下面一步步拆解问题：

1. deleteNode方法的核心逻辑错误 #

你的deleteNode开头调用了answ=search(curr,n);，这个逻辑完全不符合BST删除节点的递归流程：

• 当递归进入左子树或右子树时，search(curr,n)会返回null（因为当前curr不是目标节点，且目标节点在更深的子树里），这时候你直接返回curr，跳过了递归删除的步骤，导致真正的删除逻辑根本没执行。
• 正确的做法应该是通过递归遍历找到目标节点，而不是提前调用search判断。

2. 拼写错误导致的潜在问题 #

代码里存在多处拼写不一致的问题：

• 类名NodeT和NodoT混用（比如BinaryTree里的root定义为NodoT，但addRec参数是NodeT）
• inorder方法里的inorden(n.right)应该是inorder(n.right)
• minValue方法里的menor=curr.left.elem应该是min=curr.left.elem

修正后的完整代码 #

下面是修正了所有问题后的代码：

class NodeT {
    int elem;
    NodeT left;
    NodeT right;
    public NodeT(int elem) {
        this.elem = elem;
    }
}

class BinaryTree {
    NodeT root; // 修正拼写：NodoT -> NodeT

    public void insertElem(int n) {
        root = addRec(root, n);
    }

    public NodeT addRec(NodeT n, int elem) {
        if (n == null) {
            n = new NodeT(elem);
        } else {
            if (elem < n.elem) {
                n.left = addRec(n.left, elem);
            } else {
                n.right = addRec(n.right, elem);
            }
        }
        return n;
    }

    public void inorder(NodeT n) {
        if (n != null) {
            inorder(n.left);
            System.out.println(n.elem);
            inorder(n.right); // 修正拼写：inorden -> inorder
        }
    }

    public NodeT search(NodeT root, int n) {
        if (root == null) return null; // 增加边界判断，避免空指针
        if (root.elem == n) return root;
        else {
            if (n < root.elem) {
                return search(root.left, n); // 无需提前判断left是否为null，递归会处理
            } else {
                return search(root.right, n); // 同理
            }
        }
    }

    public void delete(int n) {
        root = deleteNode(root, n);
    }

    // 修正后的deleteNode逻辑
    public NodeT deleteNode(NodeT curr, int n) {
        // 1. 递归终止条件：当前节点为空，说明没找到目标
        if (curr == null) {
            System.out.println("not found");
            return null;
        }

        // 2. 递归查找目标节点
        if (n < curr.elem) {
            curr.left = deleteNode(curr.left, n);
        } else if (n > curr.elem) {
            curr.right = deleteNode(curr.right, n);
        } else {
            // 3. 找到目标节点，处理三种删除情况
            // 情况1：只有右孩子或叶子节点
            if (curr.left == null) {
                return curr.right;
            }
            // 情况2：只有左孩子
            else if (curr.right == null) {
                return curr.left;
            }
            // 情况3：有两个孩子，找右子树最小值替代，然后删除该最小值节点
            curr.elem = minValue(curr.right);
            curr.right = deleteNode(curr.right, curr.elem);
        }
        return curr;
    }

    int minValue(NodeT curr) {
        int min = curr.elem;
        while (curr.left != null) {
            min = curr.left.elem; // 修正拼写：menor -> min
            curr = curr.left;
        }
        return min;
    }

    public static void main(String[] args) {
        BinaryTree bt = new BinaryTree();
        int data[] = {50,30,70,20,40,60,80};
        for (int i=0; i<data.length; i++) {
            bt.insertElem(data[i]);
        }
        System.out.println("初始中序遍历：");
        bt.inorder(bt.root);
        bt.delete(20);
        System.out.println("\n删除20后中序遍历：");
        bt.inorder(bt.root);
        bt.delete(30);
        System.out.println("\n删除30后中序遍历：");
        bt.inorder(bt.root);
        bt.delete(50);
        System.out.println("\n删除50后中序遍历：");
        bt.inorder(bt.root);
    }
}

修正后的测试结果 #

运行代码后，删除50时不会再出现"not found"，中序遍历结果始终保持BST的有序性：

• 初始遍历：20,30,40,50,60,70,80
• 删除20后：30,40,50,60,70,80
• 删除30后：40,50,60,70,80
• 删除50后：40,60,70,80

另外，我还优化了search方法，增加了空指针判断，并且去掉了不必要的子节点非空判断，让递归逻辑更简洁。

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