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로 합산되는 하위 트리의 수를 반환합니다.

• 재귀적으로 count를 계산하므로 정적 변수 count를 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