바이너리 검색 트리 IEnumerator.MoveNext() 탐색 순회가 아닌 재귀 적입니다. 어떻게?

Question

BSTNode<Tkey,TValue> 노드로 구성된 이진 검색 트리 BST<Tkey,TValue>을 만든 후이 노드에 대해 IEnumerable 인터페이스를 구현하려고합니다. I는 root 노드 _current 전달

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 
} 

열거 결과이다

이

는이 BSTNodeEnumrator<Tkey,TValue> 내가 구축 방법이다. 또한 AVL BST처럼 부모 노드를 추적하지 않기 때문에이 스택을 사용하려고합니다.

이제는 열거자가 비 순차적 방식으로 트리를 순서대로 넘어가 길 원합니다. 결과적으로 BST의 특성으로 인해 정렬 된 열거 형을 가져와야합니다. 이는 달성하고자하는 바로 위대한 것입니다.

우리는이 C# 코드로 알고리즘을 변형 할 수있다 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 

이 같이 의사 코드에서 주문 탐색에 대한 비 재귀 알고리즘 :

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을 반환해야만하므로 bool MoveNext() 구현이 필요합니다. 적절한 노드에 _current을 설정하면 true이고, 내가 끝에 있으면 false입니다.

public bool MoveNext()을 어떻게 구현해야합니까? 내가 머리를 감쌀 수없는 주된 이유는 바로 을 bool MoveNext()으로 변환하고 싶다면 단순히 BSTNode<Tkey,TValue> result = _current; 노드를 방문하는 대신 return true을 입력해야하고 그 후에는 분명히 할 수없는 _current = _current.Right;을 설정해야합니다.

Answer 1

는 뒤에서 만든있는 IEnumerator 클래스에 대한 컴파일러 생성 된 코드입니다 고리). 따라서 결과를 반환 할 때마다 루프를 중단 할 수 있습니다. 결과가 결정된 후에 _current = _current.Right;을 실행해야하기 때문에 문제가 발생합니다. 따라서 새로운 변수 _result을 도입하려고합니다. 열거를 통해 반복하는 것은 처음 MoveNext()를 호출하고 부울 결과를 테스트로 구성

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; } 
} 

참고. 그런 다음 true이 반환 된 경우 Current에 의해 반환 된 값을 사용합니다.

Answer 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; } 
} 

---

, 여기에 발신자가 foreach-에 아마 (열거를 통해 반복되는

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