データ構造入門：スレッド二分木（Threaded Binary Tree）の仕組みと種類を解説

スレッド二分木（Threaded Binary Tree）とは

本記事では、データ構造の一つである「スレッド二分木」について詳しく解説します。二分木の各ノードは最大で2つの子を持ちますが、子が1つしかない場合、あるいは1つも存在しない場合、連結リスト表現ではそのリンク部分がnull（空）のまま残され、メモリが無駄になってしまいます。スレッド二分木では、この未使用のリンク領域を「スレッド（糸）」として再利用することで、メモリを有効活用しつつ効率的な巡回を可能にしています。

スレッド二分木の種類

スレッド二分木には、大きく分けて「単一スレッド二分木」と「完全スレッド二分木」の2種類があります。さらに単一スレッド方式には、「左スレッド型」と「右スレッド型」という2つのバリエーションが存在します。

左スレッド型と右スレッド型の動作

左スレッド型では、あるノードに左の子が存在しない場合、その左ポインタは中間順巡回（inorder traversal）における先行ノード（inorder predecessor）を指すように設定されます。同様に、右スレッド型では、右の子を持たないノードの右ポインタは、中間順巡回における後続ノード（inorder successor）を指します。そして、いずれの場合も対応する先行ノードや後続ノードが存在しないときは、ヘッダーノードを指すことになります。

以下は、左スレッド型および右スレッド型の木の例です。

完全スレッド二分木のノード構造

完全スレッド二分木では、各ノードが合計5つのフィールドを持つ点が特徴です。通常の二分木ノードと同じ3つのフィールド（左リンク・データ・右リンク）に加えて、その側のリンクが実際の子ノードへのリンクなのか、それともスレッドなのかを判別するためのブール値（真偽値）フラグが2つ追加されています。

次の図は、完全スレッド二分木の構造を示したものです。

このようにスレッドを活用することで、スタックを使用せずに中間順巡回を実行できるなど、メモリの有効利用と処理効率の向上という大きなメリットが得られます。