C++で二分木のすべてのノードの積を求めるアルゴリズムと実装例

ノードからなる二分木（バイナリツリー）が与えられ、その二分木に含まれるすべてのノードの値の積を求めるのが本記事の課題です。

二分木には、木全体の頂点となる「ルートノード」が存在します。各ノードはデータ部分を持ち、さらに左部分木を形成するための左ポインタと、右部分木を形成するための右ポインタを保持しています。木を走査する際には、一時的なポインタを用意し、左ポインタをたどって左部分木へ、右ポインタをたどって右部分木へと移動することで、木全体を効率的に巡回できます。

入力

出力

Nodes are-: 10, 20, 30, 40, 50, 60
積 = 10 × 20 × 30 × 40 × 50 × 60 = 720,000,000

アプローチ

• ノードのデータを入力します。

• ルートノードから出発し、左部分木または右部分木へ移動しながらすべてのノードを走査します。

• 各ノードのデータを取得し、保持している値に新しいデータを順次掛けていきます。

• 積を保持している一時変数の値を出力します。

アルゴリズム

開始
ステップ1 → ノードの構造体を作成
    struct node
        int data
        node *left, *right
終了
ステップ2 → ノードを木に挿入する関数を宣言
    node* new_node(int data)
        node* temp = new node()
        temp→data = data
        temp→left = temp→right = NULL
        temp を返す
終了
ステップ3 → すべてのノードの積を求める関数を宣言
    int node_product(node* root)
        IF root == NULL
            return 1
        End IF
        return (root→data * node_product(root→left) *
            node_product(root→right))
ステップ4 → main() 内での処理
    node* root = new_node(10) を作成
    root→left = new_node(20) を設定
    root→left→left = new_node(30) を設定
    int product = node_product(root) を設定
    product を表示
停止

実装例

#include <iostream>
using namespace std;
// ノードの構造体
struct node{
    int data;
    node *left, *right;
};
// 新しいノードを作成する関数
node* new_node(int data){
    node* temp = new node();
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
// すべてのノードの積を計算する関数
int node_product(node* root){
    if (root == NULL)
        return 1;
    return (root->data * node_product(root->left) * node_product(root->right));
}
int main(){
    node* root = new_node(10);
    root->left = new_node(20);
    root->right = new_node(30);
    root->left->left = new_node(40);
    root->left->right = new_node(50);
    root->right->left = new_node(60);
    int product = node_product(root);
    cout << "Product of all the nodes is: " << product << endl;
    return 0;
}

実行結果

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

Product of all the nodes is: 720000000

補足：再帰の仕組みと注意点

このアルゴリズムでは、node_product 関数が再帰的に呼び出されます。ノードが NULL の場合に 1 を返すのは、乗算における単位元（何倍しても値が変わらない数）として機能させるためです。これにより、子を持たない葉のノードに到達したときも計算が正しく継続されます。

なお、ノード数が多い場合やノードの値が大きい場合は、積が int 型の最大値（2,147,483,647）を超えてオーバーフローする恐れがあります。そのようなケースでは、long long 型の使用を検討してください。