プログラム

二分木とは

二分木

木構造とは

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

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

木構造

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

二分木とは

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

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

2分木

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

完全二分木

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

完全二分岐

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

葉の数 = 2深さ

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

節の数 = 2深さ - 1


チャンネル登録はこちら

フォローはこちら