Tree に対する STL 風イテレータ

wordring 用に、木に対するイテレータを考察しました。

必要なメンバ関数

STL コンテナのイテレータは、前後へ移動できれば十分です。　しかし Tree のイテレータは、前後の移動だけでは不十分です。

以下の移動が可能であれば、Tree 内のノードを自由に移動することが出来ます。

• 最初の子
• 子の終端
• 親
• 次の同胞
• 前の同胞

STL 風に考えると、それぞれ以下の関数名になると思います。

• begin()
• end()
• parent()
• operator++()
• operator--()

tree 、 tag_tree 、 trie 三種類の木を実装してみました。　

走査イテレータ・アダプタ

Tree イテレータの基本は、これで十分だと思います。　しかし実用において、このイテレータを直接利用することはほとんどないでしょう。使ってみると、とにかく面倒くさいです。

実用的には、走査用のイテレータ・アダプタを使うでしょう。

Wikipedia は、4つの走査順を紹介しています。 これらは、基本 Tree イテレータに対するアダプタとして実装できます。　

よく使われる走査順は、（ HTML や XML の書き順のような）行きがけ順でしょう。

※本稿で定義した5つの移動方向で全ての走査順を実装できるということは、5つの移動方向で十分であることを示すと思います。

tree_iterator 、 level_order_tree_iterator 二種類の走査イテレータ・アダプタを実装してみました。