recursion - 再帰を伴わない複合パターン反復子

Question

再帰を使わずに複合 (ツリー) 構造のイテレータを書いたり考えたりした人はいますか? もしそうなら、あなたのアイデアを共有できますか？ありがとう

編集：Java for langを考えていました。

Answer 1

再帰なしでツリーをトラバースするのは簡単です。二分木を仮定すると、各ノードはおそらく他のノードへの 3 つの参照を持っています。左の子、右の子、および親。したがって、深さ優先の左から右の反復順序を想定すると、左の子がない場合は、while-lop (疑似コードwhile current.left-child != null, current = current.left-child) で左の子の参照に従い、右の子を試します。右の子もいない場合は、右の子が見つかるまで上に移動します ( while current.right-child == null, current = current.parent)

言語を指定していませんが、再帰を避けたいので、何らかの命令型言語であると仮定すると、上記が可能になるはずです。

つまり、イテレータは、現在のノードへの参照と、それがどの方向に移動しているかについての情報を保持する必要があります。

Answer 2

このSOの質問から、いくつかのインスピレーションを得ることができます。 再帰なしのバイナリツリーのポストオーダートラバーサル 必要なのは、アルゴリズムを非バイナリツリーに拡張することだけです。