二叉搜索树（BST）删除节点时陷入死循环的问题求助

Hey there! Let's break down why your BST's delete function is getting stuck in an infinite loop when dealing with mixed left/right branches, and how to fix it.

The Root Cause of the Infinite Loop #

Your current Delete method has flawed traversal logic. Let's walk through your failing test case (BST.Delete(6) after inserting 10,5,8,7,6) to see what's going wrong:

1. The tree structure looks like this:

   10
      /
     5
      \
       8
      /
     7
    /
   6
   

2. current starts as the root node (10). Since 10 > 6, we know the target is in the left subtree—but your code doesn't move current to current.left here.
3. Next, you check current.left (node 5). 5 !== 6, and 5 > 6 is false, so you don't shift current to the left.
4. current.right is null, so that block does nothing.
5. The loop repeats with current still pointing to 10—this is the infinite loop!

Your traversal only moves current if the direct left child is larger than the target, or the direct right child is smaller than the target. That's backwards for a BST:

• If the target is smaller than the current node's data, you should always move to the left child (if it exists)
• If the target is larger, always move to the right child (if it exists)

On top of that, your original code only deletes direct children of the current node and just sets them to null—it doesn't handle nodes with their own children at all.

Fixed BST Implementation #

Here's a revised version with proper traversal and full deletion logic (handling leaf nodes, nodes with one child, and nodes with two children):

var BST = (function(){
    // PRIVATE
    var root = null;
    // NODE OBJECT
    var Node = function (data, left, right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    // Helper: Find the smallest node in a subtree (inorder successor)
    function getInorderSuccessor(node) {
        let current = node.right;
        while (current.left !== null) {
            current = current.left;
        }
        return current;
    }

    // Recursive helper to handle deletion logic
    function deleteNode(node, data) {
        if (node === null) return null;

        // Traverse to find the target node
        if (data < node.data) {
            node.left = deleteNode(node.left, data);
        } else if (data > node.data) {
            node.right = deleteNode(node.right, data);
        } else {
            // Node found: handle deletion cases
            // Case 1: Leaf node (no children)
            if (!node.left && !node.right) {
                console.log(`${data} has been removed from the tree`);
                return null;
            }
            // Case 2: Node with one child
            else if (!node.left) {
                console.log(`${data} has been removed from the tree`);
                return node.right;
            } else if (!node.right) {
                console.log(`${data} has been removed from the tree`);
                return node.left;
            }
            // Case 3: Node with two children
            else {
                const successor = getInorderSuccessor(node);
                node.data = successor.data;
                node.right = deleteNode(node.right, successor.data);
                console.log(`${data} has been removed (replaced with successor ${successor.data})`);
            }
        }
        return node;
    }

    // PUBLIC METHODS
    return {
        insert: function(data) {
            const node = new Node(data,null, null);
            if (root === null) {
                root = node;
            } else {
                let current = root;
                while (true) {
                    if (current.data > data) {
                        if (current.left === null) {
                            current.left = node;
                            break;
                        }
                        current = current.left;
                    } else {
                        if (current.right === null) {
                            current.right = node;
                            break;
                        }
                        current = current.right;
                    }
                }
            }
        },
        Delete: function(data) {
            if (root === null) {
                return console.log("Nothing in Tree");
            }
            root = deleteNode(root, data);
            if (!root) console.log("Tree is now empty");
        },
        show: function() {
            console.log(root);
        },
        test: function() {
            console.log("test is working");
        }
    }
})();

Key Improvements #

• Recursive Traversal: Recursion makes it straightforward to navigate the tree and update parent pointers correctly, avoiding loops entirely.
• Full Deletion Logic: Handles all three standard BST deletion cases:
  1. Deleting a leaf node (simply remove it)
  2. Deleting a node with one child (replace the node with its child)
  3. Deleting a node with two children (replace it with its inorder successor, then delete that successor)
• Correct Navigation: The recursive function moves left/right based on proper BST rules, so it will always find the target node if it exists.

Testing the Fixed Code #

Your failing test case now works as expected:

BST.insert(10);
BST.insert(5);
BST.insert(8);
BST.insert(7);
BST.insert(6);
BST.Delete(6); // Logs "6 has been removed from the tree"
BST.show(); // 7's left child is now null, as expected

Your original pure-branch test cases will also work, and the code now supports more complex deletion scenarios.

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