C++でスレッド付き二分木を中間順（Inorder）に走査する方法

本記事では、スレッド付き二分木（Threaded Binary Tree）というデータ構造について詳しく解説します。二分木の各ノードは最大2つの子を持ちますが、子が1つしかない、あるいはまったく存在しない場合、通常の連結リスト表現ではそのリンク部分はNULLのまま無駄になってしまいます。スレッド付き二分木では、この空きリンクを「スレッド」として再利用することで、メモリを有効活用しながら効率的な走査を実現できます。

ノードの左または右の子領域が空いている場合、その領域がスレッドとして利用されます。スレッド付き二分木には大きく分けて片側スレッド木（シングルスレッド）と完全スレッド木の2種類が存在します。

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

完全スレッド付き二分木では、各ノードは5つのフィールドを持ちます。通常の二分木ノードと同じ3つのフィールドに加えて、左右のリンクが実際の子ノードへのリンクなのか、それともスレッドなのかを判別するためのブール値を格納する2つのフィールドを持っています。

以下は完全スレッド付き二分木のイメージ図です。

アルゴリズム

スレッドを利用した中間順走査（Inorder Traversal）は、再帰やスタックを使わずに実装できるのが大きな特徴です。手順は以下の通りです。

inorder():
Begin
    temp := root
    無限に繰り返す：
        p := temp
        temp := temp の右側
        もし p の右フラグが false ならば：
            temp の左フラグが true になるまで：
                temp := temp の左側
            繰り返し終了
        終了条件
        もし temp と root が同じならば：
            ループを抜ける
        終了条件
        temp のキーを出力する
    繰り返し終了
End

C++での実装例

それでは、実際にC++でスレッド付き二分木を実装し、中間順走査を行うコードを見てみましょう。

#include <iostream>
#define MAX_VALUE 65536
using namespace std;
class N { //ノードの宣言
    public:
        int k;
        N *l, *r;
        bool leftTh, rightTh;
};
class ThreadedBinaryTree {
    private:
    N *root;
    public:
    ThreadedBinaryTree() { //変数を初期化するコンストラクタ
        root= new N();
        root->r= root->l= root;
        root->leftTh = true;
        root->k = MAX_VALUE;
    }
    void insert(int key) {
        N *p = root;
        for (;;) {
        if (p->k< key) { //右スレッドへ移動
            if (p->rightTh)
               break;
            p = p->r;
        }
        else if (p->k > key) { //左スレッドへ移動
            if (p->leftTh)
               break;
            p = p->l;
        }
        else {
            return;
        }
    }
    N *temp = new N();
    temp->k = key;
    temp->rightTh= temp->leftTh= true;
    if (p->k < key) {
        temp->r = p->r;
        temp->l= p;
        p->r = temp;
        p->rightTh= false;
    }
    else {
        temp->r = p;
        temp->l = p->l;
        p->l = temp;
        p->leftTh = false;
    }
}
void inorder() { //木の内容を出力する
    N *temp = root, *p;
    for (;;) {
        p = temp;
        temp = temp->r;
        if (!p->rightTh) {
            while (!temp->leftTh) {
                temp = temp->l;
            }
        }
        if (temp == root)
            break;
            cout<<temp->k<<" ";
        }
        cout<<endl;
    }
};
int main() {
    ThreadedBinaryTree tbt;
    cout<<"Threaded Binary Tree\n";
    tbt.insert(56);
    tbt.insert(23);
    tbt.insert(89);
    tbt.insert(85);
    tbt.insert(20);
    tbt.insert(30);
    tbt.insert(12);
    tbt.inorder();
    cout<<"\n";
}

出力結果

Threaded Binary Tree
12 20 23 30 56 85 89

まとめ

このように、スレッド付き二分木を利用すると、NULLになっているポインタをスレッドとして活用できるため、再帰呼び出しや追加のスタック構造なしに中間順走査を実行できます。挿入処理も二分探索木と同様の手順で行われ、空きリンクをたどることで次の要素へ効率的に移動できる点が大きなメリットです。上記の出力結果からも、要素が昇順（12, 20, 23, 30, 56, 85, 89）に正しく表示されていることが確認できます。