木構造の外部イテレータ
ちょっと横道へそれる。
「ツリー構造用の外部/内部イテレータの実装 - terazzoの日記」には、以下の3つのアプローチによるm分木の外部イテレータの実装例がある。
これら以外のアプローチで、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 + " "); } } } }