問題タブ [preorder]

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

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

最近、私の人生でBSTを多用している間、インオーダートラバーサル以外のものを使用することを考えたことさえありませんでした（プログラムをプレオーダー/ポストオーダートラバーサルを使用するように適応させることがいかに簡単かを認識し、知っています）。

これに気付いたとき、私は古いデータ構造の教科書をいくつか引き出し、事前注文と事後注文のトラバーサルの有用性の背後にある理由を探しましたが、彼らはあまり言いませんでした。

プレオーダー/ポストオーダーを実際に使用する場合の例をいくつか挙げてください。順序よりも意味があるのはいつですか？

2つのツリーノードが関連しているかどうかを確認します（つまり、祖先-子孫）

• O（N）空間（N =ノード数）を使用して、O（1）時間で解きます
• 前処理が許可されています

それでおしまい。以下の私の解決策（アプローチ）に行きます。最初に自分のことを考えたいのなら、やめてください。

前処理のために、私は事前注文を行い（最初にルートを再帰的に通過し、次に子を通過する）、各ノードにラベルを付けることにしました。

ラベルについて詳しく説明します。各ラベルは、「1,2,1,4,5」のようなコンマ区切りの自然数で構成されます。このシーケンスの長さは、（ノードの深さ+ 1）に等しくなります。たとえば、ルートのラベルが「1」の場合、ルートの子には「1,1」、「1,2」、「1,3」などのラベルが付けられます。次のレベルのノードには「1,1,1」のようなラベルが付けられます。 "、" 1,1,2 "、...、" 1,2,1 "、" 1,2,2 "、..。

ノードの「注文番号」は、その親の子リストの「このノードの1から始まるインデックス」であると想定します。

一般的なルール：ノードのラベルは、親ラベルの後にコンマとノードの「注文番号」が続くもので構成されます。

したがって、O（1）で2つのノードが関連しているかどうか（つまり、祖先-子孫）に答えるために、一方のラベルが他方のラベルの「プレフィックス」であるかどうかを確認します。そのようなラベルがO（N）スペースを占めると見なすことができるかどうかはわかりませんが。

修正または代替アプローチを使用する批評家が予想されます。

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

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

問題は、予約注文リストと各ノードが持つ子の数のシーケンスからバイナリ ツリーを構築することです。例: "BAC" と "200" は 1 つの入力で、"ABC" の順不同のリストになる可能性があります。

私の現在の方法は、2番目のcharsequence（数字のあるもの）で「2」をチェックすることです.2つの子があり、「0」は子を持たず、「L」は左の子を持ち、「R」です。右の子がいます。これを行うには、次の方法を使用します。

これは基本的に childCodes シーケンスを処理して、ツリーの各ブランチがどこで途切れるかを判断します。問題は、より大きなツリーの場合、最初のいくつかのアイテムのみを処理してから崩壊することです。(より大きなツリーの例: 「ABCDEFGHIJKLMNOPQRSTU」と子コード「220022002200LRR20RLL0」)

javascript を使用して html ツリー内の要素を事前にトラバーサルする方法

Img src = http://www.sitepoint.com/hierarchical-data-database-2/ (素晴らしい記事) 、ボックスが html 要素であると仮定

例：

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つを再帰的に構築できます。

インオーダートラバーサルとプレオーダートラバーサルを文字列として指定すると、バイナリツリーを再構築できることは知っていますが、インオーダートラバーサルのみを指定すると、ポストオーダートラバーサルやプレオーダートラバーサルを見つけることができますか？

ベクター ベースのバイナリ ツリーがあり、さまざまな走査方法を使用して、ツリー内の各値に関数を適用する必要があります。preorder トラバーサルは、再帰関数を使用して実装するのが非常に簡単でしたが、inorder および postorder トラバーサルで同じことを行うのに問題がありました。誰かがそれを助けることができれば、それは素晴らしいことです!

含める必要のある追加情報: ノードのベクトルを使用しています。各ノードには、そのノードが満たされているかどうかを示すブール変数と、テンプレート化されたデータ変数が含まれています。各ノードはインデックス「i」に格納され、その左の子はインデックス「2i+1」に、右の子は「2i+2」に格納されます。

リストに事前注文トラバーサルを適用するために、最初にインデックス 0 に格納されたデータを処理し、次にこの再帰関数を呼び出しました。

私の「n」パラメータとしてインデックス1と2で始まる2回。

事前順序で値を出力する再帰関数を作成しようとしています。ただし、何らかの理由で、inOrder関数と同じように出力され続けます。postOrder関数は正常に機能しますが、再帰関数を少し異なる方法で実行する必要がありました。以下の私のコードを見て、何が問題なのか教えてもらえますか？これが一日中私に問題を与えてきたので、私は本当に感謝しています。前もって感謝します