内部イテレータできた!

ForEachDetailLeftとForEachDetailRightを単純に組み合わせてできるわけじゃなかった。だけどヒントにはなった気がする。やり方は違うけど、結果的に 木構造の外部イテレータ - チキン煮込みチーズミックス4辛 となんか似てる。何がって言われてもよくわからんけど。
ちなみに、前回の状態からこれができるまで、約3時間も費やしております。すばやくなんてできないよ...。

ソースコードは以下。TreeNodeクラスの該当部分のみ。

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

/// <summary>委譲される手続きの入口</summary>
static void ForEachDetail(
  TreeNode<T> root,
  Action<T> action,
  JobHolder holder,
  Action cont)
{
  // rootを根とする部分木の、最小のノードを見つける
  TreeNode<T> leftmost = root;
  while (leftmost._left != null) leftmost = leftmost._left;

  // 見つけたノードから走査開始
  // contは、この部分木の走査が終了したあとにすべきこと
  //   例)この部分木を包むひとつ上の部分木の走査を開始する
  AtLeftMost(leftmost, action, holder, cont);
}

static void AtLeftMost(
  TreeNode<T> leftmost,
  Action<T> action,
  JobHolder holder,
  Action cont)
{
  action(leftmost._value);

  if (leftmost._parent != null)
  {
    if (leftmost == leftmost._parent._left)
    {
      holder.Job =
        () => OnTheWay(leftmost._parent, action, holder);
    }
    else
    {
      holder.Job = cont;
    }
  }
  else
  {
    holder.Job = null;
  }
}

static void OnTheWay(TreeNode<T> node, Action<T> action, JobHolder holder)
{
  action(node._value);

  if (node._right != null)
  {
    TreeNode<T> nextRoot = GetNextRoot(node);
    if (nextRoot == null)
    {
      // 出口はここしかない?
      // ForEachでForEachDetailに渡したnullは使われないな...
      holder.Job =
        () => ForEachDetail(node._right, action, holder, null);
    }
    else
    {
      holder.Job =
        () => ForEachDetail(
          node._right,
          action, holder,
          () => OnTheWay(nextRoot, action, holder));
    }
  }
  else
  {
    if (node._parent != null)
    {
      holder.Job =
        () => OnTheWay(node._parent, action, holder);
    }
    else
    {
      holder.Job = null;
    }
  }
}

static TreeNode<T> GetNextRoot(TreeNode<T> node)
{
  while (node._parent != null)
  {
    if (node._parent._left == node) return node._parent;
    node = node._parent;
  }
  return null;
}

実際に動かしてみた → http://ideone.com/zbXa5
あとはこれを外部イテレータにするだけ。