นับโหนดในทรีที่กำหนดซึ่งมีน้ำหนักเป็นกำลังสองใน C++

กำหนดไบนารีทรีที่มีน้ำหนักของโหนด เป้าหมายคือการหาจำนวนโหนดที่มีน้ำหนักเพื่อให้ตัวเลขเป็นกำลังสอง หากน้ำหนักเท่ากับ 32 แสดงว่าเป็น 25 ดังนั้นโหนดนี้จะถูกนับ

ตัวอย่าง

อินพุต

ต้นไม้ที่จะถูกสร้างขึ้นหลังจากป้อนค่าจะได้รับด้านล่าง -

ผลลัพธ์

Count the nodes in the given tree whose weight is a power of two are: 3

คำอธิบาย

we are given with the tree node and the weights associated with each
node. Now we calculate the power of each and every weight and check whether it can
be expressed as power of 2 or not.

อินพุต

ต้นไม้ที่จะถูกสร้างขึ้นหลังจากป้อนค่าจะได้รับด้านล่าง -

ผลลัพธ์

Count the nodes in the given tree whose weight is a power of two are: 3

คำอธิบาย

we are given with the tree node and the weights associated with each
node. Now we calculate the digit sum of each and every weight and check whether it's
odd or not.

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −

ในแนวทางนี้ เราจะใช้ DFS กับกราฟของต้นไม้เพื่อข้ามผ่าน และตรวจสอบว่าน้ำหนักของโหนดเป็นกำลัง 2 หรือไม่ ใช้เวกเตอร์สองตัว Node_Weight(100) และ edge_graph[100] เพื่อจุดประสงค์นี้

• เริ่มต้น Node_Weight[] ด้วยน้ำหนักของโหนด

• สร้างต้นไม้โดยใช้ vector edge_graph

• หาผลรวมของตัวแปรโกลบอลและเริ่มต้นด้วย 0

• ฟังก์ชัน power_two(int node, int root) รับโหนดและโหนดรูทของทรีและคืนค่าจำนวนโหนดในทรีที่กำหนดซึ่งมีน้ำหนักเป็นกำลังสอง

• Take set =Node_Weight[โหนด];

• หาก set &&(!(set &(set − 1))) คืนค่าเป็น true แสดงว่ากำลังสอง (ระดับบิต AND และค่าลบ)

• พลังที่เพิ่มขึ้นตามที่ตั้งค่าไว้มีค่าเท่ากับ 2

• ต้นไม้ขวางใน vector edge_graph[node] ใช้สำหรับวนซ้ำ

• เรียก power_two(it, node) สำหรับโหนดถัดไปในเวกเตอร์

• ในตอนท้ายของฟังก์ชันทั้งหมด เราจะมีกำลังเท่ากับจำนวนโหนดที่มีน้ำหนักมีค่าเท่ากับกำลังสอง

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
vector<int> Node_Weight(100);
vector<int> edge_graph[100];
int powers = 0;
void power_two(int node, int root){
   int set = Node_Weight[node];
   if(set && (!(set & (set − 1)))){
      powers++;
   }
   for(int it : edge_graph[node]){
      if(it == root){
         continue;
      }
      power_two(it, node);
   }
}
int main(){
   //weight of the nodes
   Node_Weight[2] = 8;
   Node_Weight[1] = 100;
   Node_Weight[4] = 211;
   Node_Weight[3] = 16;
   Node_Weight[8] = 7171;
   Node_Weight[9] = 32;
   //create graph edge
   edge_graph[2].push_back(1);
   edge_graph[2].push_back(4);
   edge_graph[4].push_back(3);
   edge_graph[4].push_back(8);
   edge_graph[8].push_back(9);
   power_two(2, 2);
   cout<<"Count the nodes in the given tree whose weight is a power of two are: "<<powers;
   return 0;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Count the nodes in the given tree whose weight is a power of two are: 3