使用堆栈的二进制搜索树

Question

我正在尝试创建一个二进制搜索树，而不使用递归遍历该树。附加的代码用于初始化树，但当我试图遍历它时，当我试图在GetEnumerator()方法中推入堆栈时，它总是给我"object reference not set to instant of object“。我意识到这意味着我需要推送一个实例，而不是类本身，但是我怎么才能创建一个" this“的实例呢？或者，使用stack实现的唯一方法是创建一个单独的类来保存树？代码如下：

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

public class BinarySearchTree : IEnumerable<int>
{
    public int value;
    public BinarySearchTree left;
    public BinarySearchTree right;
    Stack<BinarySearchTree> stacks;
    public BinarySearchTree(int value)
    {
        this.value = value;
    }

    public BinarySearchTree(IEnumerable<int> values)
    {
        this.value = values.First();
        foreach (var val in values.Skip(1))
        {
            this.Add(val);
        }
    }
    public int Value
    {
        get
        {
            return this.value;
        }
    }

    public BinarySearchTree Left
    {
        get
        {
            return this.left;
        }
    }

    public BinarySearchTree Right
    {
        get
        {
            return this.right;
        }
    }

    public void Add(int value)
    {
        BinarySearchTree current_node = this;
        while (current_node.left != null && current_node.right != null)
        {
            if (value <= current_node.value)
            {
                current_node = current_node.left;
            }
            else
            {
                current_node = current_node.right;
            }
        }
        if (value <= current_node.value)
        {
            current_node.left = new BinarySearchTree(value);
            //return current_node;
        }
        else
        {
            current_node.right = new BinarySearchTree(value);
            //return current_node;
        }
    }

    public BinarySearchTree GetValueAtNode()
    {
        
    }
    public IEnumerator<int> GetEnumerator()
    {
        BinarySearchTree current_node = this;
        stacks.Push(current_node);
        while (stacks.Count != 0){
            if (current_node.left != null)
            {
                stacks.Push(current_node);
                current_node = current_node.left;
            }
            yield return stacks.Peek().value;
            current_node = stacks.Peek().right;
            stacks.Pop();
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

错误消息为：

BinarySearchTreeTests.Can_sort_complex_tree:
    Outcome: Failed
    Error Message:
    System.NullReferenceException : Object reference not set to an instance of an object.
    Stack Trace:
       at BinarySearchTree.GetEnumerator()+MoveNext() in c:\Users\320145763\Exercism\csharp\binary-search-tree\BinarySearchTree.cs:line 78
   at BinarySearchTreeTests.Can_sort_complex_tree() in c:\Users\320145763\Exercism\csharp\binary-search-tree\BinarySearchTreeTests.cs:line 84

相关的单元测试是：

using System.Linq;
using Xunit;

public class BinarySearchTreeTests
{
    [Fact]
    public void Can_sort_complex_tree()
    {
        var tree = new BinarySearchTree(new[] { 2, 1, 3, 6, 7, 5 });
        Assert.Equal(new[] { 1, 2, 3, 5, 6, 7 }, tree.AsEnumerable());
    }
}

Answer 1

一些问题：

• Add中的while条件不正确，可能是只有一个子引用为null，并且while循环后面的代码将覆盖现有的子引用，从而可能会丢失树的一部分。最简单的方法可能是执行一个while (true)，并在选择的方向上没有子节点时立即跳出循环，并创建一个新节点来填补这个空白。

• stacks不应该是实例成员，而应该是GetEnumerator的局部变量，否则将使两个正在执行的GetEnumerator迭代器干扰彼此的堆栈需要。

• stacks永远不会初始化为实际的Stack实例。您需要new Stack<BinarySearchTree>() somewhere...

• GetEnumerator的逻辑不是(完全)正确的。例如，current_node = stacks.Peek().right;可能会将null赋值给current_node，以便您在下一次迭代中获得异常。

以下是对两个受影响的方法的更正：

    public void Add(int value)
    {
        BinarySearchTree current_node = this;
        while (true)
        {
            if (value <= current_node.value) {
                if (current_node.left == null) {
                    current_node.left = new BinarySearchTree(value);
                    break;
                }
                current_node = current_node.left;
            } else {
                if (current_node.right == null) {
                    current_node.right = new BinarySearchTree(value);
                    break;
                }
                current_node = current_node.right;
            }
        }
    }

    public IEnumerator<int> GetEnumerator()
    {
        Stack<BinarySearchTree> stacks = new Stack<BinarySearchTree>();
        stacks.Push(this);
        while (stacks.Count != 0){
            BinarySearchTree current_node = stacks.Peek();
            while (current_node.left != null) {
                current_node = current_node.left;
                stacks.Push(current_node);
            }
            while (stacks.Count != 0){
                current_node = stacks.Peek();
                yield return current_node.value;
                stacks.Pop();
                if (current_node.right != null) {
                    stacks.Push(current_node.right);
                    break;
                }
            }
        }
    }