データ構造における二分木ADTの基本概念・実装方法・種類を徹底解説

基本概念

二分木（バイナリツリー）とは、どのノードも2つより多くの子を持つことができない木として定義されるデータ構造です。任意のノードが持てる子の数（次数）の最大値は2であり、二分木を構成する各ノードの次数は0、1、2のいずれかになります。

上図のように、二分木はルート（根）と2つの部分木「左部分木」「右部分木」によって構成されます。ルートの左側に位置するすべてのノードは左部分木と呼ばれ、右側に位置するすべてのノードは右部分木と呼ばれます。

実装方法

二分木の子ノードは最大で2つであるため、それぞれに対して直接ポインタを割り当てることができます。ツリーノードの宣言は、双方向連結リストの構造体宣言と同じ形式となり、ノードはキーとなる情報（要素）と、他のノードを指す2つのポインタ（left：左、right：右）を含む構造体として定義します。

二分木ノードの宣言例

typedef struct tree_node *tree_ptr;
struct tree_node
{
    element_type element1;
    tree_ptr left1; tree_ptr right1;
};
typedef tree_ptr TREE;

二分木の種類

厳密二分木

厳密二分木とは、すべてのノードが0個または2個の子を持つ二分木のことです。子を1つだけ持つノードは一切存在しません。

スキュー木（斜め木）

スキュー木とは、葉以外のすべてのノードが子を1つしか持たない二分木です。スキュー木には「左スキュー木」と「右スキュー木」の2種類があります。

左スキュー木

左スキュー木では、すべてのノードが左の子のみと結び付いています。つまり、左部分木だけで構成された二分木です。

右スキュー木

右スキュー木では、すべてのノードが右の子のみと結び付いています。つまり、右部分木だけで構成された二分木です。

満二分木

すべての葉が同じレベル（深さ）にあり、かつすべての非葉ノードがちょうど2つの子を持ち、全レベルで可能な限り最大数のノードを含む場合、その二分木は満二分木と定義されます。高さhの満二分木が持てる最大ノード数は 2^h+1 − 1 個です。

完全二分木

完全二分木では、すべての非葉ノードがちょうど2つの子を持ちますが、すべての葉が同じレベルにある必要はありません。最下段以外のすべてのレベルで最大数のノードを持ち、最後のレベルの要素は左から右の方向へ順番に埋めていくものとして定義されます。

ほぼ完全二分木

ほぼ完全二分木とは、「右の子を持つノードは必ず左の子も持つ」という条件を満たす木として定義されます。逆に、左の子を持っているからといって、右の子を持つことは要求されません。

一般木と二分木の違い

一般木の特徴

• 一般木では、ノードが持てる子の数に制限がありません。
• 式の評価を行うのが難しいという欠点があります。

二分木の特徴

• 二分木では、ノードが持てる子は最大2つに制限されています。
• 構造が単純なため、式の評価を簡単に行うことができます。

木構造の主な応用例

• 算術式の操作・処理
• 記号表（シンボルテーブル）の構築
• 構文解析
• 文法の記述
• 式木の生成