1. 序章

このチュートリアルでは、深さ優先探索からツリーを再構築する方法を発見します。 例としてバイナリツリーを使用してデモンストレーションを行い、どのトラバーサルの組み合わせを一緒に使用して一意のツリーを再作成できるかを確認します。

2. ツリーを再構築するために使用できるトラバーサル

ご存知のように、二分木はさまざまな種類の走査で表すことができます。 これらのトラバーサルは、ツリーを再構築するために使用できます。 ただし、通常、ツリーを再構築するには1つのタイプのトラバーサルでは不十分であり、2つのトラバーサルを組み合わせて使用する必要があります。

以下は、ツリーを再構築するために組み合わせて使用できる深さ優先走査のタイプです。

  • インオーダーおよびプレオーダー
  • インオーダーおよびポストオーダー
  • プレオーダーとポストオーダー–ツリーが完全な二分木である場合にのみ使用できます。

ご覧のとおり、二分木が完全な二分木でない限り、一意のツリーを取得するには、順序どおりの走査が常に不可欠です。このような場合、実際にそれから再構築できます。プレオーダーおよびポストオーダートラバーサル。 これについては、このチュートリアルの後半で詳しく説明します。

3. 実用例

例として次のツリーを使用します–さまざまなトラバーサルメソッドを使用してツリーを再構築しようとします。

このツリーでさまざまなトラバーサルメソッドを使用すると、次のトラバーサルシーケンスが得られます。

4. プレオーダーとインオーダーからツリーを再構築する

プレオーダーシーケンスとインオーダーシーケンスからツリーを再構築するには、まずプレオーダーシーケンスの最初の要素を確認します。プレオーダーはルートからツリーをトラバースするため、左のノード、次に右のノード、最初の要素6がツリーのルートであることがわかります。

次に、順序どおりのシーケンスを見て、ルート6を見つけます。 6の左側にある順序どおりの要素は、左側のサブツリーに属します。 6の右側の要素は、その右側のサブツリーに属します。

これで、次のように部分的にツリーの構築を開始できます。

次に、事前注文シーケンスに戻り、次の要素である3を取得します。 前のステップから、3が左側のサブツリーに属していることがすでにわかっています。 順序どおりに3が見つかった場合、左側と右側のサブツリーにそれぞれ2と4があることがわかります。 すなわち 3は左側のサブツリーのルートノードであり、2と4は3の左側と右側のノードです。

これで、ツリーの左側が完全に構築された状態で、ツリーがうまく形作られています。

次のプレオーダーシーケンスは19です。これは、インオーダーシーケンスで見つかった場合、次のツリーになります。

前の手順からわかるように、 プレオーダーシーケンスをトラバースし、インオーダーシーケンス内の各ノード位置について、それを使用して左右の子を決定する再帰パターンが出現しています。 

最後に、プレオーダーの次の番号は12であり、インオーダーシーケンスを見ると、ノード7と15がそれぞれその左と右の子であることがわかり、ツリーの最終的な表現が得られます。

4.1. プレオーダーとインオーダーからツリーを再構築するためのアルゴリズム

擬似コードでロジックを記述する次のアルゴリズムを見てみましょう。 アルゴリズムでは次のことを想定していることに注意してください。

  • ノードは、左右の子ノードへの参照を持つ構成です。
  • indexOf（）は、配列内の要素のインデックスを検索するために使用されるメソッドです
  • length は、配列の長さを示します

   

5. ポストオーダーとインオーダーからツリーを再構築する

ポストオーダーおよびインオーダーシーケンスからツリーを再構築することは、プレオーダーおよびインオーダーシーケンスを使用してツリーを再構築することと非常に似ています。 ただし、この場合は、注文後のシーケンスの最後の要素を確認することから始めます。 ポストオーダーシーケンスは常にルートノードで終了するため、最後の要素6がツリーのルートである必要があることがわかります。

前の例と同様に、次のステップでは、順序どおりの順序でノード6を見つけ、その左と右の子に属するノードを見つけます。

最後の要素から注文後のシーケンスに沿って続行し、ツリー全体が構築されるまでこれらの手順を繰り返します。

5.1. ポストオーダーおよびインオーダーからツリーを再構築するためのアルゴリズム

ポストオーダーシーケンスとインオーダーシーケンスからツリーを再構築するための擬似コードは、前の擬似コードの例と非常に似ていますが、ポストオーダーシーケンスを後ろから前にトラバースし始めるという点が異なります。また、最初に適切なツリーへの入力を開始します。 これは、ポストオーダートラバーサルが後方に移動すると、ルート、左、右のノードが得られるという事実と一致しています。 これにより、次のようになります。

 

   

6. ポストオーダーとプレオーダーからツリーを再構築する

最後に、プレオーダーとポストオーダーのシーケンスからツリーを再構築する方法を見ていきます。 プレオーダーとポストオーダーからツリーを再構築できるようにするには、ツリーが完全な二分木である必要があります。 つまり、ツリー内の各ノードには0個または2個のノードが必要です。

なぜこれらの2つのシーケンスを一般に二分木に使用できないのか疑問に思っている場合は、以下の2つの二分木がいっぱいではないことを見てみましょう。

これらの2つのツリーは同一のプレオーダーとポストオーダーのシーケンスを持っているため、プレオーダーとポストオーダーのシーケンスではノードが左または右の子。

この例のツリーは実際には完全な二分木であるため、実際には、事前注文と事後注文のみから再構築できます。

まず、事前注文シーケンスの最初の要素からノードを決定します。 次に、完全な二分木を扱っていることがわかっているので、事前注文シーケンスの次の要素3は確かにルートノードの左の子であると推測できます。

ここで、注文後のシーケンスで3が見つかった場合、その位置を使用して、どの要素が3の子であるかを判別できます。

この情報を使用して、次の部分ツリーを取得します。

先行予約の3の次の要素は2です。 これが完全な二分木であることを知っているので、2は3の左の子であり、4は3の右の子であると結論付けることができます。

プレオーダーシーケンスの次は番号19で、ポストオーダーシーケンスの位置は左側のサブツリーのルートとして表示されます。

これに基づいて、ツリーを再配置して次のようにすることができます。

ここでも、反復でツリーを構築するために使用している再帰パターンを見ることができます。 まず、事前注文シーケンスを使用して各ノードを通過します。 次に、注文後のシーケンスを使用して、各ノードの子を検索します。 二分木がいっぱいであるという事実は、どのノードが事前注文シーケンスから左の子であるかを判断するのに役立ちます。

6.1. ポストオーダーとプレオーダーからツリーを再構築するためのアルゴリズム

次に、プレオーダーシーケンスとポストオーダーシーケンスからツリーを再帰的に構築するためのアルゴリズムを説明する方法を見てみましょう。

   

7. 概要

このチュートリアルでは、深さ優先探索から二分木を再構築するさまざまな方法を発見しました。 さらに、サンプルツリーに知識を実装し、ツリーを再構築するためだけにプレオーダーおよびポストオーダートラバーサルを使用することの制限を学びました。