1. 概要

このチュートリアルでは、2分木と二分探索木の2つの一般的なツリーデータ構造について説明します。 両方のツリー構造のプロパティと例を含む正式な定義を示します。

最後に、それらの間の主要な概念上の違いについて説明します。

2. 二分木の紹介

二分木は、人気があり広く使用されているツリーデータ構造です。 名前が示すように、バイナリツリーの各ノードは、最大で2つの子ノード（左と右の子）を持つことができます。 ルート、中間親、リーフノードの3種類のノードが含まれています。

ルートノードは、バイナリツリーの最上位ノードです。 リーフノードは、子ノードのないノードとして定義できます。 最後に、ルートノードとリーフノードを除いて、他のすべてのノードは中間の親ノードです。 例を見てみましょう：

まず、ツリーが二分木であるかどうかを確認しましょう。 主要で最も重要なプロパティは、各ノードが最大2つの子ノードを持つことができることです。 したがって、サンプルツリーがこのプロパティに従っていることがわかります。 したがって、それは二分木です。

ここで、ノードは二分木のルートノードです。 また、ノードとはリーフノードです。 最後に、ノードとは中間の親ノードです。

二分木の各ノードには、左の子へのポインター、データ、右の子へのポインターの3つのフィールドが含まれています。 二分木の論理表現を見てみましょう：

二分木にはさまざまな種類があります。 それらのいくつかは、完全、完全、完全、歪んだ、バランスの取れた二分木です。 さらに、二分木データ構造は、検索、挿入、削除、およびトラバーサルの4つの主要な操作をサポートします。

3. プロパティ

二分木データ構造のいくつかの重要なプロパティについて説明しましょう。

高さの二分木には最大ノードが存在する可能性があります。 二分木を見てみましょう。 葉のノードはの高さにあります。 したがって、の高さはです。

さらに、根の高さはです。 したがって、高さのあるノードの最大数はです。 同様に、含めることができるノードの最大数はです。

ここで、バイナリツリー内のノードの総数が与えられると、バイナリツリーの最小の高さまたはレベルはになります。 には、ノードがあります。 したがって、最小の高さまたはレベルはになります。

バイナリツリーのレベルで最大ノードを持つことができます。簡単に検証できます。 二分木のルートノードのレベルは常にです。 したがって、ノードの最大数が存在する可能性があります。これは、すべてのバイナリツリーに有効です。

さらに、バイナリツリーの正確なノード数とレベルを計算する方法に関するアルゴリズムの詳細な説明は、チュートリアル「レベルNのバイナリツリー内のノード数」にあります。

二分木に葉があると仮定しましょう。 二分木構造によると、それは少なくともレベルを持っている必要があります。 の場合、葉があります。 したがって、このプロパティによれば、少なくとも真のレベルが必要です。

現在、バイナリツリーの定義に基づいて、各ノードには最大2つの子ノードを含めることができます。 したがって、バイナリツリーのすべてのノードに子が含まれるか子が含まれるシナリオを考えてみます。 このような場合、 の子を持つノードの数は、常に子のないノードの数より1つ少なくなります。

には、子のないノード（キーとのノード）と子のあるノード（キーとのノード）があります。 したがって、この例ではプロパティを検証します。

4. 二分探索木の紹介

二分探索木は、ソートされたツリーデータ構造です。 さらに、いくつかの追加のプロパティを使用して、バイナリツリーのプロパティに従います。 したがって、各ノードは最大2つの子ノードを持つことができます。 ただし、ここでは、左側のサブツリーのキーがその親ノードのキー値よりも小さくなっています。同様に、右側のサブツリーのキーがその親ノードのキー値よりも大きくなっています。[X187X ]

例を見てみましょう：

まず、それが二分探索木であるかどうかを判断しましょう。 ルートノードの左側の子には、ルートノードのキーよりも値が小さいキーが含まれています。 同様に、ルートノードの右側の子には、ルートノードよりも大きな値を持つキーが含まれています。 最後に、ツリーの残りの部分は、バイナリツリーとバイナリ検索ツリーの両方のプロパティに従います。 したがって、それは二分探索木であると言えます。

別の例を見てみましょう：

ここでは、ルートと中間の親ノードにそれぞれ子ノードが含まれているため、ツリーは二分木です。 ただし、これは二分探索木ではありません。 左側のサブツリーのリーフノードを見ると、それが二分探索木のプロパティに違反していることがわかります。 したがって、これは二分木ですが、二分探索木ではありません。

二分探索木のデータ構造と可能なツリー操作の詳細については、チュートリアル二分探索木のクイックガイドを参照してください。

5. 違い

二分探索木と二分木の間には類似点があります。 どちらもツリーデータ構造であり、両方の構造の各ノードには最大2つの子ノードを含めることができます。 類似点に関係なく、それらにはいくつかのコア構造および機能の違いがあります。 それらの主な違いについて説明しましょう：

6. 結論

このチュートリアルでは、2分木と2分探索木の2つのツリーデータ構造について説明しました。 両方のデータ構造を例を挙げて説明し、それらの主な違いを示しました。