Đếm số cây con có tổng đến một giá trị x cho trước trong C ++

Cho một cây nhị phân và một giá trị x làm đầu vào. Mục đích là tìm tất cả các cây con của cây nhị phân có tổng trọng số của các nút bằng x.

Ví dụ

Đầu vào

x =14. Cây sẽ được tạo sau khi nhập các giá trị được đưa ra bên dưới

Đầu ra

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

Giải thích

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.

Đầu vào

x =33. Cây sẽ được tạo sau khi nhập các giá trị được đưa ra bên dưới -

Đầu ra

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

Giải thích

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.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -

Trong cách tiếp cận này, chúng tôi sẽ tính toán đệ quy tổng trọng số của cây con bên trái và cây con bên phải của nút gốc và cuối cùng, chúng tôi sẽ cộng nó vào trọng số của nút gốc. Nếu tổng bằng x thì số gia tăng.

• Xây dựng một cây Tree_Node với root là một con trỏ đến gốc của nó.

• Hàm insert_Node (int data) thêm các nút vào cây này.

• Hàm subtrees_x (Tree_Node * root, int x) đưa con trỏ gốc tới cây andx và trả về số lượng các cây con có tổng giá trị x cho trước.

• Lấy số lượng biến tĩnh là 0 vì chúng tôi sẽ tính toán số lượng một cách đệ quy.

• Lấy một nút tĩnh thuộc loại Tree_node làm gốc.

• Khởi tạo các biến Left_subtree =0, Right_subtree =0. Đối với tổng trọng số của nút trong cây con trái và phải từ gốc.

• Nếu gốc là NULL, trả về tổng bằng 0.

• Tính Left_subtree + =subtrees_x (root−> Left, x) cho tổng các nút trong cây con bên trái.

• Tính Right_subtree + =subtrees_x (root−> Right, x) cho tổng các nút trong cây con bên trái.

• Đặt sum =Left_subtree + Right_subtree + root−> ldata.

• Nếu tổng bằng x thì số gia tăng.

• Nếu temp! =Root, không phải là nút bắt đầu, thì trả về tổng là Left_subtree + root−> data + Right_subtree.

• Cuối cùng, kết quả trả về là số lượng cây mong muốn với tổng của nút bằng x.

Ví dụ

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

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