可以'；t在递归方法中设置对象

本文关键字：递归方法 设置 对象 可以 | 更新日期: 2023-09-27 17:59:24

我正在尝试向二进制搜索树添加一个节点。这里有两个节点的比较——要添加的节点和树中的一个节点（第一次是它的根）。

    ...
    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；"之后，它会跳回一个级别，并且左/右节点（我们之前设置的节点）仍然设置为null。

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

可以'；t在递归方法中设置对象

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

有关引用类型和参数的更多信息，请参阅传递引用类型参数（C#编程指南）。

我将把这个类称为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;
    }
}

很容易理解这里发生了什么。

  1. 如果要与之进行比较的节点不存在，那么这就是新节点应该占据的位置
  2. 如果新节点的值小于当前节点中的值，请插入到左侧子树中
  3. 如果新节点的值大于当前节点的值，请插入右侧子树中
  4. 如果值相等（剩下的唯一可能），则不需要更改。只需返回原始树即可

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

相关文章：