Binary-Search-Tree 的删除功能不适用于 2 child 个节点

Question

我正在学习二叉搜索树和递归。我能够使用叶节点和单个 child 节点获得预期结果。但是，每当我尝试删除具有 2 child 个节点但未收到预期结果的节点时。删除rootNode（12）时，怎么可能rootNode被设置为18...因为18是root的右child右节点的值？

/* Using Pre-Order Traversal
* Original Tree: [12,7,3,7,14,18]
* Expected Result: [14,7,3,7,18]
* Result Tree: [18,7,3,7,18] */

public void DeleteNode(Node rootNode, int deleteValue)
{
    SearchBinaryTree(DeleteNodeHelper, rootNode, deleteValue);
}

public void DeleteNodeHelper(Node node)
{
    if(node != null)
    {
        // 0 child? unlink the node from its parent
        if (node.Left == null && node.Right == null)
        {
            node.Value = 0;
            node.Name = "deleted";
            node.Left = null;
            node.Right = null;
        }
        // 2 child? replace root node with right child's left-most value
        if (node.Left != null && node.Right != null)
        {
            Node rootNodeReplacement = FindLeftMostNode(node.Right);
            SearchBinaryTree(DeleteNodeHelper, node.Right, rootNodeReplacement.Value);
            node.Value = rootNodeReplacement.Value;
        }
        //1 child? replace root node with only child
        else
        {
            node.Value = node.Left != null ? node.Left.Value : node.Right.Value;
            node.Name = node.Left != null ? node.Left.Name : node.Right.Name;
            node.Left = null;
            node.Right = null;
        }
    }
}

public void SearchBinaryTree(Action<Node> action, Node node, int searchValue)
{
    if (node != null)
    {
        if ( node.Value == searchValue)
        {
            action.Invoke(node);
        }
        if (node.Value < searchValue)
        {
            SearchBinaryTree(action, node.Right, searchValue);
        }
        if (node.Value > searchValue)
        {
            SearchBinaryTree(action, node.Left, searchValue);
        }     
    }
}

public Node FindLeftMostNode(Node node)
{
    while (node.Left != null)
    {
        node = node.Left;
    }
    return node;
}

Answer 1

想通了。我交换了两行代码。我试图在更新根节点之前删除 right-child 的 left-most 节点。

public void DeleteNodeHelper(Node node)
{
    if (node != null)
    {
        // 0 child? unlink the node from its parent
        if (node.Left == null && node.Right == null)
        {
            node.Value = 0;
            node.Name = "deleted";
            node.Left = null;
            node.Right = null;
        }
        // 2 child? replace root node with right child's left-most value
        if (node.Left != null && node.Right != null)
        {
            Node rootNodeReplacement = FindLeftMostNode(node.Right);
            node.Value = rootNodeReplacement.Value; //this line was swapped with the one below
            SearchBinaryTree(DeleteNodeHelper, node.Right, rootNodeReplacement.Value);
        }
        //1 child? replace root node with only child
        else
        {
            node.Value = node.Left != null ? node.Left.Value : node.Right.Value;
            node.Name = node.Left != null ? node.Left.Name : node.Right.Name;
            node.Left = null;
            node.Right = null;
        }
    }
}

Binary-Search-Tree 的删除功能不适用于 2 child 个节点

Binary-Search-Tree's remove function doesn't work for 2 child nodes

c#

recursion

binary-search-tree