C++で二分木を循環双方向リンクリストに変換する方法を解説

このチュートリアルでは、二分木（バイナリツリー）を循環双方向リンクリストへ変換するC++プログラムについて詳しく解説します。

与えられるのは1つの二分木です。私たちのタスクは、木の左ポインタと右ポインタをそれぞれリンクリストの「前の要素」「次の要素」に対応させ、中間順走査（Inorder Traversal）の順序をそのまま循環リンクリストの並びとして実現することです。

アルゴリズムの考え方

この問題は再帰を利用するとシンプルに解けます。処理の流れは以下の通りです。

• 左部分木を再帰的に循環リンクリストへ変換する
• 右部分木を再帰的に循環リンクリストへ変換する
• 現在のノードを、自分自身の左右ポインタを自分に向けることで1ノードだけの循環リンクリストとして扱う
• 「左リスト＋現在ノード」と「右リスト」を連結し、完成したリストの先頭ノードを返す

リスト同士の連結では、各循環リンクリストの先頭ノードの left ポインタが必ず末尾ノードを指しているという性質を利用します。これにより、効率よく両リストの先頭と末尾をつなぎ合わせることができます。

サンプルコード

#include<iostream>
using namespace std;

// 二分木のノード構造体
struct Node {
    struct Node *left, *right;
    int data;
};

// 左リストの末尾に右リストを連結する関数
Node *concatenate(Node *leftList, Node *rightList) {
    // 片方のリストが空なら、もう片方をそのまま返す
    if (leftList == NULL)
        return rightList;
    if (rightList == NULL)
        return leftList;

    Node *leftLast = leftList->left;   // 左リストの末尾ノード
    Node *rightLast = rightList->left; // 右リストの末尾ノード

    // 左リストと右リストを接続
    leftLast->right = rightList;
    rightList->left = leftLast;
    leftList->left = rightLast;
    rightLast->right = leftList;

    return leftList;
}

// 二分木を循環リンクリストへ変換し、先頭ノードを返す
Node *bTreeToCList(Node *root) {
    if (root == NULL)
        return NULL;

    Node *left = bTreeToCList(root->left);
    Node *right = bTreeToCList(root->right);

    // 現在のノードを1ノードの循環リストにする
    root->left = root->right = root;

    return concatenate(concatenate(left, root), right);
}

// 循環リンクリストを表示する
void print_Clist(Node *head) {
    cout << "Circular Linked List is :\n";
    Node *itr = head;
    do {
        cout << itr->data << " ";
        itr = itr->right;
    } while (head != itr);
    cout << "\n";
}

// 新しいノードを生成してそのアドレスを返す
Node *newNode(int data) {
    Node *temp = new Node();
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

int main() {
    Node *root = newNode(10);
    root->left = newNode(12);
    root->right = newNode(15);
    root->left->left = newNode(25);
    root->left->right = newNode(30);
    root->right->left = newNode(36);

    Node *head = bTreeToCList(root);
    print_Clist(head);

    return 0;
}

実行結果

Circular Linked List is :
25 12 30 10 36 15

コードのポイント

concatenate 関数：O(1) でのリスト連結

循環リンクリストでは、先頭ノードの left ポインタが常に末尾ノードを指します。そのため leftList->left で左リストの末尾を、rightList->left で右リストの末尾を即座に取得できます。あとは4つのポインタを付け替えるだけで、線形探索なしの O(1) 計算量で2つのリストを連結できるのが大きな特徴です。

bTreeToCList 関数：再帰による変換

この関数は再帰的に動作します。まず左右の子部分木をそれぞれ循環リンクリストへ変換し、続いて root->left = root->right = root; によって現在のノードを独立した1ノードの循環リストに変えます。最後に「左リスト → 現在ノード → 右リスト」の順で連結することで、中間順走査と同じ順序を持つ循環リンクリストが完成します。

表示用の print_Clist 関数では、do-while 文を使って先頭ノードに戻ってきた時点で走査を終了しています。これは循環リンクリスト特有の終端判定方法であり、NULL チェックが不要になる点も覚えておくと便利です。