問題を単純にしてみる

C#

難しい原因は、

  1. 左の部分木を走査
  2. 自分の値を走査
  3. 右の部分木を走査

という感じで、再帰する部分が2ヶ所あることだと思う。ということで、まずは、

左の子を無視して、自分→右の子と走査する

という感じで、ものすごく簡単にしてみた。するとこうなる。

/// <summary>内部イテレータ</summary>
public void ForEach(Action<T> action)
{
  JobHolder holder = new JobHolder();
  ForEachDetailRight(this, action, holder);
  while (null != holder.Job)
  {
    holder.Job();
  }
}

/// <summary>自分と右の子だけを走査する</summary>
static void ForEachDetailRight(
  TreeNode<T> node,
  Action<T> action,
  JobHolder holder)
{
  action(node._value);
  holder.Job =
    node._right == null ?
    (Action)null :
    () => ForEachDetailRight(node._right, action, holder);
}

これは簡単。配列の時とほとんど変わらない。

次に、

右の子は無視して、左の子→自分と走査する

ようにしようとしたけど...、これができない！これはちょうど配列を逆にたどる感じだと思う。
この2つができたら、どうにかやって完全なイテレータができそうな気がするのだが。いや、直観だから勘違いかもしれんけど。