C++で二分木を変換する:各ノードに右部分木の合計値を格納する方法

このチュートリアルでは、二分木を変換して、すべてのノードがその右部分木に含まれる全ノードの合計値を保持するようにするプログラムについて解説します。

具体的には、二分木が与えられたとき、各ノードの値が「そのノード自身の値+右部分木の合計」に等しくなるような新しい木を返すことが課題となります。

アルゴリズムの考え方

この問題は、再帰(後順トラバーサルの考え方)を用いることで簡潔に解くことができます。各ノードに対して以下の手順を実行します。

• 右部分木を再帰的に変換し、その合計値を取得する
• 左部分木を再帰的に変換し、その合計値を取得する
• 現在のノードの値に右部分木の合計値を加算する
• 親ノードへは「更新後のノードの値+左部分木の合計値」を返す

葉ノードの場合は自身の値をそのまま返し、空のノード(NULL)の場合は0を返します。これにより、すべてのノードが右部分木の合計を反映した値に更新されます。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
// ツリーのノード構造体
struct Node {
    int data;
    Node *left, *right;
};
// 新しいノードの作成
struct Node* createNode(int item){
    Node* temp = new Node;
    temp->data = item;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}
// 新しい二分木の生成
int rightsum_tree(Node* root){
    if (!root)
        return 0;
    if (root->left == NULL && root->right == NULL)
        return root->data;
    // 左右の部分木の値を更新
    int rightsum = rightsum_tree(root->right);
    int leftsum = rightsum_tree(root->left);
    // 右部分木の合計を加算
    root->data += rightsum;
    return root->data + leftsum;
}
// 木を中順(インオーダー)で走査
void inorder(struct Node* node){
    if (node == NULL)
        return;
    inorder(node->left);
    cout << node->data << " ";
    inorder(node->right);
}
int main(){
    struct Node* root = NULL;
    root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->right = createNode(6);
    rightsum_tree(root);
    cout << "Updated Binary Tree :\n";
    inorder(root);
    return 0;
}

出力

Updated Binary Tree :
4 7 5 10 9 6

コードの解説

例として、ルート1、左の子2、右の子3、2の子として4と5、3の右子として6を持つ二分木を考えます。変換後、各ノードは以下のように更新されます。

• 葉ノードの4、5、6はそのままの値を保持します。
• ノード2は自身の値2と右部分木の合計5を足して7になります。
• ノード3は自身の値3と右部分木の合計6を足して9になります。
• ルートの1は自身の値1と右部分木の合計9を足して10になります。

この結果を中順(インオーダー)走査で出力すると「4 7 5 10 9 6」となり、期待どおりの出力が得られます。

計算量

各ノードを一度だけ訪問するため、時間計算量はO(N)(Nはノード数)です。再帰呼び出しの深さは木の高さに依存するため、木が偏っている最悪の場合、空間計算量はO(N)となります。