私は、4 日前にかかった中間試験の問題に出くわしました。理解できませんでした。
木の順不同のトラバーサルを行ったときに答えが得られたと仮定すると、プリオーダーのトラバーサルの場合、どうして解を見つけることができるのでしょうか。次の例がありますE A C K F H D B G。
preorder traversal は何を返しますか?
a. FAEKCDBHG
b. FAEKCDHGB
c. EAFKHDCBG
d. FEAKDCHBG
誰が私を学習面で助けてくれますか?
編集：答えはFAEKCDHGBです。しかし、これはどのように計算されますか？
したがって、順序は次のとおりです。
E A C K F H D B G
また、予約注文は次の場所から行う必要があります。
a. FAEKCDBHG
b. FAEKCDHGB
c. EAFKHDCBG
d. FEAKDCHBG
これらのオプションのそれぞれについてツリーを描画することによって続行する必要がありますが、同時にそれをインオーダートラバーサルに適合させ、どれが可能かを確認してください。
これを行うには、事前順トラバーサルの各文字について、その文字の周囲でインオーダー トラバーサルを 2 つに分割します。
を。
Fがルートに違いないことがわかっています。順不同のトラバーサルを次のように分割しますF。
| F |
E A C K H D B G
予約注文トラバーサルの次の文字は ですA。A周りを含むサブツリーを分割しAます:
| F |
| A | H D B G
E C K
次はE。分割するものはありません。次はK：
| F |
| A | H D B G
E C
K
次はC。分割するものはありません。
次はD：
| F |
| A | | D |
E C H B G
K
次はB：
| F |
| A | | D |
E C H B
K G
これで分割はできなくなります。このツリーで preorder トラバーサルを実行すると、次のようになります。
F A E C K D H B G
これは私たちが始めたものではないので、矛盾に達しました。したがって、それはできません。他の人にも同じことをしてください。
答えは未定義です。
これらの 2 つのツリーを見てください。
E
\
A
\
C
\
K
\
F
\
H
\
D
\
B
\
G
と：
A
/ \
E C
\
K
\
F
\
H
\
D
\
B
\
G
これらの 2 つのツリーは同じ順序でトラバーサルしますが、最初のツリーは の順序でトラバーサルEACKFHDBGし、2 番目は の順序でトラバーサルします。AECKFHDBG
したがって、順序通りのトラバーサルが与えられた場合、そのトラバーサルに適合する可能性のある二分木は 1 つ以上あります。これは、より多くのバイナリ ツリーが存在するn!一方で、可能な順列 (したがって、順序通りのトラバーサル)があるという事実によるものです。これにより、複数のツリーに適合する (少なくとも 1 つの) 順序どおりのトラバーサルが存在することが保証されます (ピジョンホールの原則)。
可能なbツリーの1つは次のとおりです。
したがって、事前注文トラバーサルは以下を返します。
HKAECFBDG
もう1つは次のとおりです。
事前注文トラバーサルが与えるもの:
HAEKCFBDG
さらに別のものは次のとおりです。
事前注文トラバーサルが与えるもの:
KAECHFBDG
、これはあなたのオプションではありません。与えられた順不同のトラバーサルに対して他のバイナリツリーを思い付くことができないので、誰からのコメントも大歓迎です..
私も試験でこの質問をしましたが、b が質問の Google 検索からの答えであることを知りました。ロルツ。