C++の二分木のすべての葉ノードの積

ノードを含む二分木が与えられ、タスクは、与えられた二分木のすべてのリーフノードの積を見つけることです。

リーフノードは、子を持たないエンドノードです。ツリーでは、親ノードにしかなり得ないルートノードを除いて、ノードは親ノードまたは子ノードとして機能できます。したがって、左右のポインタがNULLであるノードは、リーフノードです。

入力

出力

Leaf nodes are -: 23, 34, 25
Product-: 23*34*25 = 19550

アプローチ

• ノードデータを入力する

• ルートノードから開始して、トラバースのために左側のサブディレクトリまたは右側のサブディレクトリに移動するすべてのノードをトラバースします。

• 左右のポインタがNULLのノードを一時変数に格納して、製品を検索します。

• 乗算された値を保持する一時変数の値を出力します。

アルゴリズム

Start
Step 1 → create structure of a node and temp, next and head as pointer to a
   structure node
      struct node
         int data
         Create node *left, *right
      End
Step 2 → declare function to insert a node in a tree
   node* new_node(int data)
      Set node* temp = new node()
      Set temp→data = data
      Set temp→left = temp→right = NULL
      return temp
   End
Step 3 → Declare a function to find product of all the leaf nodes
   void leaf(node* root, int &product)
      IF (!root)
         Return
      End
      IF (!root→left && !root→right)
         Set product *= root→data
         Call leaf(root→left, product)
         Call leaf(root→right, product)
Step 4 → In main()
   Create node* root = new_node(10)
   Set root→left = new_node(20)
   Set root→left→left = new_node(30)
   Set int product = 1
   Call leaf(root, product)
   Display product
Stop

例

#include <bits/stdc++.h>
using namespace std;
//structure of a node
struct node{
   int data;
   node *left, *right;
};
//function to create a new leaf of a tree
node* new_node(int data){
   node* temp = new node();
   temp→data = data;
   temp→left = temp→right = NULL;
   return temp;
}
//function to find the product of all leaf nodes of a tree
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