糸付き2分木/Threaded Binary Tree
子ノードがない場合に間順の前と後ろをそれぞれ左の子ポインタと右の子ポインタに設定しておいた木構造である。この場合、子ノードの有無はポインタ以外のフィールドで示す必要がある。これを使うと、間順走査の効率が非常によくなるが、前順や後順は通常のスタックを使った実装の方がよい。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
糸付き2分木/Threaded Binary Treeがどのようなアルゴリズムかについては、英語になりますが、以下の説明がとても分かりやすいです。
まずは、通常の2分木のノードを以下のように考えます。
上のノードを用いて、以下のような2分木を考えます。
図を見ると、使われていないポインタがたくさんあります。例えば、’E’のノードでは、左右のポインタがどちらとも使われていません。
この使われていないポインタを有効利用しようというのが糸付き2分木の考え方です。
2分木から糸付き2分木への変換
上の2分木を糸付き2分木に変換します。
- 一番左端、一番右端の空のポインタはそれぞれNullのままにする。
- 左側のポインタが空である場合は’InOrder predecessor’つまり「通り掛け順の前のノード」を、右側のポインタが空である場合は’InOrder successor’つまり「通り掛け順の次のノード」を指す。（PreOrder、PostOrderの場合でも同じように定義できると思いますが、ここでは、InOrderの場合のみを考えます）
通り掛け順のノードの探索を考えると、以下のような順序になります。
D → B → E → A → C → F
よって、一番左端’D’のポインタは前のノードが存在しないので、また一番右端’F’のポインタは次のノードが存在しないので、それぞれNullになります。
Null → D → B → E → A → C → F → Null
子のポインタを点線によって図示すると、以下のようになります。
しかし、このまま実装した場合、ポインタが子ノードを指しているのか、それとも通り掛け順の前後のノードを指しているのか、どちらか判断できないという問題が生じてしまいます。
フラグの導入
そこで、フラグを導入し、以下のようなノードにすることで上述の問題を解決します。
フラグはポインタが子ノードを指す場合は1、通り掛け順の前後のノードを指す場合は0とすることにします。
フラグを加えて、2分木を再び図示すると、以下のようになります。
この状態で左端、右端のノードについて考えます。
左右最端ともに子ノードはないので、フラグを0にすると、これらの通り掛け順の前後のノードはNullなのでを指し示すことができず、一貫性が失われます。
ダミーノードの導入
そこでダミーノードを導入します。
ダミーノードはデータは無し、左右ともフラグは１、左ポインタはルートを、右ポインタは自分自身を指します。また、左右最端の前後ノードとなります。
図示すると以下のようになります。
ダミーノードの導入によりフラグの一貫性が保つことができます。