C++で二分木を双方向リンクリストに変換する方法（セット1）

はじめに

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

変換対象の二分木が与えられ、それを双方向リンクリストへ変換するのが課題です。具体的には、二分木の各ノードが持つ左ポインタ（left）と右ポインタ（right）を、リンクリストの前ポインタ（prev）と次ポインタ（next）としてそのまま再利用します。さらに、変換後のリンクリストのノードの並び順は、元の二分木の通り順（中順・inorder）トラバーサルと一致していなければなりません。

アプローチ

この問題には非常にシンプルな手法が使えます。二分木を通り順で走査しながら、同時に双方向リンクリストのノードを構築していきます。走査の過程で、各ノードのleftポインタを直前に訪問したノード（prev）に、rightポインタを次に訪問するノードに設定することで、自然にリンクリストが完成します。

アルゴリズムの手順

1. ノードがNULLの場合は何もせずに戻る。
2. 再帰的に左部分木を変換する。
3. prevがNULLの場合、現在のノードはリストの先頭（head）となる。
4. prevがNULLでない場合は、現在のノードのleftをprevに、prevのrightを現在のノードに設定して双方向にリンクを張る。
5. prevを現在のノードに更新する。
6. 再帰的に右部分木を変換する。

実装例

#include <iostream>
using namespace std;
//二分木のノード構造体
struct node{
    int data;
    node* left;
    node* right;
};
//走査しながら双方向リンクリストのノードを構築する
void binarytodll(node *root, node **head){
    if (root == NULL)
        return;
    static node* prev = NULL;
    //左部分木を変換
    binarytodll(root->left, head);
    if (prev == NULL)
        *head = root;
    else {
        root->left = prev;
        prev->right = root;
    }
    prev = root;
    //右部分木を変換
    binarytodll(root->right, head);
}
//新しいノードを生成する
node* newNode(int data) {
    node* new_node = new node;
    new_node->data = data;
    new_node->left = new_node->right = NULL;
    return (new_node);
}
//双方向リンクリストのノードを出力する
void print_dll(node *node){
    while (node!=NULL) {
        cout << node->data << " ";
        node = node->right;
    }
}
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 = NULL;
    binarytodll(root, &head);
    print_dll(head);
    return 0;
}

出力

25 12 30 10 36 15

コードのポイント

この実装の鍵となっているのは、関数内で宣言されたstatic変数のprevです。通り順トラバーサルでは直前に訪問したノードが常に分かるため、このprevを使って現在のノードと前のノードを双方向にリンクできます。最初に訪問されるノード（最も左側のノード）はprevがNULLの状態で処理されるため、リストの先頭（head）として記録されます。

サンプルコードでは、10を根とする二分木を構築しています。通り順トラバーサルの結果である「25 12 30 10 36 15」が、そのまま双方向リンクリストの並び順になります。

計算量については、すべてのノードを一度ずつ訪問するため時間計算量はO(n)、再帰呼び出しのスタック深さは木の高さに依存するため空間計算量はO(h)（hは木の高さ）となります。