【C++】キューを使って二分木をスレッド化二分木に変換する方法（セット1）

このチュートリアルでは、キュー（queue）データ構造を利用して、通常の二分木をスレッド化二分木（Threaded Binary Tree）へ変換するプログラムについて解説します。

スレッド化二分木とは？

スレッド化二分木とは、右の子を持たないノードのNULLポインタ部分を、「中順走査（inorder traversal）における次のノード（中順後続ノード）」への参照に置き換えた二分木のことです。これにより、再帰やスタックに頼らずに効率的な中順走査が可能になります。

今回の課題は、与えられた二分木に対して、キューを活用して中順走査を高速化するための追加リンク（スレッド）を設定し、スレッド化二分木へと変換することです。

アルゴリズムの流れ

1. まず、元の二分木を中順走査し、訪問順にノードをキューへ格納します。
2. 次にもう一度木を走査します。各ノードを処理する際にキューから要素を取り出し（pop）、右の子を持たないノードについては、キューの先頭にあるノード（＝中順後続ノード）を右ポインタに設定し、isThreadedフラグをtrueにします。
3. これにより、すべてのNULL右ポインタがスレッドとして機能するようになります。

C++での実装例

#include <iostream>
#include <queue>
using namespace std;

// スレッド化ツリー用のノード構造体
struct Node {
   int key;
   Node *left, *right;
   bool isThreaded;
};

// 中順走査の順序でノードをキューに格納する
void convert_queue(Node* root, std::queue<Node*>* q){
   if (root == NULL)
      return;
   if (root->left)
      convert_queue(root->left, q);
   q->push(root);
   if (root->right)
      convert_queue(root->right, q);
}

// 木を走査しながらスレッド化ツリーを作成する
void create_threadedtree(Node* root, std::queue<Node*>* q){
   if (root == NULL)
      return;
   if (root->left)
      create_threadedtree(root->left, q);
   q->pop();
   if (root->right)
      create_threadedtree(root->right, q);
   // 右ポインタがNULLの場合は、
   // 中順後続ノード（inorder successor）を指すようにする
   else {
      root->right = q->front();
      root->isThreaded = true;
   }
}

// 木を受け取り、スレッド化された木へ変換する
void createThreaded(Node* root){
   std::queue<Node*> q;
   convert_queue(root, &q);
   create_threadedtree(root, &q);
}

Node* leftMost(Node* root){
   while (root != NULL && root->left != NULL)
      root = root->left;
   return root;
}

// スレッド化ツリーの中順走査を実行する
void inOrder(Node* root){
   if (root == NULL)
      return;
   Node* cur = leftMost(root);
   while (cur != NULL) {
      cout << cur->key << " ";
      // スレッド化されたノードなら、中順後続ノードへ移動
      if (cur->isThreaded)
         cur = cur->right;
      else
         cur = leftMost(cur->right);
   }
}

Node* newNode(int key){
   Node* temp = new Node;
   temp->left = temp->right = NULL;
   temp->key = key;
   return temp;
}

int main(){
   Node* root = newNode(1);
   root->left = newNode(2);
   root->right = newNode(3);
   root->left->left = newNode(4);
   root->left->right = newNode(5);
   root->right->left = newNode(6);
   root->right->right = newNode(7);
   createThreaded(root);
   cout << "Traversing threaded tree :\n";
   inOrder(root);
   return 0;
}

実行結果

Traversing threaded tree :
4 2 5 1 6 3 7

コードのポイント解説

• convert_queue関数： 再帰的に中順走査を行い、ノードを訪問順にキューへpushしていきます。
• create_threadedtree関数： 同じく中順走査の順序で木をたどりながら、各ステップでキューからpopします。右の子を持たないノードには、キューの先頭（front）にある中順後続ノードへのスレッドを張ります。
• leftMost関数： 指定した部分木の最も左側にあるノードを取得します。中順走査の開始点を見つけるために使用されます。
• inOrder関数： スレッド化された木を再帰なしで走査します。isThreadedがtrueなら右ポインタで後続ノードへ移動し、そうでなければ右部分木の最左ノードへ移動します。

このように、キューを一度だけ活用することで、シンプルかつ直感的に二分木をスレッド化二分木へ変換できます。変換後の木は、再帰呼び出しや追加のメモリ消費を抑えながら高速な中順走査を実現できる点が大きなメリットです。