二叉搜索树删除节点函数未返回被删除节点问题排查

现有Java实现的二叉搜索树删除功能，delete()函数虽能成功删除目标节点，但返回的是树的根节点而非被删除的节点。以下是原代码及运行输出：

原代码 #

// Binary Node Class
class BinaryNode {
    int info;
    BinaryNode left;
    BinaryNode right;

    public BinaryNode(int info){
        this.info = info;
        left = null;
        right = null;
    }

    public void displayNode(){
        System.out.print(this.info);
    }
}

// Binary Tree Operation Class
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class BinaryTreeOperations{

    BinaryNode rootNode;

    public BinaryTreeOperations(){
        rootNode = null;
        rootNode = insertTreeNodes(rootNode, 7); // root node
        insertTreeNodes(rootNode, 4); // 按BST规则插入后续节点
        insertTreeNodes(rootNode, 1);
        insertTreeNodes(rootNode, 8);
        insertTreeNodes(rootNode, 10);
        insertTreeNodes(rootNode, 2);
        insertTreeNodes(rootNode, 21);
        insertTreeNodes(rootNode, 5);

        inOrderTraversal(rootNode);

        System.out.print("Deleted Node: ");
        delete(rootNode, 8).displayNode();
        System.out.println();
        inOrderTraversal(rootNode);
    }

    public BinaryNode delete(BinaryNode root, int key){
        if(root == null)
            return root;
        if(key < root.info)
            root.left = delete(root.left, key);
        else if(key > root.info)
            root.right = delete(root.right, key);
        else{
            if(root.left != null && root.right != null){
                root.info = findMin(root.right).info;
                root.right = delete(root.right, root.info);
            }
            else
                root = (root.left != null) ? root.left : root.right;
        }
        return root;
    }

    private BinaryNode findMin(BinaryNode root) {
        if(root != null){
            while(root.left != null){
                root = root.left;
            }
        }
        return root;
    }

    public void inOrderTraversal(BinaryNode root){
        if(root == null)
            return;
        else{
            inOrderTraversal(root.left);
            root.displayNode();
            System.out.print(", ");
            inOrderTraversal(root.right);
        }
    }

    // 递归插入节点到BST
    /**
     * BST规则：小于等于根节点的值放左子树，大于的值放右子树
     * @param root 树的根节点
     * @param data 要插入的数据
     * @return 更新后的子树根节点
     */
    public BinaryNode insertTreeNodes(BinaryNode root, int data){
        if(root == null) {
            root = new BinaryNode(data);
            root.left = root.right = null;
        }
        else if(data <= root.info)
            root.left = insertTreeNodes(root.left, data);
        else
            root.right = insertTreeNodes(root.right, data);
        return root;
    }

    public static void main(String[] args) {
        BinaryTreeOperations treeOperation = new BinaryTreeOperations();
    }
}

原运行输出 #

1, 2, 4, 5, 7, 8, 10, 21, 
Deleted Node: 7 
1, 2, 4, 5, 7, 10, 21,

问题分析 #

1. 返回值逻辑错误：delete()函数的设计目的是递归调整树结构，返回的是调整后的子树根节点，而非被删除的目标节点。调用delete(rootNode, 8)时，返回的是整个树的根节点（值为7），因此输出错误。
2. 根节点未同步更新：原代码未将delete()的返回值赋值给rootNode，若删除的是根节点，rootNode将无法同步为新的根节点，导致树结构异常。

解决方案 #

通过新增辅助方法，在删除过程中捕获被删除的节点，同时正确维护树的结构。利用数组传递被删除节点的引用（Java值传递特性限制，数组可保存引用），区分两种删除场景处理：

修改后的完整代码 #

// Binary Node Class
class BinaryNode {
    int info;
    BinaryNode left;
    BinaryNode right;

    public BinaryNode(int info){
        this.info = info;
        left = null;
        right = null;
    }

    public void displayNode(){
        System.out.print(this.info);
    }
}

// Binary Tree Operation Class
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class BinaryTreeOperations{

    BinaryNode rootNode;

    public BinaryTreeOperations(){
        rootNode = null;
        rootNode = insertTreeNodes(rootNode, 7); // root node
        insertTreeNodes(rootNode, 4);
        insertTreeNodes(rootNode, 1);
        insertTreeNodes(rootNode, 8);
        insertTreeNodes(rootNode, 10);
        insertTreeNodes(rootNode, 2);
        insertTreeNodes(rootNode, 21);
        insertTreeNodes(rootNode, 5);

        inOrderTraversal(rootNode);
        System.out.println();

        System.out.print("Deleted Node: ");
        BinaryNode removedNode = deleteAndGetRemoved(8);
        if (removedNode != null) {
            removedNode.displayNode();
        }
        System.out.println();
        
        inOrderTraversal(rootNode);
    }

    // 对外方法：删除节点并返回被删除的节点
    public BinaryNode deleteAndGetRemoved(int key) {
        BinaryNode[] removed = new BinaryNode[1];
        // 更新根节点为删除后的新根
        rootNode = deleteHelper(rootNode, key, removed);
        return removed[0];
    }

    // 递归辅助方法：处理删除逻辑并记录被删除节点
    private BinaryNode deleteHelper(BinaryNode root, int key, BinaryNode[] removed) {
        if (root == null) {
            return null;
        }

        if (key < root.info) {
            root.left = deleteHelper(root.left, key, removed);
        } else if (key > root.info) {
            root.right = deleteHelper(root.right, key, removed);
        } else {
            // 找到目标节点，保存被删除的节点（拷贝值避免原节点引用被覆盖）
            removed[0] = new BinaryNode(root.info);

            // 处理双子节点情况：用右子树最小值替换当前节点，再删除最小值节点
            if (root.left != null && root.right != null) {
                BinaryNode minNode = findMin(root.right);
                root.info = minNode.info;
                // 删除右子树的最小值节点（无需记录此节点）
                root.right = deleteHelper(root.right, minNode.info, new BinaryNode[1]);
            } else {
                // 单节点或叶子节点：直接替换为子节点或null
                root = (root.left != null) ? root.left : root.right;
            }
        }
        return root;
    }

    private BinaryNode findMin(BinaryNode root) {
        if(root != null){
            while(root.left != null){
                root = root.left;
            }
        }
        return root;
    }

    public void inOrderTraversal(BinaryNode root){
        if(root == null)
            return;
        inOrderTraversal(root.left);
        root.displayNode();
        System.out.print(", ");
        inOrderTraversal(root.right);
    }

    public BinaryNode insertTreeNodes(BinaryNode root, int data){
        if(root == null) {
            root = new BinaryNode(data);
            root.left = root.right = null;
        }
        else if(data <= root.info)
            root.left = insertTreeNodes(root.left, data);
        else
            root.right = insertTreeNodes(root.right, data);
        return root;
    }

    public static void main(String[] args) {
        BinaryTreeOperations treeOperation = new BinaryTreeOperations();
    }
}

修改后运行输出 #

1, 2, 4, 5, 7, 8, 10, 21, 
Deleted Node: 8 
1, 2, 4, 5, 7, 10, 21,

关键修改点 #

1. 新增deleteAndGetRemoved()对外方法，封装删除逻辑并返回被删除节点。
2. 新增deleteHelper()递归辅助方法，通过数组捕获被删除节点的引用。
3. 处理双子节点删除时，先保存原目标节点的值，再完成值替换和子节点删除操作。
4. 正确更新rootNode为删除操作后的新根节点，避免树结构不一致。

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