再帰の代わりに明示的なスタックを使用して、preorder、inorder、およびpostorderの深さ優先のツリートラバーサルを繰り返し行う方法を示す、多くの記事と本（Stack Overflowの回答）を見てきました。 例：https://en.wikipedia.org/wiki/Tree_traversal#Depth-first_search_2再帰のないバイナリツリートラバーサルの直感的な説明
プレオーダートラバーサルは単純ですが、他のものは複雑で、はっきりしないと思います。
これらのアルゴリズムを直感的に説明するソースがあります（記事や書籍が好きであることが多いので）、誰かが最初にそれらを思い付く方法を知ることができますか？
プレオーダー：ノードを訪問し、各子を処理することによってノードが処理されます。
Inorder：ノードは、左の子を処理し、ノードを訪れ、次に右の子を処理することによって処理されます。
PostOrder（DFS）：ノードは、各子を処理し、ノードを訪問することによって処理されます。
すべての場合、すぐにはできない作業を保存するためにスタックが使用されます。子ノードの処理を延期する必要があるのは1つだけなので、事前注文のケースが最も簡単です。
プレオーダー：スタックには処理するノードがあります。ノードを処理するには、ノードにアクセスし、スタック上の正しい子をプッシュし、次に左の子を処理します。左の子がない場合は、スタックから1つを取得します。
Inorderもかなり簡単です。スタックは、プロセスへとノードを訪問するノードを格納するために持っていますが、プロセスへのノードは常にちょうどそう、訪問したノードの右の子である：
INORDER：スタックが訪問するノードを保持しています。スタックからノードを取得すると、そのノードを参照して、適切な子を処理します。ノードを処理するとき、ノードをスタックに置き、左の子を処理します。
スタックを処理するために、とノードを訪問するノードを格納するために持っている、と彼らはINORDERケースにあるように、彼らは常に単純に関連していないので、後順はトリッキーです。スタックは何とかどのようなものかを示さなければなりません。
後順：
あなたはこのようにそれを行うことができますスタックがすでに処理された子供の数とともに、訪問するノードまたはプロセスを保持しています。スタックからエントリ
(n,x)を処理するには、< = x個の子がある場合はノードnにアクセスしてください。そうでなければ、(n,x+1)をスタックに置き、ノードの最初の未処理の子を処理します。
技術的には、スタックを使用するのは再帰であり、明示的ではありません。メソッドを何度も呼び出すのと同様に、スタックが使用されるため、暗黙的に再帰されます。一方の方法がコールスタックを使用し、もう一方の方法がノードスタックを使用するということだけです。何らかの再帰をせずに木をたどることはできません。 –
@DaneBrick、*技術的に*、それは間違っています。関数がそれ自身の観点から定義されているときの再帰です。 –
@MattTimmermans私は理解していますが、OPがスタックとのツリートラバーサルを理解するのに問題があるが、再帰を伴うトラバーサルを理解できる場合は、両方のトラバーサルメソッドが実際に非常に似ていることに注意したいと思います。スタックは再帰で使用されるためです。 –