C++で二分木をミラーツリーに変換する方法

このチュートリアルでは、二分木（バイナリツリー）をそのミラーツリーへ変換するC++プログラムについて解説します。

ここでは、ある一つの二分木が与えられるものとします。私たちの課題は、木の左側と右側を入れ替えることで、与えられた二分木からミラーツリーを作成することです。

ミラーツリーとは？

ミラーツリーとは、元の木を鏡に映したように左右を反転させた木のことです。すべてのノードで左の子と右の子が入れ替わるため、中間順走査（Inorder Traversal）の結果も完全に逆順になります。

アルゴリズムの考え方

変換には再帰呼び出しを利用します。各ノードに対して、まず左右の部分木をそれぞれ再帰的に反転し、その後、そのノード自身の左右ポインタを交換します。これにより木全体が反転され、処理の時間計算量はノード数に比例するO(n)で抑えられます。

実装例

#include<bits/stdc++.h>
using namespace std;
// 二分木のノード構造体
struct Node{
   int data;
   struct Node* left;
   struct Node* right;
};
// 子を持たない新しいノードの生成
struct Node* newNode(int data){
   struct Node* node = (struct Node*)malloc(sizeof(struct Node));
   node->data = data;
   node->left = NULL;
   node->right = NULL;
   return(node);
}
void mirror(struct Node* node){
   if (node == NULL)
      return;
   else{
      struct Node* temp;
      // 左右の部分木を再帰的に反転
      mirror(node->left);
      mirror(node->right);
      // 左右のポインタを交換
      temp = node->left;
      node->left = node->right;
      node->right = temp;
   }
}
// 中間順走査の結果を出力
void print_tree(struct Node* node){
   if (node == NULL)
      return;
   print_tree(node->left);
   cout << node->data << " ";
   print_tree(node->right);
}
int main(){
   struct Node *root = newNode(1);
   root->left = newNode(2);
   root->right = newNode(3);
   root->left->left = newNode(4);
   root->left->right = newNode(5);
   // 元の木の中間順走査を出力
   cout << "Inorder traversal of the constructed" << endl;
   print_tree(root);
   mirror(root);
   // ミラーツリーの中間順走査を出力
   cout << "\nInorder traversal of the mirror tree" << endl;
   print_tree(root);
   return 0;
}

出力

Inorder traversal of the constructed
4 2 5 1 3
Inorder traversal of the mirror tree
3 1 5 2 4

実行結果から、元の木の中間順走査「4 2 5 1 3」に対して、ミラーツリーでは「3 1 5 2 4」と完全に逆順に出力されていることが確認できます。このように、再帰的な左右の入れ替えを行うだけで、シンプルかつ効率的に二分木を反転することが可能です。