プログラミング
 Computer >> コンピューター >  >> プログラミング >> プログラミング

二分木（バイナリツリー）のデータ構造と重要な性質を解説

二分木（バイナリツリー）とは、各ノードが持てる子ノードの数を最大2つに制限した木構造のデータ構造です。本記事では、この二分木が持つ重要な性質について、具体例とともにわかりやすく解説します。

まず、次のような二分木を例に考えてみましょう。

二分木（バイナリツリー）のデータ構造と重要な性質を解説

二分木の主な性質

  • 各レベルの最大ノード数：レベル「l」における最大ノード数は 2l−1 です。ここでいうレベルとは、根（ルート）からそのノードまでの経路上にあるノードの総数を指し、ルート自身も含みます。なお、ルートのレベルは1として扱います。
  • 木全体の最大ノード数：高さ h の二分木に含まれる最大ノード数は 2h−1 です。ここでいう高さとは、ルートから葉までの経路上にあるノード数の最大値です。ノードが1つだけの木の高さは1として計算します。
  • 最小高さ（最小レベル数）：n 個のノードを持つ二分木において、取りうる最小の高さ（最小レベル数）は log2(n+1) です。ただし、葉ノードの高さを0と定義する場合には、log2(n+1)−1 という式になります。
  • 葉の数とレベル数の関係：「L」個の葉（リーフノード）を持つ二分木は、少なくとも log2(L+1) 以上のレベル数を持ちます。
  • 葉ノードと内部ノードの関係：すべてのノードが子を0個または2個持つような二分木（フルバイナリツリー）では、葉ノードの数は常に「2つの子を持つノード」の数より1つ多くなります。

補足：グラフ理論との関係

二分木は木構造の一種であるため、グラフ理論における「木」が持つすべての一般的な性質を備えています。したがって、上記の性質に加えて、木構造全般に共通する特徴（連結性・閉路を持たないことなど）もそのまま成り立ちます。

  1. 二分探索木の走査アルゴリズム完全解説：行順・先行順・後行順・レベル順をC++で実装

    二分探索木の走査とはこの記事では、二分探索木（BST：Binary Search Tree）に格納されたキーを巡回するための4種類の走査アルゴリズムを解説します。具体的には、以下の4つです。行順（Inorder）走査：左部分木 → 根 → 右部分木の順に訪問先行順（Preorder）走査：根 → 左部分木 → 右部分木の順に訪問後行順（Postorder）走査：左部分木 → 右部分木 → 根の順に訪問レベル順（Level-order）走査：木の上から階層ごとに左から右へ訪問例として使用する木説明のために、次のような二分探索木を想定します。この木に対する各走査の結果は以下のようになります。行順走

  2. データ構造における二分木の表現方法｜配列と連結リストの違いを解説

    コンピュータメモリ上での二分木の表現方法 ここでは、二分木をコンピュータのメモリ上でどのように表現するかについて解説します。表現方法には主に2種類あり、配列を使う方法と連結リスト（リンクリスト）を使う方法があります。 配列による表現 まず、次のような二分木を例に考えてみましょう。 配列による表現では、木の要素をレベル順（幅優先順）に走査しながら格納していきます。つまり、ノードを上のレベルから順番に保存する方式です。存在しない要素がある場合は、その位置を空白のまま残します。上記の木を配列で表現すると、次のようになります。 123456789101112131415 10516-81520