C++で指定された値xになる合計サブツリーをカウントします

入力として二分木と値xが与えられます。目標は、ノードの重みの合計がxに等しい二分木のすべてのサブツリーを見つけることです。

例

入力

x=14.値を入力した後に作成されるツリーを以下に示します

出力

Count of subtrees that sum up to a given value x are: 1

説明

we are given with a x value as 14. As we can see there is only one leaf node with the values as 14 therefore the count is 1.

入力

x=33。値を入力した後に作成されるツリーを以下に示します-

出力

Count of subtrees that sum up to a given value x are: 2

説明

we are given with a x value as 33. As we can see there are two subtrees
with the sum values as 33 therefore the count is 2.

以下のプログラムで使用されるアプローチは次のとおりです −

このアプローチでは、ルートノードの左側のサブツリーと右側のサブツリーの重みの合計を再帰的に計算し、最後にそれをルートの重みに追加します。合計がxに等しい場合は、カウントをインクリメントします。

• ルートへのポインタとしてルートを使用してツリーTree_Nodeを構築します。

• 関数insert_Node（int data）は、このツリーにノードを追加します。

• 関数subtrees_x（Tree_Node * root、int x）は、ツリーandxへのルートポインターを取得し、指定された値xまでの合計サブツリーの数を返します。

• 再帰的にカウントを計算するため、静的変数のカウントを0とします。

• タイプTree_nodeの静的ノードをルートとします。

• 変数Left_subtree=0、Right_subtree=0を初期化します。ルートからの左右のサブツリーのノードの重みの合計。

• ルートがNULLの場合、合計を0として返します。

• 左のサブツリー内のノードの合計について、Left_subtree + =subtrees_x（root-> Left、x）を計算します。

• 左側のサブツリーのノードの合計について、Right_subtree + =subtrees_x（root-> Right、x）を計算します。

• sum =Left_subtree + Right_subtree +root->ldataを設定します。

• 合計がxに等しい場合は、カウントをインクリメントします。

• 開始ノードではなくtemp！=rootの場合、合計をLeft_subtree + root-> data+Right_subtreeとして返します。

• 最後に、ノードの合計がxに等しいツリーの必要な数としてカウントを返します。

例

#include <bits/stdc++.h>
using namespace std;
struct Tree_Node{
   int data;
   Tree_Node *Left, *Right;
};
Tree_Node* insert_Node(int data){
   Tree_Node* new_node = (Tree_Node*)malloc(sizeof(Tree_Node));
   new_node−>data = data;
   new_node−>Left = new_node−>Right = NULL;
   return new_node;
}
int subtrees_x(Tree_Node* root, int x){
   static int count = 0;
   static Tree_Node* temp = root;
   int Left_subtree = 0, Right_subtree = 0;
   if(root == NULL){
      return 0;
   }
   Left_subtree += subtrees_x(root−>Left, x);
   Right_subtree += subtrees_x(root−>Right, x);
   int sum = Left_subtree + Right_subtree + root−>data;
   if(sum == x){
      count++;
   }
   if(temp != root){
      int set = Left_subtree + root−>data + Right_subtree;
      return set;
   }
   return count;
}
int main(){
   Tree_Node* root = insert_Node(10);
   root−>Left = insert_Node(20);
   root−>Right = insert_Node(12);
   root−>Left−>Left = insert_Node(14);
   root−>Left−>Right = insert_Node(1);
   root−>Right−>Left = insert_Node(21);
   root−>Right−>Right = insert_Node(11);
   int x = 14;
   cout<<"Count of subtrees that sum up to a given value x are: "<<subtrees_x(root, x);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of subtrees that sum up to a given value x are: 1