問題タブ [postorder]

inorder または pre-order 反復トラバーサルではなく、反復ポスト オーダー トラバーサルの Visited フラグを保持する必要があるのはなぜですか。

訪問済みフラグを保持せずにポストオーダートラバーサルを行うことは可能ですか?

プレオーダー、インオーダー、ポストオーダーのツリー トラバーサル アルゴリズムをよく理解しています。（参照）。私はいくつかの用途を理解しています: 二分探索木を順番にトラバースするための in-order 、木のクローンを作成するための pre-order です。しかし、私は一生、注文後のトラバーサルが必要な現実世界のタスクを思いつくことはできません。

例を教えてください。そして、事前注文トラバーサルのより良い使い方を教えてください。

編集: 式ツリーと RPN 以外の例を教えてください。それは本当にすべてのポストオーダーが良いのでしょうか?

スタックを使用してポスト オーダー トラバーサルを実行しようとしていましたが、バイナリへの無効なオペランド タイプのエラーが発生しました。この状況を克服する方法を教えてください。以下はコードです。

開始ルートノードを指定して、すべてのサブツリーノードを返す再帰関数があります。

次のツリー構造の場合：

私がそのように反復しようとすると：

この関数はA値のみを返します。

再帰でy​​ield-returnを使用し、Preorderの要素（この例ではA、B、C、D、E）を取得したいと思います。

（foreachの前にyield returnを配置すると、foreachは発生しません）。

これは可能ですか？

ast.NodeVisitor.generic_visit（）を操作するだけで、Pythonでast.NodeVisitorのインスタンスに対してポストオーダートラバーサルを実行することは可能ですか？これは私がしました：

これは私に与えました：

私はそれが私に与えて欲しい：

どうすればいいですか？行き詰まってください。

非再帰的なポストオーダー バイナリ ツリー トラバーサルのこの疑似コードっぽいアルゴリズムを使用して、実際にコードに実装することを想定しています。基本的に、ノードへの参照を保存するためのスタックと、整数値 1 または 2 を保存するための 2 つの並列スタックを作成して、左または右のサブツリーにアクセスしたかどうかを確認します。私は彼らが私にくれたものに基づいてアルゴリズムを作成しましたが、何らかの理由で数字の一部のみを印刷し、正しい順序ではありません.

彼らが私にやりたいことは次のとおりです。

そして、これが私の実装です：

この場合が真である二分木はありますか?

二分木が 1 つのルート ノードのみで構成されている場合を除き、そうは思いません。

バイナリツリー（バイナリ検索ツリーではない）を順番にトラバースした結果を次のように示します。

E、D、B、A、G、F、H、C

ここで、インオーダートラバーサルが指定されているのと同じツリーのポストオーダートラバーサルの結果を確認する必要があります。

誰かが私にこれのためのアルゴリズムを提案できますか？

PS：順序どおりの結果からツリー自体をスケッチする方法はありますか？

Binary Search Tree任意の1つのトラバーサル（、、または）、またはそれらの任意の2つの組み合わせからのpre構築postに関するin-orderさまざまなサイトの多数の記事に非常に混乱しています。たとえば、このページでは、トラバーサルとともに、、または順序トラバーサルpreがpost与えられると、を構築できると書かれています。しかし、あちこちで、彼らは私たちに一人でからを構築することを示しています。また、ここでは、与えられたトラバーサルからを構築する方法を示します。他のいくつかのサイトで、トラバーサルのみからを構築するための解決策を見つけました。levelin-orderBSTBSTpre-orderBSTprepost-orderBSTpost-order

inorderこれで、とpre-orderトラバーサルが与えられると、を一意に形成できることがわかりましたBST。私が提供した最初のリンクに関しては、BSTfrompre-orderとを構築できないと言われてpost-orderいますが、配列を並べ替えてトラバーサルpost-orderを取得し、それと配列を使用して？を形成することはできません。それは4番目のリンクのソリューションと同じですか、それとも異なりますか？そして、与えられただけで、それを並べ替えてを取得し、それとを使用してを取得できます。繰り返しますが、それはリンク2と3のソリューションとは異なる必要がありますか？inorderpre-orderBSTpre-orderin-orderpre-orderBST

具体的には、一意に生成するのに十分なものは何BSTですか？一意性が必要ない場合は、単純にソートしてin-orderトラバーサルを取得し、そこからN個BSTの可能なものの1つを再帰的に構築できます。

ツリーでのポストオーダー トラバーサルのアプリケーションの 1 つは、ディスク スペースの計算であると読みました。事前注文トラバーサルを使用できないのはなぜですか? 私たちは同じ答えを得ることはありませんか？