0

問題の説明:

R. ボリスト教授は樹木を研究しています。彼は、お気に入りのすべてのツリーの事前順、順序順、および後順トラバーサルの記録を保持しています。しかし、彼のオフィスでの火災により、彼が順番通りのトラバーサルを保管していたファイル キャビネットが破壊されました。彼はお気に入りの木すべての前順と後順のトラバーサルをまだ持っていますが、これは欠落しているインオーダーのトラバーサルを再構築するのに十分な情報ですか?

次のタスクのプログラムを設計して実装する必要があります。入力は 2 つの数値リストで構成されます。最初のリストは、あるツリー T の前順トラバーサルです。2 番目のリストは、同じツリー T の後順トラバーサルです。出力は、T のインオーダー トラバーサルでなければなりません。入力が一意のツリーを決定しない場合、任意の一貫したインオーダー トラバーサル返品できます。

実装の設計に役立つ場合は、次のことを想定できます。

  • 1,000 を超えるノードを持つツリーはありません。
  • 複数のノードに同じラベルを使用するツリーはありません。
  • ノードのラベルは 0 から 10,000 までの数字です。

サンプルデータ

Input:
2 6 7 1 11 8 5 10 3 4 9
7 8 5 11 10 1 6 4 9 3 2
Output:
7 6 8 11 5 1 10 2 4 3 9

ヒント

ツリーの前順および後順トラバーサルが与えられた場合、どの要素がルートであったかを推測できますか? 左のサブツリーから派生した要素はどれですか? 右のサブツリーから? 再帰。

最初に、ツリー内のすべてのノードが 2 つまたは 0 つの子を持つことが保証されている場合に問題を解決します。一部のノードに子が 1 つしかない場合は、少し注意が必要です。

ノート

記事では、ソリューションの効率/実行時間を分析する必要はありません (これは、将来のプロジェクトで必要になります)。しかし、その正しさを分析してください。つまり、アルゴリズムが正しい理由を明確に説明してください。

4

1 に答える 1

2

問題の説明が明示的にそう述べていなくても、バイナリ ツリーを扱っていることはヒントから明らかです。

ヒントは良いです: ツリーのルートを見つけてから、左のサブツリーのルートと右のサブツリーのルートを見つけます。

ルートを削除した後、リストを切り取ることができるノードのリスト内の位置を探します。切り取り前のノードは左側のサブツリーからのものであり、切り取り後のノードは右側のサブツリーからのものです。

あなたがしたように小さな例を作ることは良い考えです。

具体的に「事前および事後トラバーサルからインオーダー トラバーサルを構築する方法を理解する」に答えるには、まず事前トラバーサルとポスト トラバーサルからツリーを再構築し、次にツリーからインオーダー トラバーサルを構築します。

于 2012-08-15T22:04:52.503 に答える