問題タブ [inorder]

私の入力結果24, 4, 2, 3, 9, 10, 32、そして私は次の結果を得ています2, 3, 4, 24。

スタックを使用しています。このプログラムを手動でチェックしたelse if場合、正しいサブツリーがある場合でも、ノードはスタックの4で通過していません。

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

たとえば、二分探索木が与えられた場合:

a と b の間 (両端を含む) の値を持つノードの順序付きリストを取得したいと思います。

再帰ヘルパー関数を実装しました:

それは私に与えます：

ただし、次のものが必要です。

とにかくリストを平坦化する方法はありますか? 私がやっていることはリストを別のリストに追加していることに気づきましたが、コードを壊さずにこれを修正する方法がわかりません。

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

int の二分探索木を使用して、指定された整数x値より小さいすべての整数のリンク リストを作成します。

私が試したことは？

1)残忍な解決策(非効率)

BSTの 順不同の訪問、Bst のすべての整数のリストにノードを挿入し、x から始まるリストのすべてのノードを解放します。

2)より効率的だが間違っている

検索を行い、x を見つけたら、x を見つけたノードの左側の息子を順番に訪問するリストを作成します。

たとえば、次の BST を考慮すると、明らかに間違っています。

このソリューションでは、x=15 の場合、{12,13,14} と考えます。x=root に対してのみ機能します。

質問は、どうすればよいですか？

面接に行く前にいくつかの準備をしていて、モリス・トラバーサルについて知りました.

これは私がJavaで書いたモリス・トラバーサルのコードです(その動作):

In-Order メソッドのコードは次のとおりです。

そして、私がメインで行ったことは次のとおりです。バイナリツリーに70,000,000ノードを挿入し、次の小さなチェックを行いました:

そして、結果は私を驚かせました！

それらは結果です：

モリス トラバーサル TOOK: 637 ミリ秒

再帰インオーダー TOOK: 367 ミリ秒

注意 - このテストを行ったとき、morrisTraversal() および recInOrderHelper() メソッドからのすべての System.out.println(...) にコメントを付けました。

Morris Traversal は反復的 (スタック フレームなどを開かない) であり、In-Order は再帰的であるため (再帰呼び出しごとに約 70,000,000 スタック フレームを開く)、高速になると思っていたので、これらの結果は私を驚かせました。

私はそれらの両方がO(n)であることを知っているので、明らかに私はいくつかのことについて間違っていますが、どれですか? 私は何が欠けていますか？Morris Traversal が再帰的な In-Order よりも遅いのはなぜですか?

編集-次のテストも行いました。ツリーに70,000,000ノードを挿入する代わりに、100,000ノードを挿入し、次のコードを実行しました:

結果は次のとおりです。

再帰インオーダー TOOK: 214434 ミリ秒

モリス トラバーサル TOOK: 502786 ミリ秒

ご覧のとおり、Morris Traversal は、再帰的な In-Order に比べて依然として非常に遅いです。そこで、別のテストを行い、1,000 個のノードのみを挿入し、各コードを 10,000 回だけ実行しました。結果は次のとおりです。

再帰インオーダー TOOK: 44 ミリ秒

モリス トラバーサル TOOK: 97 ミリ秒

まだわからないの？Morris Traversal が遅いのはなぜですか?

最初に断っておきますが、これは宿題ではありません。面接の準備をしていて、この問題に遭遇しました。インオーダーおよびレベルオーダートラバーサルの定義を渡すことができると思います。:-)。

例えば：

上記のツリーの順序順およびレベル順のトラバーサルは次のとおりです。

5、10、20、50、51、55、60、65、70、80

50、10、60、5、20、55、70、51、65、80

私の考え:

(1) レベル順序配列をトラバースして、順序配列に現れる最初の要素を見つけます。この要素を現在のルートと呼びます。

(2) 順序付けられた配列で現在のルートのインデックスを見つけます。順序配列はインデックスで区切られています。順序配列の左側は現在のルートの左側のサブツリーであり、順序配列の右側は現在のルートの右側のサブツリーです。

(3) 順序配列を左側として更新し、手順 1 に進みます。

(4) 順序配列を右辺として更新し、手順 2 に進みます。

上のツリーを例にとります。

ソリューションの検証を手伝ってくれる人はいますか? そして、別のものを与えるなら本当に感謝します。

順序通りのトラバーサル (Java) を使用してバイナリ ツリーを出力しようとしていますが、あいまいさはありません。

ポストオーダー表記入力からツリーを作成しました。

たとえば、input = 2 3 4 * - 5 + 次に、ツリーを作成し、順序通りのトラバーサルを使用して出力したいと考えています。

したがって、出力は = 2 - (3*4) + 5 である必要があります。

私の質問は、基本的な BinaryNode および BinaryTree クラスに干渉することなく、自分のドライバー クラスを変更するだけで、思い通りに出力を印刷できるかということです。もしそうなら、どうすればこれを行うことができますか？

printInOrder メソッド (BinaryNode クラス内) を変更することによってのみこれを行うことができる場合、これまでのところ次のようになります。

スタック オーバーフローに参加するのはこれが初めてです。正しく投稿していない場合は、ご容赦ください :)

次のツリー構造のためにツリーをフラット化するにはどうすればよいですか（順番にトラバーサル）：https ：//gist.github.com/damadamdam/7b6364220b11871f2930

私の期待する答えも要点に添付されています。

私は、順序順および後順トラバーサルを指定してツリーを作成するという問題に慣れようとしていました。次のコードを書きましたが、何か問題が発生していて、それを見つけることができませんでした。誰かがこれについて私を助けることができますか?

サンプル i/p:

in[] = {4,10,3,1,7,11,8,2}; int post[] = {4,1,3,10,11,8,2,7};