問題タブ [postorder]

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

次のような事前注文トラバーサル関数があります。

それは実際に機能しますが、ポストオーダーにするのはこれと同じくらい簡単だと思いました

しかし残念なことに、それはうまく機能しません。これを修正する方法を知りたいのですが、単純な間違いをしている可能性があります。あるいは、完全に間違っているかもしれません。

Binary Tree に次の値 ({18, 26, 52, 78, 45, 16, 67, 58, 73, 11}) を入力すると、次のツリーが表示されます。

PreOrder トラバーサルと InOrder トラバーサルの両方が期待どおりに機能します。しかし、PostOrder (PO) に関しては、私が思っていたものとは違うものを受け取っています。

私が理解しているように、PO は最初に左のサブツリーを検索し、次に右のサブツリーを検索し、最終的にノード (ルート ノードで終了) を検索します。

このツリーを介して PO をトラバースすると、{11, 16, 45, 58, 73, 67, 78, 52, 26, 18} という結果になります。この結果の背後にあるロジックを書き出すと、次のようになります。ルートから開始し、完全に左に進むと、最初のノードである 11 になります。その後、1 レベル上に移動し、その親 (16) を取得します。ルートに到達するまでこれを続けます (これは leftChild ではないため含まれません)。この最初の左側のサブツリーを通過したら、右側のレベルを下って、そこで leftChilds をチェックします。何もない場合は、45 を見つける別のレベルに移動します。

この時点で、{11, 16, 45} のリストがあります。これを続けて、結果の次の値である 58 になります。これが私の混乱の原因です。次に取得する値は、予想される 67 とは対照的に、73 です。別の leftChild (その親) が見つかると、なぜ 73 にジャンプするのでしょうか?

次のコードは、PostOrder のツリーをトラバースします。

これは、値が 73 のノードが parentNode の前に処理されるためだと思いますが (左右が上位の優先度)、45-52-78 の三角形ではなぜそうではないのでしょうか?

T が複数のノードを持つ順序付けられたツリーである場合。T の事前順序トラバーサルが、T の後順序トラバーサルと同じ順序でノードを訪問することは可能ですか? 「はい」の場合、例を教えてください。また、「いいえ」の場合、なぜそれが発生しないのか説明していただけますか?

プレオーダー、ポストオーダー、インオーダーの描画ルールは次のとおりです。

1. トラバーサルの事前注文: ルート、左、右
2. ポストオーダー トラバーサル: 左、右、ルート
3. 順序通りのトラバーサル: 左ルート、右

たとえば、次のような式があるとします。

ABCDEFGHIJKL、

この式を個別に (事前注文、事後注文、注文順で) 描画するにはどうすればよいですか。それぞれ (事前注文、事後注文、注文順) で異なる形式のツリーが存在する可能性があります。(つまり、事前注文の 2 つの形式)。(事前注文と順序どおり) または (事後注文と順序どおり) の両方がある場合は、一意のツリーを持つことができます。予約注文では、最初のノードがルートです (つまり、「A」がルートです)。ポストオーダーでは、最後のノードがルートです (つまり、「L」がルートです)。

これらの木を描くための全体的な公式または「ルール」はありますか? 私はそれらを描くことができません

編集:次のトラバーサルの各プレオーダー、ポストオーダー、インオーダーからツリーを構築する方法を意味します:

ABCDEFGHIJKL、

データ構造とアルゴリズムのクラスの 2 つの演習は、次のように聞こえます。

preorder トラバーサルが 1, 2, 5, 3, 6, 10, 7, 11, 12, 4, 8, 9 で、inode トラバーサルが 5, 2, 1, 10, 6, 3, 11, 7、12、8、4、9。

後順トラバーサルが 5, 2, 10, 6, 11, 12, 7, 3, 8, 9, 4, 1 で、inode トラバーサルが 5, 2, 1, 10, 6, 3, 11, であるツリーを構築します。 7、12、8、4、9。

プログラミング言語で実装することなく、ツリーの構造を描画するだけで済みます。この作業を困難にしているのは、木が二分木ではないことです。ツリーを構築するためにどのようなテクニックを使用できますか?

インターネットと「ユーチューブ」を検索しましたが、これに関する適切なチュートリアルが見つかりませんでした。「後置」で特定の式の対応する「バイナリツリー」を描画するにはどうすればよいですか?

そして、この表現は中置詞と接頭辞でどのように見えるでしょうか?

これを段階的にどのように行うべきかわかりません:(

18 5 1 + / 4 * 3 5 18 6 / - + -

ノート：

前順、後順、およびインオーダーを描画するためのルールは次のとおりです。 1. 前順トラバーサル: ルート、左、右 2. 後順トラバーサル: 左、右、ルート、 右

試験に必要です

Nノードの二分探索木でのポストオーダー トラバーサルの時間計算量を考えてみましょう。一般的なケースでは、すべてのノードにアクセスする必要があることはわかっていますがO(N)、BST がリストの場合、最悪の場合の複雑さはどのくらいですか? O(N^2)ノードをトラバースNして最後に到達し、Nノードを最初に戻すため、が必要だと思います。ということN*N = N^2で、そうだと思いますO(N^2)。そうですか？

以下のメソッドは、バイナリ ツリーの Post Order トラバーサル メソッドであることを意図しています。次のような二分木があります。

4 は 18 のルートであり、ポスト オーダーはルートを最後に出力することを意図しているため、これらの値では 8、4、18、17 の出力が期待されました。ただし、4、8、18、17 という出力が得られました。

in order と post order トラバーサルの両方でノードを order で処理する二分探索木を描くように依頼されました"ATTA"。私はさまざまな方法を試しましたが、最終的にはトラバーサル方法の 1 つにしか機能しません。