データ構造における二分木ADT

基本概念

二分木は、ノードが3つを超える子を持つことができないツリーとして定義されます。ノードの最高次数は2です。これは、二分木の次数が0または1または2であることを示しています。

上の図では、二分木はルートと2つのサブツリーTreeLeftとTreeRightで構成されています。二分木の左側にあるすべてのノードは左側のサブツリーと呼ばれ、二分木の右側にあるすべてのノードは右側のサブツリーと呼ばれます。

実装

二分木には最大2つの子があります。それらに直接ポインタを割り当てることができます。ツリーノードの宣言は、ノードがキー情報に加えて他のノードへの2つのポインタ（左と右）を含む構造であるという点で、二重リンクリストの構造と同じです。

二分木ノード宣言

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

二分木の種類

厳密に二分木

厳密に二分木は、すべてのノードがゼロまたは2つの子を持つ二分木として定義されます。どのノードにも1つの子は含まれません。

スキューツリー

スキューツリーは、リーフを除くすべてのノードに子ノードが1つしかない二分木として定義されます。スキューツリーには、左スキューバイナリツリーと右スキューバイナリツリーの2種類があります。

左に歪んだ二分木

左スキューツリーには、左の子のみに関連付けられたノードがあります。左のサブツリーのみを含む二分木です。

右に歪んだ二分木

右スキューツリーには、右の子にのみ関連付けられたノードがあります。これは、正しいサブツリーのみを含む二分木です。

完全な二分木または適切な二分木

すべてのリーフが同じレベルにあり、すべての非リーフノードに正確に2つの子があり、すべてのレベルで可能な限り多くのノードで構成されている場合、バイナリツリーは完全なバイナリツリーとして定義されます。高さhの完全な二分木は最大2h+1 –1ノードです。

完全な二分木

すべての非リーフノードには正確に2つの子がありますが、すべてのリーフが同じレベルに属する必要はありません。完全な二分木は、最後のレベルを除くすべてのレベルのノード数が最も多いものとして定義されます。最後のレベルの要素は、左から右の方向に入力する必要があります。

ほぼ完全な二分木

ほぼ完全な二分木は、右の子を持つ各ノードに左の子もあるツリーとして定義されます。左の子を持つことは、右の子を持つためにノードを必要としません

一般ツリーと二分木の違い

一般ツリー

• 一般的なツリーには子の数に制限はありません。
• 一般的なツリーでは、式を評価するのは困難です。

二分木

• 二分木には最大2つの子があります
• 二分木では式の評価は簡単です。

木の適用

• 算術式の操作
• シンボルテーブルの作成
• 構文の分析
• 文法を書く
• 式ツリーの作成