Удалить узел из двоичного дерева поиска итеративно

Question

У меня есть три метода удаления узла в BST. Методы RemoveRec и RemoveNonRec осуществляют рекурсивный и итеративный поиск узла, а Remove удаляет найденный узел.

private void RemoveRec(int value, ref TreeNode node)
{
    if (node != null)
    {
        if (value < node.Value)
        {
            RemoveRec(value, ref node.Left);
        }
        else if (value > node.Value)
        {
            RemoveRec(value, ref node.Right);
        }
        else
        {
            Remove(value, ref node);
        } 
    } 
}

public void RemoveNonRec(int value)
{
    ref TreeNode node = ref this.Root;
    while (node != null)
    {
        if (value < node.Value)
        {
            node = node.Left;
        }
        else if (value > node.Value)
        {
            node = node.Right;
        }
        else
        {
            Remove(value, ref node);
            break;
        }
    }
}

private void Remove(int value, ref TreeNode node)
{
    if (node != null)
    {
        if (node.Counter > 1)
        {
            --node.Counter;
            Console.WriteLine("Deleted element: {0}, elements in the node: {1}", node.Value, node.Counter);
        }
        else
        {
            int vMes = node.Value;

            if (node.Left == null && node.Right == null)
            {
                node = null;
            }
            else if (node.Left != null && node.Right == null)
            {
                node = node.Left;
            }
            else if (node.Left == null && node.Right != null)
            {
                node = node.Right;
            }
            else
            {
                if (node.Right.Left == null)
                {
                    node.Right.Left = node.Left;
                    node = node.Right;
                }
                else
                {
                    TreeNode p = node.Right;
                    while (p.Left.Left != null)
                       p = p.Left;
                    TreeNode q = p.Left;
                    p.Left = q.Right;
                    q.Left = node.Left;
                    q.Right = node.Right;
                    node = q;
                }
            }

            Console.WriteLine("Deleted node: {0}", vMes);
        }
    }
}

Проблема в том, что RemoveNonRec работает неправильно, и я немного знаю почему. Однако я понятия не имею, как заставить это работать.

Answer 1

Мне удалось решить проблему. Теперь все отлично работает

public void RemoveNonRec(int value)
{
    TreeNode node = Root;
    while (node != null)
    {
        if (value < node.Value)
        {
            if (node.Left != null && node.Left.Value == value)
            {
                Remove(value, ref node.Left);
                break;
            }
            node = node.Left;
        }
        else if (value > node.Value)
        {
            if (node.Right != null && node.Right.Value == value)
            {
                Remove(value, ref node.Right);
                break;
            }
            node = node.Right;
        }
        else
        {
            Remove(value, ref Root);
            break;
        }
    }
}

Answer 2

В качестве решения вы можете добавить эти два метода в свой класс TreeNode, которые возвращают ссылки.

private TreeNode left;
private TreeNode right;

public ref TreeNode GetLeft()
{
    return ref left;
}

public ref TreeNode GetRight()
{
    return ref right;
}

Так что вы больше не получаете доступ к свойствам. Вместо этого вы вызываете эти два метода:

private void RemoveRec(int value, ref TreeNode node)
{
    if (node != null)
    {
        if (value < node.Value)
        {
            RemoveRec(value, ref node.GetLeft());
        }
        else if (value > node.Value)
        {
            RemoveRec(value, ref node.GetRight());
        }
        else
        {
            Remove(value, ref node);
        }
    }
}

public void RemoveNonRec(int value)
{
    if(value == Root.Value)
    {
        Remove(value, ref Root);
    }
    else
    {
        TreeNode node = Root;

        while (node != null)
        {
            if (value < node.Value)
            {
                node = node.GetLeft();
            }
            else if (value > node.Value)
            {
                node = node.GetRight();
            }
            else
            {
                Remove(value, ref node);
                break;
            }
        }
    }
}

private void Remove(int value, ref TreeNode node)
{
    if (node != null)
    {
        if (node.Counter > 1)
        {
            --node.Counter;
            Console.WriteLine("Deleted element: {0}, elements in the node: {1}", node.Value, node.Counter);
        }
        else
        {
            int vMes = node.Value;
            ref TreeNode left = ref node.GetLeft();
            ref TreeNode right = ref node.GetRight();

            if (left == null && right == null)
            {
                node = null;
            }
            else if (left != null && right == null)
            {
                node = left;
            }
            else if (left == null && right != null)
            {
                node = right;
            }
            else
            {
                if (node.GetRight().GetLeft() == null)
                {
                    node.GetRight().GetLeft() = left;
                    node = right;
                }
                else
                {
                    TreeNode p = right;
                    ref TreeNode leftLeft = ref p.GetLeft().GetLeft();
                    while (leftLeft != null)
                        p = p.GetLeft();
                    ref TreeNode q = ref p.GetLeft();
                    p.GetLeft() = q.GetRight();
                    q.GetLeft() = node.GetLeft();
                    q.GetRight() = node.GetRight();
                    node = q;
                }
            }

            Console.WriteLine("Deleted node: {0}", vMes);
        }
    }
}