JavaScript中BST的Remove()方法无法删除元素，求排查问题

核心问题 #

你的remove方法根本没修改树的实际结构，原因有这几点：

• 引用操作错误：pointer只是root的引用副本，修改pointer或者return节点，不会改变原树中父节点的left/right指向，更不会更新root本身。比如你找到目标节点后return null，这个返回值没被用来替换任何实际节点的引用。
• 双节点删除逻辑错误：直接把pointer赋值为nextBiggest完全不对，正确做法是用后继节点的值覆盖要删除节点的值，再删除后继节点。
• 没跟踪父节点：遍历的时候只记录了当前节点，没记录它的父节点，所以找不到要修改的关联位置。

修复后的代码 #

const Node = (data, left = null, right = null) => {
    return { data, left, right };
};

const Tree = array => {
    const remDupsAndSort = array => {
        const mergeSort = array => {
            if (array.length <= 1) return array;
            let leftArr = array.slice(0, Math.floor(array.length / 2));
            let rightArr = array.slice(Math.floor(array.length / 2));
            return merge(mergeSort(leftArr), mergeSort(rightArr));
        };
        
        const merge = (leftArr, rightArr) => {
            let sorted = [];
            while (leftArr.length && rightArr.length) {
                if (leftArr[0] < rightArr[0]) {
                    sorted.push(leftArr.shift());
                } else {
                    sorted.push(rightArr.shift());
                }
            };
            return [...sorted, ...leftArr, ...rightArr];
        };
        return mergeSort([...new Set(array)]);
    };

    array = remDupsAndSort(array);

    const buildTree = (array, start, end) => {
        if (start > end) return null;
        let mid = Math.floor((start + end) / 2);
        let node = Node(array[mid]);
        node.left = buildTree(array, start, mid - 1);
        node.right = buildTree(array, mid + 1, end);
        return node;
    };

    let root = buildTree(array, 0, array.length - 1);

    const remove = (value) => {
        // 用递归方式处理，递归能自然处理父节点的引用更新
        const removeNode = (node, val) => {
            if (!node) return null;
            
            if (val < node.data) {
                node.left = removeNode(node.left, val);
                return node;
            } else if (val > node.data) {
                node.right = removeNode(node.right, val);
                return node;
            } else {
                // 情况1：叶子节点
                if (!node.left && !node.right) {
                    return null;
                }
                // 情况2：只有一个子节点
                if (!node.left) {
                    return node.right;
                }
                if (!node.right) {
                    return node.left;
                }
                // 情况3：有两个子节点，找后继节点（右子树最小节点）
                let successor = node.right;
                while (successor.left) {
                    successor = successor.left;
                }
                // 用后继节点的值覆盖当前节点
                node.data = successor.data;
                // 删除后继节点
                node.right = removeNode(node.right, successor.data);
                return node;
            }
        };

        root = removeNode(root, value);
    };

    return { root, remove };
};

关键修改点 #

• 改用递归实现removeNode：递归调用时，会把修改后的子节点重新赋值给父节点的left/right，这样实际修改了树的结构。
• 修复双节点删除逻辑：不再直接替换节点引用，而是用后继节点的值覆盖目标节点，再删除后继节点。
• 更新root引用：每次删除操作后，把root重新赋值为removeNode的返回值，确保根节点被正确更新。

测试示例：

// 测试代码
const tree = Tree([5,3,7,2,4,6,8]);
tree.remove(5);
// 此时root应该是6，树结构正确
console.log(tree.root.data); // 输出6

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