binary-search-Tree＆＃x27;删除函数不适合2个孩子节点

Question

我正在学习二进制搜索树和递归。我可以通过叶子和单个子节点获得预期的结果。但是，每当我尝试删除带有2个子节点的节点，但没有收到预期的结果。删除rootnode（12）时，如何将rootnode设置为18 ...因为18是root右子右节点的值？

/* 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

弄清楚了。我交换了两行代码。在更新根节点之前，我试图删除右儿童的最左节点。

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;
        }
    }
}