c# – 二进制搜索树IEnumerator.MoveNext()在遍历实现中非递归.

这就是我构建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
}

我传入根节点,_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()实现,因为我必须返回一个bool.如果我确实将_current设置为适当的节点,则为true,如果我在最后,则为false.

我该如何实现公共bool MoveNext()？我无法解决的主要问题是,如果我想转换BSTNode< Tkey,TValue> Next()into bool MoveNext()我必须返回true而不是简单地访问节点BSTNode< Tkey,TValue> result = _current;并且只有在那之后才设置_current = _current.Right;我显然做不到.