首页 文章

二进制搜索树IEnumerator.MoveNext()在递归实现中非递归 . 如何?

提问于
浏览 1666
3

在构建了一个由 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 回答

  • 5

    调用者循环遍历枚举(可能在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 .

  • 2

    老实说,对于像这样的非trival枚举器,最好只使用.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类的编译器生成代码

    [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();
        }
      }
    

相关问题