无法在递归方法中设置对象

Question

我正在尝试向二叉搜索树添加一个节点。这是比较两个节点的地方 - 您要添加的节点和树中的一个节点（第一次是它的根节点）。

    ...
    Compare(newNode, tree.root);
    ...

    public static void Compare(Node newN, Node comN)
        {
            if (comN == null)
            {
                comN = newN;
                return;
            }
            else
            {
                if (newN.data < comN.data)
                { Compare(newN, comN.left); }
                else if (newN.data > comN.data)
                { Compare(newN, comN.right); }
                else if (newN == comN)
                    return;
            }
        }
        // .data = int value of the node

当我通过时：

在"comN = newN;"部分，设置节点。然而，在"return;"之后它跳回了一个级别并且left/right节点（我们之前设置的节点）仍然设置为null。

有什么建议吗？（很抱歉可能使用不正确的术语，我是新手）

Answer 1

由于 C# 传递参数的方式，默认情况下，您使用的是本地引用。将 comN 设置为 newN 不会复制值：它将您的本地引用设置为同一对象，而不更新调用代码中的引用。您可以通过如下更改代码来获得预期的行为：

Compare(newNode, ref tree.root);
...

public static void Compare(Node newN, ref Node comN)
    {
        if (comN == null)
        {
            comN = newN;
            return;
        }
        else
        {
            if (newN.data < comN.data)
            { Compare(newN, ref comN.left); }
            else if (newN.data > comN.data)
            { Compare(newN, ref comN.right); }
            else if (newN == comN)
                return;
        }
    }

有关引用类型和参数的详细信息，请参阅 Passing Reference-Type Parameters (C# Programming Guide)。

Answer 2

我将把它称为 class BST 而不是 Node 因为它使正在发生的事情更清楚一些。假设它被定义为接受一个 data 和一个左右节点作为参数：

// C# 6 for brevity
class BST
{
    public int Data { get; }
    public BST Left { get; }
    public BST Right { get; }

    public Bst(int data, BST left, BST right) 
    {
        Data = data;
        Left = left;
        Right = right;
    }
}

您的插入算法可以定义如下：

static class BSTExtensions
{
    public static BST Insert(this BST bst, BST n)
    {
        if (bst == null)
            return n;

        if (n.Data < bst.Data)
            return new BST(bst.Data, bst.Left.Insert(n), bst.Right);
        if (n.Data > bst.Data)
            return new BST(bst.Data, bst.Left, bst.Right.Insert(n));

        return bst;
    }
}

很容易理解这里发生的事情。

如果您应该比较的节点不存在，那么这就是新节点应该占据的位置。
如果新结点的值小于当前结点的值，则插入左子树。
如果新节点的值大于当前节点的值，则插入右子树。
如果值相等（唯一剩余的可能性），则不需要更改。只是 return 原始树。

虽然我也让这个例子中的树不可变，但如果你在你的 class 中实现 setter，你可以更有效地做到这一点，同时仍然不需要 ref.

无法在递归方法中设置对象

Can't set an object in a recursive method

c#

methods

recursion

binary-search-tree