木構造の外部イテレータ

ちょっと横道へそれる。
「ツリー構造用の外部/内部イテレータの実装 - terazzoの日記」には、以下の3つのアプローチによるm分木の外部イテレータの実装例がある。

1. いったん木構造を配列にしてから、その配列のイテレータを返す
2. スタックで現在位置を保持しておく
3. 残りの要素を処理するオブジェクトを作る

これら以外のアプローチで、2分木の外部イテレータ（通りがけ順の深さ優先探索）を作ってみた。

2分木のノード

namespace TreeApp
{
  class IntTreeNode
  {
    int _value;

    IntTreeNode _left;

    IntTreeNode _right;

    IntTreeNode _parent;

    public IntTreeNode(int value, IntTreeNode left, IntTreeNode right)
    {
      _value = value;
      _left = left;
      _right = right;
    }

    public int Value
    {
      get { return _value; }
    }

    public IntTreeNode Parent
    {
      get { return _parent; }
      set { _parent = value; }
    }

    public IntTreeNode Left
    {
      get { return _left; }
    }

    public IntTreeNode Right
    {
      get { return _right; }
    }
  }
}

2分木

using System.Collections.Generic;

namespace TreeApp
{
  class IntTree : IEnumerable<int>
  {
    IntTreeNode _root;

    public IntTree()
    {
      _root = null;
    }

    public IntTreeNode Root
    {
      get { return _root; }
    }

    public IEnumerator<int> GetEnumerator()
    {
      return new IntTreeIterator(this);
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
      return GetEnumerator();
    }

    static public IntTree CreateSampleTree()
    {
      // 深さ3（リーフ）
      IntTreeNode node00 = new IntTreeNode(0, null, null);
      IntTreeNode node02 = new IntTreeNode(2, null, null);
      IntTreeNode node04 = new IntTreeNode(4, null, null);
      IntTreeNode node06 = new IntTreeNode(6, null, null);
      IntTreeNode node08 = new IntTreeNode(8, null, null);
      IntTreeNode node10 = new IntTreeNode(10, null, null);
      IntTreeNode node12 = new IntTreeNode(12, null, null);
      IntTreeNode node14 = new IntTreeNode(14, null, null);

      // 深さ2
      IntTreeNode node01 = new IntTreeNode(1, node00, node02);
      node00.Parent = node01;
      node02.Parent = node01;
      IntTreeNode node05 = new IntTreeNode(5, node04, node06);
      node04.Parent = node05;
      node06.Parent = node05;
      IntTreeNode node09 = new IntTreeNode(9, node08, node10);
      node08.Parent = node09;
      node10.Parent = node09;
      IntTreeNode node13 = new IntTreeNode(13, node12, node14);
      node12.Parent = node13;
      node14.Parent = node13;

      // 深さ1
      IntTreeNode node03 = new IntTreeNode(3, node01, node05);
      node01.Parent = node03;
      node05.Parent = node03;
      IntTreeNode node11 = new IntTreeNode(11, node09, node13);
      node09.Parent = node11;
      node13.Parent = node11;

      // 深さ0
      IntTreeNode node07 = new IntTreeNode(7, node03, node11);
      node03.Parent = node07;
      node11.Parent = node07;

      IntTree tree = new IntTree();
      tree._root = node07;
      return tree;
    }
  }
}

2分木の外部イテレータ

using System;
using System.Collections.Generic;

namespace TreeApp
{
  class IntTreeIterator : IEnumerator<int>
  {
    IntTree _tree;

    IntTreeNode _current;
    
    bool _init;

    public IntTreeIterator(IntTree tree)
    {
      _tree = tree;
      Reset();
    }

    void CheckDisposed()
    {
      if (_tree == null)
      {
        const string msg = "This object was already disposed.";
        throw new InvalidOperationException(msg);
      }
    }

    IntTreeNode GetMinLeaf(IntTreeNode node)
    {
      while (node != null && node.Left != null)
      {
        node = node.Left;
      }
      return node;
    }

    public int Current
    {
      get
      {
        CheckDisposed();
        return _current.Value;
      }
    }

    public void Dispose()
    {
      CheckDisposed();
      _tree = null;
    }

    object System.Collections.IEnumerator.Current
    {
      get { return Current; }
    }

    public bool MoveNext()
    {
      CheckDisposed();

      if (_init)
      {
        _current = GetMinLeaf(_tree.Root);
        _init = false;
        return _current != null;
      }

      if (_current == null)
      {
        return false;
      }

      if (_current.Right != null)
      {
        _current = _current.Right;
        _current = GetMinLeaf(_current);
        return true;
      }
      else
      {
        while (true)
        {
          IntTreeNode old = _current;
          _current = _current.Parent;

          // ルートまで全部終わった
          if (_current == null)
          {
            return false;
          }

          if (old == _current.Left)
          {
            return true;
          }
          // 右の子から来た場合は素通り
        }
      }
    }

    public void Reset()
    {
      CheckDisposed();
      _current = null;
      _init = true;
    }
  }
}

Main

using System;

namespace TreeApp
{
  class Program
  {
    static void Main(string[] args)
    {
      IntTree tree = IntTree.CreateSampleTree();
      foreach (int n in tree)
      {
        Console.Write(n + " ");
      }
    }
  }
}

実際に動かしてみた

http://ideone.com/DkZId