1. 序章

シリアル化とは、データ構造またはオブジェクトをビットシーケンスに変換して、ファイルやメモリバッファに保存したり、ネットワーク経由で送信したりできるようにすることです。将来的には、シーケンスを逆シリアル化して、同じデータ構造またはオブジェクト。

このチュートリアルでは、バイナリツリーをシリアル化および逆シリアル化するためのアルゴリズムを紹介します。

2. 二分木の定義

二分木は、各ノードが最大2つの子を持つ階層データ構造です。 二分木の各ノードには3つの要素があります。ノードデータを保持するデータ要素と、その左右の子を指す2つの子ポインターです。 子ノードが存在しない場合、それを表すために使用します。

3つの主要なバイナリツリートラバーサルメソッドがあります：プレオーダー、インオーダー、およびポストオーダー。 pre-orderメソッドとin-orderメソッドなどの2つのメソッドを組み合わせて、バイナリツリーをシリアル化および逆シリアル化できます。

このチュートリアルでは、単一のツリートラバーサルメソッドを使用してバイナリツリーをシリアル化および逆シリアル化する方法を示します。 たとえば、プレオーダートラバーサルを使用してバイナリをシリアル化し、同じ方法で逆シリアル化することができます。

3. プレオーダートラバーサルを使用してバイナリツリーをシリアル化する

プレオーダートラバーサルアルゴリズムを使用して、バイナリツリーをシリアル化できます。プレオーダーバイナリツリートラバーサルでは、最初にルートノードをトラバースします。 次に、その左と右のサブツリーをそれぞれトラバースします。 たとえば、上記の例のツリーを次の順序で事前に並べ替えることができます。

ツリーをシリアル化するときは、ノードも考慮します。 この場合、を使用してノードを表すことができます。 したがって、プレオーダーシーケンスは次のようになります。

再帰的な事前注文トラバーサルアルゴリズムを使用して、シリアル化シーケンスを構築できます。

このアルゴリズムでは、最初にノードデータをシリアル化し、次にその左と右の子を再帰的にシリアル化します。 ノードに出会った場合は、特殊文字でシリアル化します。

二分木にノードが含まれている場合、このアルゴリズムの全体的な実行時間は、各ノードに1回だけアクセスするためです。 スペース要件は、シリアル化シーケンスを格納することでもあります。 シリアル化シーケンスでノードを格納するために追加のスペースが必要ですが、各ノードには最大で2つの子があるため、追加のスペースは最大でです。

4. プレオーダートラバーサルを使用してバイナリツリーを逆シリアル化します

同じ事前注文アルゴリズムを使用して、シーケンスをバイナリツリーに逆シリアル化できます。

アルゴリズムの説明を簡単にするために、再帰関数の入力としてシリアル化シーケンスのイテレータオブジェクトを使用します。 異なるプログラミング言語では、同様のイテレータがサポートされています。 たとえば、JavaでIteratorインターフェイスを使用できます。

逆シリアル化プロセスは、シリアル化プロセスに似ています。 最初にルートノードデータを逆シリアル化し、次にその左と右の子を再帰的に逆シリアル化します。 特殊文字が表示された場合は、それをノードとして逆シリアル化します。

各ノードを1回だけ構築するため、全体的な実行時間とスペース要件は両方ともです。

5. ポストオーダートラバーサルを使用してバイナリツリーをシリアル化する

プレオーダートラバーサルと同様に、ポストオーダートラバーサルアルゴリズムを使用してバイナリツリーをシリアル化できます。 ポストオーダーの二分木トラバーサルでは、最初にその左と右のサブツリーをそれぞれトラバースします。 そして、ついにルートノードにアクセスします。 再帰的なポストオーダートラバーサルアルゴリズムを使用して、シリアル化シーケンスを構築できます。

このアルゴリズムでは、最初に左右の子を再帰的にシリアル化します。 次に、最後にルートノードデータをシリアル化します。 全体的な実行時間とスペース要件もです。

6. ポストオーダートラバーサルシーケンスを逆シリアル化します

プレオーダーシリアル化では、ルートノードをシーケンスの先頭に配置します。 ただし、シーケンスの最後にルートノードをポストオーダーシリアル化で配置します。 たとえば、ポストオーダーでサンプルツリーを次の順序でトラバースできます。 したがって、ポストオーダートラバーサルは、プレオーダートラバーサルの一種の逆操作です。

ポストオーダートラバーサルシーケンスをシリアル化するには、最初にシーケンスを逆にしてから、変更されたプレオーダー逆シリアル化プロセスを使用してバイナリツリーを構築します。

順序付け後の走査では、次の順序でツリーを走査します。

  • 左のサブツリー
  • 右のサブツリー
  • ルートノード

デシリアライズプロセスは逆順で機能するため、最初にルートノードをデシリアライズします。 次に、適切なサブツリーを逆シリアル化します。 最後に、左側のサブツリーを逆シリアル化します。 

各ノードを1回だけ構築するため、全体的な実行時間とスペース要件は両方ともです。

7. インオーダートラバーサル二分木シリアル化と逆シリアル化

順序付きツリートラバーサルメソッドを使用して、バイナリツリーをシリアル化および逆シリアル化することはできません。順序付きバイナリツリートラバーサルでは、最初に左側のサブツリーをトラバースします。 次に、ルートノードにアクセスし、右側のサブツリーをトラバースします。 このトラバーサルにより、シリアル化されたシーケンスでルートノードを見つけることが困難になります。

たとえば、次のバイナリツリーを順番にトラバースすると、シーケンスが生成されます。

ただし、次の二分木で同じ順序のシーケンスを生成できます。

したがって、関連するツリーは一意ではないため、順序どおりのシーケンスを逆シリアル化してバイナリツリーに戻すことはできません。

8. 結論

このチュートリアルでは、バイナリツリーをシリアル化および逆シリアル化するための2つのアルゴリズム、事前注文トラバーサルと事後注文トラバーサルを示しました。 また、インオーダートラバーサルアルゴリズムは、バイナリツリーのシリアル化と逆シリアル化には適していないことも示しました。

最後に、すべてのシリアル化および逆シリアル化アルゴリズムが線形時間および空間の複雑さを持っていることを確認しました。