二叉搜索树IEnumerator.MoveNext()非递归中序遍历实现。如何？

Question

在构建了由 BSTNode<Tkey,TValue> 个节点组成的二叉搜索树 BST<Tkey,TValue> 之后，我正在尝试为其实现 IEnumerable 接口。

这就是我构建 BSTNodeEnumrator<Tkey,TValue>:

的方式

public class BSTNodeEnumerator<TKey, TValue> : IEnumerator<BSTNode<TKey, TValue>> where TKey : IComparable<TKey>
{
    private Stack<BSTNode<TKey, TValue>> _stack;

    public BSTNodeEnumerator(BSTNode<TKey, TValue> root)
    {
        _stack = new Stack<BSTNode<TKey, TValue>>();
        _current = null;
        _root = root;
    }

    // ... rest of the implementation
}

我传入root节点，_current是枚举的结果。我也在尝试为此使用堆栈，因为我不像在 AVL BST 中那样跟踪父节点。

现在我希望枚举器以非递归的方式按顺序+遍历树。由于 bst 的属性，这也应该导致排序的枚举，这很好，因为这正是我想要实现的。

伪代码顺序遍历的非递归算法wikipedia article

    iterativeInorder(node)
  s ← empty stack
  while (not s.isEmpty() or node ≠ null)
    if (node ≠ null)
      s.push(node)
      node ← node.left
    else
      node ← s.pop()
      visit(node)
      node ← node.right

我们可以将算法转换成这个c#代码：

public BSTNode<Tkey,TValue> Next() 
{
   while (_stack.Count > 0 || _current != null) 
    {
         if (_current != null)
         {
          _stack.Push(_current);
          _current = _current.left;
         }
         else
         {
          _current = _stack.Pop();
          BSTNode<Tkey,TValue> result = _current;
          _current = _current.Right;
         }
    }
    return result;
}

但这不是必需的 bool MoveNext() 实现，因为我必须 return 一个布尔值。如果我确实将 _current 设置为适当的节点，则为 True；如果我在末尾，则为 false。

我应该如何实施 public bool MoveNext()？我无法解决的主要问题是，如果我想将 BSTNode<Tkey,TValue> Next() 转换为 bool MoveNext()，我必须 return true 而不是简单地访问节点 BSTNode<Tkey,TValue> result = _current; 和只有在那组 _current = _current.Right; 之后，我显然做不到。

Answer 1

老实说，对于像这样的复杂枚举器，最好只使用 .NET 中内置的工具。它可以自动将您写入的代码转换为枚举器，只需返回 IEnumerator<BSTNode<Tkey,TValue>> 并使用 yield return 关键字进行非常小的调整。

class BSTNode<TKey, TValue> : IEnumerable<BSTNode<TKey, TValue>>
     where TKey : IComparable<TKey>
{
    public IEnumerator<BSTNode<TKey, TValue>> GetEnumerator()
    {
        var stack = new Stack<BSTNode<TKey, TValue>>();
        var current = this;
        while (stack.Count > 0 || current != null)
        {
            if (current != null)
            {
                stack.Push(current);
                current = current.Left;
            }
            else
            {
                current = stack.Pop();
                yield return current;
                current = current.Right;
            }
        }
    }

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

    public BSTNode<TKey, TValue> Left { get; set; }

    public BSTNode<TKey, TValue> Right { get; set; }

    public TKey Key { get; set; }

    public TValue Value { get; set; }
}

如果您好奇，这里是编译器为 IEnumerator class 在幕后制作的代码生成的代码

[CompilerGenerated]
  private sealed class <GetEnumerator>d__0 : IEnumerator<BSTNode<TKey, TValue>>, IDisposable, IEnumerator
  {
    private int <>1__state;
    private BSTNode<TKey, TValue> <>2__current;
    public BSTNode<TKey, TValue> <>4__this;
    private Stack<BSTNode<TKey, TValue>> <stack>5__1;
    private BSTNode<TKey, TValue> <current>5__2;

    BSTNode<TKey, TValue> IEnumerator<BSTNode<TKey, TValue>>.Current
    {
      [DebuggerHidden] get
      {
        return this.<>2__current;
      }
    }

    object IEnumerator.Current
    {
      [DebuggerHidden] get
      {
        return (object) this.<>2__current;
      }
    }

    [DebuggerHidden]
    public <GetEnumerator>d__0(int <>1__state)
    {
      base.\u002Ector();
      this.<>1__state = param0;
    }

    [DebuggerHidden]
    void IDisposable.Dispose()
    {
    }

    bool IEnumerator.MoveNext()
    {
      switch (this.<>1__state)
      {
        case 0:
          this.<>1__state = -1;
          this.<stack>5__1 = new Stack<BSTNode<TKey, TValue>>();
          this.<current>5__2 = (BSTNode<TKey, TValue>) null;
          goto label_8;
        case 1:
          this.<>1__state = -1;
          this.<current>5__2 = this.<current>5__2.Right;
          break;
        default:
          return false;
      }
label_7:
label_8:
      if (this.<stack>5__1.Count <= 0 && this.<current>5__2 == null)
        return false;
      if (this.<current>5__2 != null)
      {
        this.<stack>5__1.Push(this.<current>5__2);
        this.<current>5__2 = this.<current>5__2.Left;
        goto label_7;
      }
      else
      {
        this.<current>5__2 = this.<stack>5__1.Pop();
        this.<>2__current = this.<current>5__2;
        this.<>1__state = 1;
        return true;
      }
    }

    [DebuggerHidden]
    void IEnumerator.Reset()
    {
      throw new NotSupportedException();
    }
  }

Answer 2

调用方正在遍历枚举（可能在 foreach 循环中）。因此，您可以在每次想要 return 结果时中止循环。问题来了，因为_current = _current.Right;必须在结果确定后才执行。因此我引入了一个新变量 _result.

private BSTNode<TKey, TValue> _result;

bool IEnumerator.MoveNext()
{
    while (_stack.Count > 0 || _current != null)
    {
        if (_current != null)
        {
            _stack.Push(_current);
            _current = _current.left;
        }
        else
        {
            _current = _stack.Pop();
            _result = _current;
            _current = _current.Right;
            return true;
        }
    }
    return false;
}

BSTNode<TKey, TValue> IEnumerator<BSTNode<TKey, TValue>>.Current
{
    get { return _result; }
}

请注意，遍历枚举包括首先调用 MoveNext() 和测试布尔结果。如果 true 被 return 编辑，则使用 Current 编辑的值 return。

二叉搜索树IEnumerator.MoveNext()非递归中序遍历实现。如何？

Binary search tree IEnumerator.MoveNext() non recursive in order traversal implementation. How to?

c#

algorithm

ienumerable

enumerator

binary-search-tree