C++で二分木を論理AND特性を保持する木に変換する方法

はじめに

このチュートリアルでは、与えられた二分木を「論理AND特性」を満たす木へ変換するプログラムをC++で実装する方法を解説します。

ここで扱う問題は次のとおりです。各ノードの値が 0 または 1 のいずれかである二分木が与えられたとき、すべての内部ノードの値を「左の子の値と右の子の値の論理AND演算の結果」に書き換えます。これにより、木全体が論理AND特性を保持するようになります。なお、葉ノードの値はそのまま変更しません。

アルゴリズムの考え方

変換には、葉に近いノードから順に処理する「後順(帰りがけ順)の再帰走査」を利用します。具体的な手順は以下のとおりです。

1. まず、左部分木を再帰的に変換します。
2. 次に、右部分木を再帰的に変換します。
3. 最後に、現在のノードが左右両方の子を持つ場合のみ、その値を「左の子の値 AND 右の子の値」で更新します。

子を1つしか持たないノードや葉ノードは値を更新しないため、NULLチェックを忘れないようにしましょう。

C++による実装例

#include<bits/stdc++.h>
using namespace std;

// 二分木のノード構造体
struct Node{
    int data;
    struct Node* left;
    struct Node* right;
};

// 新しいノードを生成する関数
struct Node* newNode(int key){
    struct Node* node = new Node;
    node->data = key;
    node->left = node->right = NULL;
    return node;
}

// 各ノードが論理AND演算の結果を保持するように木を変換する
void transform_tree(Node *root){
    if (root == NULL)
        return;
    // まず左部分木を処理
    transform_tree(root->left);
    // 次に右部分木を処理
    transform_tree(root->right);
    // 左右両方の子が存在する場合のみ、AND演算の結果で値を更新
    if (root->left != NULL && root->right != NULL)
        root->data = (root->left->data) & (root->right->data);
}

// 中順走査で木の値を出力する
void print_tree(Node* root){
    if (root == NULL)
        return;
    print_tree(root->left);
    printf("%d ", root->data);
    print_tree(root->right);
}

int main(){
    Node *root = newNode(0);
    root->left = newNode(1);
    root->right = newNode(0);
    root->left->left = newNode(0);
    root->left->right = newNode(1);
    root->right->left = newNode(1);
    root->right->right = newNode(1);
    printf("変換前 :\n");
    print_tree(root);
    transform_tree(root);
    printf("\n変換後 :\n");
    print_tree(root);
    return 0;
}

実行結果

変換前 :
0 1 1 0 1 0 1
変換後 :
0 0 1 0 1 1 1

コードのポイントと計算量

この実装では各ノードをちょうど1回ずつ訪問するため、時間計算量はノード数を n とすると O(n) です。空間計算量は再帰の深さに依存し、木が偏っている最悪ケースで O(n)、平衡な木であれば O(log n) となります。

重要なのは、子ノードの値が確定した後に親ノードを更新する、ボトムアップ(葉から根へ)の処理になっている点です。これにより、一度の走査で正しく論理AND特性を満たす木を構築できます。