C++で二分木を倍化（ダブルツリー）する方法：サンプルコード付きでわかりやすく解説

このチュートリアルでは、与えられた二分木を「倍化」する方法について学びます。二分木の倍化とは、各ノードの左側に同じ値を持つ新しいノードを挿入し、元のノードをその右側に残す操作のことです。

それでは、問題を解くための手順を順番に見ていきましょう。

アルゴリズムの手順

• ノードクラスを作成します。
• ダミーデータを使って木を初期化します。
• 木を倍化するための再帰関数を記述します。
  • 再帰的に木を走査します。
• 結果を出力して確認します。

再帰関数の処理の流れは以下の通りです。

1. まず、左右の子に対して再帰的に処理を行います。
2. 現在の左の子ノードを一時変数に保存します。
3. 現在のノードと同じ値を持つ新しいノードを作成し、それを左の子として設定します。
4. 新しく作成したノードの左に、保存しておいた元の左の子を接続します。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
class node {
    public:
    int data;
    node* left;
    node* right;
};
node* newNode(int data) {
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;
    return Node;
}
void doubleTree(node* Node) {
    node* oldLeft;
    if (Node == NULL) return;
    doubleTree(Node->left);
    doubleTree(Node->right);
    oldLeft = Node->left;
    Node->left = newNode(Node->data);
    Node->left->left = oldLeft;
}
void printTree(node* node) {
    if (node == NULL) {
        return;
    }
    printTree(node->left);
    cout << node->data << " ";
    printTree(node->right);
}
int main() {
    node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    cout << "Original Tree" << endl;
    printTree(root);
    cout << endl;
    doubleTree(root);
    cout << "Double Tree" << endl;
    printTree(root);
    cout << endl;
    return 0;
}

コードのポイント

doubleTree 関数では、まず再帰的に左右の部分木を処理してから、現在のノードの複製を挿入しています。この順序が重要で、先に子を処理することで、挿入された複製ノードが後続の再帰処理に影響されることなく正しく動作します。

実行結果

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

Original Tree
2 1 3
Double Tree
2 2 1 1 3 3

出力から分かるように、元の木の中順走査（in-order traversal）の結果は「2 1 3」ですが、倍化後は各ノードの複製が直前に現れるため「2 2 1 1 3 3」となります。このように中順走査を使うことで、倍化が正しく行われたかどうかを簡単に確認できます。

まとめ

このチュートリアルでは、再帰を使って二分木を倍化する方法を紹介しました。ポイントは、左右の部分木を先に再帰的に処理し、その後に現在のノードの複製を左の子として挿入することです。この手法は計算量 O(n)、空間計算量も木の高さ分のスタック領域で済むため、効率的なアプローチと言えます。

このチュートリアルについて質問がある場合は、コメント欄でお気軽にお尋ねください。