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

概述在构建了二进制搜索树BST< Tkey,TValue>之后.它由BSTNode< Tkey,TValue>组成.我试图为它实现IEnumerable接口. 这就是我构建BSTNodeEnumrator的方法< Tkey,TValue>： public class BSTNodeEnumerator<TKey, TValue> : IEnumerator<BSTNode<TKey, TValue>> 在构建了二进制搜索树BST< Tkey,TValue>之后.它由BSTNode< 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}

我传入根节点,_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;我显然做不到.

解决方法 调用者循环遍历枚举(可能在foreach循环中).因此,每次要返回结果时都可以中止循环.出现问题,因为_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()并测试布尔结果.然后使用Current返回的值返回true.

总结

以上是内存溢出为你收集整理的c# – 二进制搜索树IEnumerator.MoveNext()在遍历实现中非递归.如何？全部内容，希望文章能够帮你解决c# – 二进制搜索树IEnumerator.MoveNext()在遍历实现中非递归.如何？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。