时间戳

首页 > 解决方案 > 迭代地从二叉搜索树中删除一个节点

c# - 迭代地从二叉搜索树中删除一个节点

问题描述

我有三种方法用于删除 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它不能正常工作，我稍微知道为什么。但是我不知道如何使它工作。

标签： c#recursioniterationbinary-search-tree

解决方案

作为一种解决方案，您可以在返回引用的 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);
        }
    }
}

推荐阅读