C#泛型二叉搜索树实现问题：增删节点失效求助

Hey there! Let’s tackle your C# generic Binary Search Tree (BST) issues head-on—your add/remove functions are misbehaving, and the print/exists checks aren’t showing the expected results. Let’s break down the most likely culprits here, since breakpoint debugging didn’t catch the issue right away.

1. You’re Not Updating the Root Node #

This is the #1 mistake with BST implementations. When you add the first node (like add(2) if your root was originally null) or remove the root node (like remove(1) where 1 is the root), if you don’t reassign the root reference, the tree never actually changes.

For example, if your Add method looks like this (without updating root):

// Wrong! Root never gets set
public void Add(T value)
{
    AddRecursive(root, value);
}

Instead, you need to assign the result of the recursive call back to root:

// Correct
public void Add(T value)
{
    root = AddRecursive(root, value);
}

private Node<T> AddRecursive(Node<T> current, T value)
{
    if (current == null)
    {
        // Returns new node to be assigned as root/child
        return new Node<T>(value);
    }
    int compare = Comparer<T>.Default.Compare(value, current.Value);
    if (compare < 0)
    {
        current.Left = AddRecursive(current.Left, value);
    }
    else if (compare > 0)
    {
        current.Right = AddRecursive(current.Right, value);
    }
    // Return the (possibly updated) current node
    return current;
}

If you skip that root = ... line, the tree stays stuck with its initial state—so adding 2 does nothing, and exists(2) returns false. Same goes for removing the root: if you don’t reassign root to its replacement node, the old root stays in place, making exists(1) still true.

2. Remove Method Isn’t Reassigning Child Nodes #

Removal logic gets tricky, especially when the node has two children. If your Remove method doesn’t update the parent node’s left/right references after deleting a child, the old node remains in the tree.

Just like with Add, you need to return the updated subtree root from the recursive call and assign it back to the parent’s child:

public void Remove(T value)
{
    root = RemoveRecursive(root, value);
}

private Node<T> RemoveRecursive(Node<T> current, T value)
{
    if (current == null) return null;

    int compare = Comparer<T>.Default.Compare(value, current.Value);
    if (compare < 0)
    {
        // Update left child with result of removing from left subtree
        current.Left = RemoveRecursive(current.Left, value);
        return current;
    }
    if (compare > 0)
    {
        // Update right child similarly
        current.Right = RemoveRecursive(current.Right, value);
        return current;
    }

    // Case 1: Node has no children
    if (current.Left == null && current.Right == null)
        return null;

    // Case 2: Node has one child
    if (current.Left == null)
        return current.Right;
    if (current.Right == null)
        return current.Left;

    // Case 3: Node has two children—replace with in-order successor
    T smallestInRight = FindSmallestValue(current.Right);
    current.Value = smallestInRight;
    // Remove the successor from the right subtree
    current.Right = RemoveRecursive(current.Right, smallestInRight);
    return current;
}

private T FindSmallestValue(Node<T> node)
{
    return node.Left == null ? node.Value : FindSmallestValue(node.Left);
}

If your Remove method isn’t using this pattern, the parent nodes never know their child was removed—so the old node lingers, and exists(1) still finds it.

3. Exists Method Has a Traversal Flaw #

If add(2) is supposed to work but exists(2) returns false, double-check your Exists logic. Make sure it’s properly traversing left for smaller values, right for larger ones, and only returns false when it hits a null node.

A correct Exists method looks like this:

public bool Exists(T value)
{
    return ExistsRecursive(root, value);
}

private bool ExistsRecursive(Node<T> current, T value)
{
    if (current == null)
        return false;
    
    int compare = Comparer<T>.Default.Compare(value, current.Value);
    if (compare == 0)
        return true;
    // Recurse left or right based on comparison
    return compare < 0 ? ExistsRecursive(current.Left, value) : ExistsRecursive(current.Right, value);
}

Avoid using == to compare generic types (since it won’t work for all types)—stick to Comparer<T>.Default.Compare instead.

4. Print Method Traverses an Unchanged Tree #

If your print only outputs 1 after adding 2, that’s solid proof the add operation didn’t modify the tree. The print method is probably traversing the root’s children, but since the root wasn’t updated or the child wasn’t assigned correctly, it only sees the initial node.

Targeted Debugging Tips #

Since breakpoint debugging didn’t hit the issue, try these specific checks:

• When calling add(2), step into the Add method and verify:
  • Is root null before the call?
  • Does the recursive method return a new node for value 2?
  • Is root assigned to this new node after the recursive call?
• When calling remove(1), check:
  • Does the method find the node with value 1?
  • Does it return the correct replacement node (null, left child, right child, or successor)?
  • Is root updated to this replacement node?
• Inspect your Node<T> class: Are Left and Right properties properly accessible (with public setters, or modified via the recursive methods)?

Fixing the root assignment in Add and Remove is almost certainly the key to resolving your issues. Once you get that right, your BST operations should start behaving as expected.

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