C++で二分木のすべての葉ノードの積を求める方法

ノードから構成される二分木が与えられたとき、その二分木に含まれるすべての葉ノードの値の積を求めるのが本記事のテーマです。

葉ノードとは、子ノードを持たない末端のノードのことを指します。木構造では、ルートノード以外の各ノードは親ノードにも子ノードにもなり得ますが、ルートノードは親としてのみ存在します。つまり、左ポインタと右ポインタがどちらもNULLになっているノードこそが葉ノードだと判定できます。

入力

出力

葉ノード -: 23, 34, 25
積 -: 23 × 34 × 25 = 19550

アプローチ

• ノードのデータを入力する
• ルートノードから出発し、左部分木または右部分木へ再帰的に降りながら全ノードを走査する
• 左右のポインタがともにNULLであるノード（＝葉ノード）を検出したら、その値を積算用の変数に掛けていく
• 積を保持している変数の値を出力する

アルゴリズム

開始
ステップ 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
      return temp
   終了
ステップ 3 → すべての葉ノードの積を求める関数を宣言する
   void leaf(node* root, int &product)
      IF (!root)
         Return
      IF (!root→left && !root→right)
         product *= root→data
      leaf(root→left, product) を呼び出す
      leaf(root→right, product) を呼び出す
ステップ 4 → main() 内で
   node* root = new_node(10) を生成
   root→left = new_node(20) を設定
   root→left→left = new_node(30) を設定
   int product = 1 を設定
   leaf(root, product) を呼び出す
   product を表示
終了

実装例

#include <bits/stdc++.h>
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;
}
// 木のすべての葉ノードの積を求める関数
void leaf(node* root, int &product) {
   if (!root)
      return;
   // 左右どちらの子も持たないノードが葉ノード
   if (!root->left && !root->right)
      product *= root->data;
   leaf(root->left, product);
   leaf(root->right, product);
}
int main() {
   node* root = new_node(10);
   root->left = new_node(20);
   root->left->left = new_node(30);
   root->left->right = new_node(40);
   root->right = new_node(50);
   root->right->right = new_node(60);
   root->right->left = new_node(70);
   int product = 1;
   leaf(root, product);
   cout << "product of a leaf nodes are :" << product;
   return 0;
}

出力

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

product of a leaf nodes are :5040000

この例では、葉ノードは 30、40、60、70 の4つであり、30 × 40 × 60 × 70 = 5,040,000 となるため、再帰的な走査によってすべての葉ノードの積が正しく計算できていることが確認できます。