C++で二分木を双方向連結リストに変換する方法（セット2）

はじめに

このチュートリアルでは、C++を使って二分木を双方向連結リスト（Doubly Linked List）に変換するプログラムについて解説します。

入力として二分木が与えられ、それを双方向連結リストへ変換するのが課題です。変換の際には、木の左ポインタと右ポインタを、それぞれリストの前ポインタ（prev）と次ポインタ（next）として再利用します。また、変換後のリストの並び順は、元の二分木を中間順走査（inorder traversal）した順序と一致していなければなりません。

アルゴリズムの考え方

ここでは、少し異なるアプローチを採用します。

• 二分木を逆中間順（右部分木 → 根 → 左部分木）で走査します。
• 各ノードを訪問するたびに、そのノードをリストの先頭に挿入し、head ポインタを最新のノードへ移動させます。
• この処理により、双方向連結リストが末尾から先頭へ向かって構築されていきます。

処理の手順

1. まず右部分木を再帰的に変換します。
2. 現在のノードの right ポインタを、現在の head に接続します。
3. head が NULL でない場合、head の left ポインタを現在のノードに向けます。
4. head を現在のノードに更新します。
5. 最後に左部分木を再帰的に変換します。

C++での実装例

#include <stdio.h>
#include <stdlib.h>
// 木のノード構造体
struct Node{
   int data;
   Node *left, *right;
};
// 二分木を双方向連結リストへ変換
void binary_todll(Node* root, Node** head_ref){
   if (root == NULL)
      return;
   // 右部分木を変換
   binary_todll(root->right, head_ref);
   // 現在のノードをリストの先頭に挿入
   root->right = *head_ref;
   // head ポインタを移動
   if (*head_ref != NULL)
      (*head_ref)->left = root;
   *head_ref = root;
   // 左部分木を変換
   binary_todll(root->left, head_ref);
}
// 新しいノードを生成
Node* newNode(int data){
   Node* node = new Node;
   node->data = data;
   node->left = node->right = NULL;
      return node;
}
// 双方向連結リストを出力
void print_dll(Node* head){
   printf("Doubly Linked list:\n");
   while (head) {
      printf("%d ", head->data);
      head = head->right;
   }
}
int main(){
   Node* root = newNode(5);
   root->left = newNode(3);
   root->right = newNode(6);
   root->left->left = newNode(1);
   root->left->right = newNode(4);
   root->right->right = newNode(8);
   root->left->left->left = newNode(0);
   root->left->left->right = newNode(2);
   root->right->right->left = newNode(7);
   root->right->right->right = newNode(9);
   Node* head = NULL;
   binary_todll(root, &head);
   print_dll(head);
   return 0;
}

出力結果

Doubly Linked list:
0 1 2 3 4 5 6 7 8 9

計算量

• 時間計算量：O(n) — 各ノードを一度だけ訪問します（n はノード数）。
• 空間計算量：O(h) — 再帰呼び出しのためのスタック領域が必要です（h は木の高さ）。

まとめ

逆中間順で走査しながら head ポインタを更新していくことで、余分なデータ構造を追加することなく、二分木のノードをそのまま双方向連結リストへ変換できます。中間順走査の順序が保たれるため、二分探索木の場合は結果としてソート済みの連結リストが得られる点も大きなメリットです。