1

文字で構成されているため、ツリーの右または左に値を配置するタイミングがわからないため、このツリーを描くのに苦労しています。

これはどうやって判断するのですか？

追加するために編集: 可能な事前注文トラバーサルとして、次の選択肢が与えられます。

A.  F A E K C D B H G
B.  F A E K C D H G B
C.  E A F K H D C B G
D.  F E A K D C H B G
4

3 に答える 3

3

この順不同のトラバーサルに相当する先行順序が複数あります。文字をグループ化する括弧がないため、元のツリー構造が何であったかを文字だけから知ることはできません。

たとえば、あなたが述べた順不同のトラバーサルを生成する可能性のある2つのツリーがありますが、異なるプリオーダートラバーサルがあります。他にもたくさんあります。

ツリー 1

順序: EACKFHDBG 事前注文 : FKAECDHBG

ツリー 2

順序: EACKFHDBG 事前注文 : KAECHFDGB

アップデート

あなたのコメントによると、これは実際にはある種のテストまたは宿題の問題であることがわかります。inorder traversal といくつかの可能な preorder traversal の両方が与えられているため、問題は、両方の順序付けを満たすツリーを再構築できるかということです。はい、これは間違いなく実行可能です。それぞれを試してみて、パズルを解くだけです。

では、これにどのようにアプローチすればよいのでしょうか。では、順序付けされたトラバーサルと事前順序付けされたトラバーサルについて、私たちは何を知っているでしょうか?
インオーダートラバーサルは、ツリー上で左から右へのノードの絶対順序を与えることがわかっています。逆に、事前順序トラバーサルでは、ルートから下に向かってノードがリストされ、常に現在のノードが最初にリストされ、次に左のサブツリー、次に右のサブツリーがリストされます。したがって、1 つのアプローチは、(最初の文字がルート ノードを示しているため) 事前順序トラバーサルをウォークスルーし、各ノードをツリーに追加しようとすることです。この順序でトラバーサルを使用して、そのノードを前のものの左または右。

どの答えから始めても構わないので、最初に答え (D) を試してみましょう: FEAKDCHBG

  1. ルート ノード F を配置することから始めます。

                                  F

  2. 次のノード E は、明らかに F に接続しますが、左か右か? inorder トラバーサルを見てみましょう。E は F の前または後に来ますか? 前に来るので、左のノードでなければなりません。

                                  F
                             /
                            E

  3. 次に A があります。現在、ツリーには 3 つのオープン スポットがあります。E の左、E の右、F の右です。順不同のトラバーサルでは、A は E の後、F の前に来ます。つまり、A の右にある必要があります。 E. 

                                  F
                             /
                            E
                             \
                              A

  4. Kは予約注文の次です。ツリーのどこに移動する必要がありますか? 順序は、K が A の後、F の前に来ることを示します。プレオーダーと一致するツリー内の 3 つのオープン スポット (A の左、A の右、または F の右) のうち、適合できる唯一の場所は A の右です。 .

                                  F
                             /
                            E
                             \
                              A
                               \
                                K

  5. 次はDです。順不同のトラバーサルは、D が F の後に来なければならないことを示しており、それに対して機能するオープン スポットがツリー内に 1 つだけあります。それは F の右側です。

                                  F
                             / \
                            E   D
                             \
                              A
                               \
                                K

  6. ここで問題が発生します。次に配置するノードは、事前注文によると C です。順序によると、C は K の前と A の後に来る必要があります。つまり、K の左に配置することを意味し ます。予約注文は上から下、左から右に進むため、配置されるすべての新しいノードは、最後に配置されたノードの真下、またはツリー内のその上と右のいずれかに配置する必要があることに注意してください。最後に配置したノードは D でした。これは、予約注文を満たすために C をそれに接続する必要があることを意味します。しかし、C が D に接続されている場合、K に接続することはできません。したがって、矛盾があります。つまり、答え (D) は正解ではありません。

うまくいけば、トラバーサルを通り抜け、そこからツリーを構築する方法がわかったはずです。他の3つの答えを試して、どれが正しいかを判断するのはあなたに任せます.

于 2016-05-25T18:28:36.917 に答える