นับต้นไม้ย่อยที่รวมค่าที่กำหนด x ใน C++

กำหนดไบนารีทรีและค่า 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) นำตัวชี้รูทไปที่ tree 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) สำหรับผลรวมของโหนดในทรีย่อยด้านซ้าย

• Set sum=Left_subtree + Right_subtree + root−>ldata.

• หากผลรวมเท่ากับ x ก็นับการเพิ่มขึ้น

• หาก temp!=root ไม่ใช่โหนดเริ่มต้น ให้คืนค่า sum เป็น 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