在构建了一个由 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()
实现,因为我必须返回一个bool . 如果我确实将 _current
设置为适当的节点,则为True,如果我在最后,则为false .
我该如何实施 public bool MoveNext()
?我无法解决的主要问题是,如果我想将 BSTNode<Tkey,TValue> Next()
转换为 bool MoveNext()
,我必须 return true
而不是简单地访问节点 BSTNode<Tkey,TValue> result = _current;
,并且只有在设置 _current = _current.Right;
之后我才显然无法做到 .
2 回答
调用者循环遍历枚举(可能在foreach循环中) . 因此,每次要返回结果时都可以中止循环 . 出现问题,因为必须在确定结果后执行
_current = _current.Right;
. 因此我引入了一个新的变量_result
.请注意,循环遍历枚举包括首先调用
MoveNext()
并测试布尔结果 . 然后使用Current
返回的值,如果返回true
.老实说,对于像这样的非trival枚举器,最好只使用.NET内置的工具 . 只需返回
IEnumerator<BSTNode<Tkey,TValue>>
并使用yield return
关键字,它就可以自动将您编写的代码转换为枚举器,只需进行非常小的调整 .如果你很好奇,这里是它在幕后制作的IEnumerator类的编译器生成代码