フルバイナリツリーとは何ですか?
完全なバイナリ ツリーは次のように定義できます。 二分木 すべてのノードには 0 または 2 つの子があります。言い換えれば、完全なバイナリ ツリーは、リーフ ノードを除くすべてのノードが 2 つの子を持つバイナリ ツリーとして定義できます。
以下のツリーは完全なバイナリ ツリーです。
上記のツリーは、リーフ ノードを除くすべてのノードに 2 つの子があるため、完全なバイナリ ツリーです。
完全な二分木の定理:
クエリセレクター
二分木 T を空ではない木とみなして、次のようにします。
- I をツリーの内部ノード、L をツリーの葉ノードとすると、葉ノードの数は次のようになります。
L = I + 1 - T が内部ノードの数 I、ノードの合計数が N である場合、ノードの合計数は次のようになります。
N = 2I + 1 - T にノードの合計数が「N」で、内部ノードの数が「I」である場合、内部ノードの数は次のようになります。
I = (N-1)/2 - 「T」の合計ノード数が「N」で、リーフ ノードの数が「L」の場合、リーフ ノードの数は次のようになります。
L = (N+1)/2 - 「T」に「L」個のリーフ ノードが含まれる場合、ノードの総数は次のようになります。
N = 2L - 1 - 「T」に「L」個のリーフ ノードがあり、「I」が内部ノードの数である場合、内部ノードの数は次のようになります。
I = L - 1
完全な二分木とは何ですか?
バイナリ ツリーは、左から埋められる最後のレベルを除いて、すべてのレベルが完全に埋められている場合に、完全なバイナリ ツリーであると言われます。
以下のツリーは完全なバイナリ ツリーです。
完全なバイナリ ツリーは、以下に示す 2 つの違いを除き、完全なバイナリ ツリーと似ています。
- リーフ ノードの塗りつぶしは、左端から開始する必要があります。
- 最後のリーフ ノードに正しい兄弟が必要であることは必須ではありません。
例を通して上記の点を理解しましょう。
インターネットに関するデメリット
以下のツリーを考えてみましょう。
上記のツリーは完全なバイナリ ツリーですが、ノード 6 には正しい兄弟がないため、完全なバイナリ ツリーではありません。
検索エンジンと例
完全なバイナリ ツリーの作成
以下に示す 6 つの要素の配列があるとします。
上記の配列には 6 つの要素 (1、2、3、4、5、6) が含まれています。完全なバイナリ ツリーを作成するために使用する手順は次のとおりです。
ステップ1： まず、配列の最初の要素、つまり 1 を選択し、ツリーのルート ノードを作成します。最初のレベルで使用できる要素の数は 1 です。
ステップ2： 次に、配列の 2 番目と 3 番目の要素を選択します。以下に示すように、配列の 2 番目の要素と 3 番目の要素をそれぞれルート ノードの左側と右側の子として保持します。
上でわかるように、第 2 レベルで使用できる要素の数は 2 です。
ステップ 3: ここで、配列から次の 2 つの要素、つまり 4 と 5 を選択します。以下に示すように、これら 2 つの要素をノード 2 の左右に保持します。
上でわかるように、ノード 4 と 5 はそれぞれノード 2 の左側と右側の子です。
ステップ 4: ここで、配列の最後の要素、つまり 6 を選択し、それをノード 3 の左側の子として保持します。これは、完全なバイナリ ツリーでは、ノードは以下に示すように左側から埋められることがわかっているためです。
Javaの戻り値の型
2 番目のレベルには 3 つの要素が含まれていることがわかります。
完全なバイナリツリーと完全なバイナリツリーの違いを画像を通して理解しましょう。
- 以下に示すバイナリ ツリーは、完全なバイナリ ツリーでも完全なバイナリ ツリーでもありません。ノード 3 には子が 1 つしかないため、完全なバイナリ ツリーではありません。また、ノードは左側から埋められる必要があるため、完全な二分木ではありませんが、ノード 3 には右側の子があり、左側の子がありません。
- 以下に示すバイナリ ツリーは完全なバイナリ ツリーですが、完全なバイナリ ツリーではありません。すべてのノードには 0 または 2 つの子があるため、これは完全なバイナリ ツリーです。これは完全なバイナリ ツリーではありません。ノード 3 には子がありませんが、ノード 2 には子があり、ノードは完全なバイナリ ツリーの左側から埋められる必要があることがわかっています。
- 以下に示すバイナリ ツリーは完全なバイナリ ツリーですが、完全なバイナリ ツリーではありません。すべてのノードが満たされたままであるため、これは完全な二分木です。ノード 2 には子が 1 つしかないため、完全なバイナリ ツリーではありません。
- 以下に示すバイナリ ツリーは、完全なバイナリ ツリーであると同時に完全なバイナリ ツリーでもあります。すべてのノードが満たされたままであるため、これは完全な二分木です。すべてのノードに 0 または 2 つの子があるため、これは完全なバイナリ ツリーです。
