我的算法中将节点添加到二叉树的缺陷在哪里？

Question

我的方法看起来像

static Node _root = null;

static void AddToTree(int val)
{
    AddToTree(val, ref _root);
}

static void AddToTree(int val, ref Node root)
{
    if(root == null)
        root = new Node() { Val = val };
    Node left = root.Left, right = root.Right;
    if(root.Val > val)
        AddToTree(val, ref left);
    else if(root.Val < val)
        AddToTree(val, ref right);
}

我怎么看它失败的是我跑

    int[] vals = { 2, 1, 5, 3, 8 };
    foreach(int i in vals)
        AddToTree(i);
    Print();

哪个使用

static void Print()
{
    if(_root == null)
        return;
    LinkedList<int> vals = new LinkedList<int>();
    Queue<Node> q = new Queue<Node>();
    q.Enqueue(_root);
    while(q.Count > 0)
    {
        Node front = q.Dequeue();
        vals.AddLast(front.Val);
        if(front.Right != null)
            q.Enqueue(front.Right);
        if(front.Left != null)
            q.Enqueue(front.Left);
    }
    Console.WriteLine(string.Join(",", vals));
}

我看到的输出是

2

即添加的第一个元素,没有其他元素.

知道我哪里错了吗？

Answer 1

此代码序列不符合您的想法:

Node left = root.Left;
Foo(ref left);

你是通过left参考而不是root.Left.现在Foo()重新分配时left,只left会受影响,而不是root.Left.

当然,您不能通过引用传递属性,因此解决方案是root.Left = left在Foo()返回后重新分配.