二分木とは

二分木

木構造とは

木構造とは、データ構造の1つで木のような階層構造でデータを管理するものです。

木構造の要素部分を節（ノード）といい、親のない最上位の節を根（ルート）、子のない節を葉（リーフ）、そして 節と節を繋ぐ線のことを枝（ブランチ）といいます。

ハードディスクのファイルシステム（フォルダの下にフォルダやファイルがぶら下がっている）やインターネットのドメイン名などは、いずれも木構造を用いて管理されています。

二分木とは

二分木（英: binary tree）とは、どの親ノードも2つ以下の子ノードで構成されている木構造のことをいいます。

次の図は二分木のイメージ例です。

二分木はすべての親ノードが子ノードを1つか2つしか持たない木構造のことです。

完全二分木

完全二分木（英：perfect binary tree）とは、二分木のうち葉以外のノードがすべて2つの子ノードを持ち、根から葉までの深さが揃っている木構造のことをいいます。

完全二分木の葉の数は次の式で求めることができます。（今回の例では、完全二分木の深さは2なので「2²」となり葉の数は「4」）

そして、葉以外のノードの数は次の式で求めることができます。（今回の例では、完全二分木の深さは2なので「2²-1」となり葉以外のノード数は「3」）