C++で二分木のミラー（鏡像）を作成する方法

このチュートリアルでは、C++を使って与えられた二分木を反転させ、ミラーツリー（鏡像木）を作成する方法を解説します。

ミラーツリーとは、元の木の左右の子をすべて入れ替えた状態の木のことです。それでは、問題を解くための手順を見ていきましょう。

解決手順

• ノードを表す構造体（struct Node）を定義します。
• ダミーデータを使って二分木を構築します。
• 与えられた二分木のミラーを求める再帰関数を作成します。
  • 左の子ノードと右の子ノードに対して再帰的に関数を呼び出します。
  • 左の子と右の子を入れ替えます。
• 結果の木を出力して確認します。

サンプルコード

実際のコードを見てみましょう。

#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 = new Node;
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}
void convertTreeToItsMirror(struct Node* node) {
    if (node == NULL) {
        return;
    }
    else {
        struct Node* temp;
        convertTreeToItsMirror(node->left);
        convertTreeToItsMirror(node->right);
        temp = node->left;
        node->left = node->right;
        node->right = temp;
    }
}
void printTree(struct Node* node) {
    if (node == NULL) {
        return;
    }
    printTree(node->left);
    cout << node->data << " ";
    printTree(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 << "Tree: ";
    printTree(root);
    cout << endl;
    convertTreeToItsMirror(root);
    cout << "Mirror of the Tree: ";
    printTree(root);
    cout << endl;
    return 0;
}

実行結果

上記のコードを実行すると、以下のような出力が得られます。

Tree: 4 2 5 1 3
Mirror of the Tree: 3 1 5 2 4

コードのポイント

このアルゴリズムの計算量は、木のノード数を n とすると O(n) です。各ノードを一度だけ訪問し、左右の子ポインタを入れ替えるだけなので非常に効率的です。また、再帰の深さは木の高さに依存するため、最悪の場合（偏った木）には O(n) のスタック領域が必要になります。

まとめ

このように、シンプルな再帰処理だけで二分木のミラーを作成することができます。チュートリアルについて質問がある場合は、コメント欄でお気軽にお尋ねください。