1. 序章

この記事では、二分木のデータ構造とそのプロパティについて学習します。 次に、6種類の二分木をイラストで学びます。

最後に、二分木のさまざまなアプリケーションについて説明します。

2. 意味

二分木は、各ノードが最大2つの子を持つ階層データ構造です。 子ノードは、左の子および右の子と呼ばれます。

まず、各ノードに3つのフィールドがあるバイナリツリーのリンクリスト表現について説明します。

  • 左の子のアドレスを格納するためのポインタ
  • データ要素
  • 適切な子のアドレスを格納するためのポインタ

二分木の例を見てみましょう。

3. プロパティ

ここで、二分木のいくつかの基本的なプロパティに焦点を当てましょう。

  1. ルートのレベルがゼロの場合、バイナリツリーはレベルで最大のノードを持つことができます。
  2. 二分木の各ノードに1つまたは2つの子がある場合、リーフノード（子のないノード）の数は、2つの子を持つノードの数より1つ多くなります。
  3. バイナリツリーの高さがで、リーフノードの高さが1の場合、ノードは最大数存在します。
  4. 二分木に葉のノードがある場合、それは少なくともそしてほとんどのレベルを持っています。
  5. ノードの二分木には、最小数のレベルまたは最小の高さがあります。
  6. ノードを持つ二分木の最小と最大の高さは、それぞれとです。
  7. ノードのバイナリツリーにnull参照があります。

4. 二分木の種類

このセクションでは、6種類の二分木について説明し、それぞれを図で説明します。

4.1. 完全な二分木

各内部ノードに0個または2個の子がある場合、バイナリツリーは完全なバイナリツリーであると言われます：

4.2. 完璧な二分木

完全な二分木は、すべてのリーフノードが同じレベルにあり、各内部ノードに2つの子がある特殊なタイプの二分木です。

4.3. 完全な二分木

すべてのレベルが完全に満たされる場合、バイナリツリーは完全なバイナリツリーと呼ばれます。唯一の例外は、ノードが可能な限り左に傾く必要がある最低レベルである可能性があります。

4.4. 退化または病理学的ツリー

縮退または病理学的ツリーは、各内部ノードが左の子または右の子のいずれかの単一の子を持つ一種の二分木です。

4.5. 歪んだ二分木

すべての内部ノードに正確に1つの子があり、左の子または右の子のいずれかがツリーを支配している場合、バイナリツリーは歪んだバイナリツリーであると言われます。 特に、左に歪んだ二分木と右に歪んだ二分木の2種類の歪んだ二分木が存在します。

4.6. 平衡二分木

平衡二分木も特殊なタイプの二分木であり、各ノードのサブツリーの左右の高さの差は最大で1つです。

5. アプリケーション

バイナリ検索ツリー、構文ツリー、ヒープ、ハッシュツリー、赤黒ツリー、など、バイナリツリーのアイデアから派生した他の多くのデータ構造があります。 ]バイナリトライ、 AVLツリー、GGMツリー、Tツリー、およびTreap。

バイナリツリーの他の実際のアプリケーションには、バイナリスペースパーティション、ヒープソート、ハフマンコーディング、仮想メモリ管理、およびインデックス作成が含まれます。

6. 結論

この記事では、二分木データ構造とその基本的なプロパティについて学習しました。

次に、6種類の二分木について例を挙げて説明しました。 最後に、二分木のさまざまなアプリケーションをリストアップしました。