Đếm các nút trong cây đã cho có trọng số là lũy thừa của hai trong C ++

Cho một cây nhị phân với trọng số là các nút của nó. Mục đích là tìm số nút có trọng số sao cho số đó là lũy thừa của hai nút. Nếu trọng số là 32 thì nó là 25 nên nút này sẽ được tính.

Ví dụ

Đầu vào

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

Đầu ra

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

Giải thích

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.

Đầu vào

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

Đầu ra

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

Giải thích

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.

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ẽ áp dụng DFS trên biểu đồ của cây để duyệt qua nó và kiểm tra xem trọng lượng của các nút có phải là lũy thừa của 2. Lấy hai vectơ Node_Weight (100) và edge_graph [100] cho mục đích này hay không.

• Khởi tạo Node_Weight [] với trọng số của các nút.

• Tạo cây bằng cách sử dụng vector edge_graph.

• Lấy một tổng biến toàn cục và khởi tạo nó bằng 0.

• Hàm power_two (int node, int root) lấy một nút và nút gốc của cây và trả về số lượng các nút trong cây đã cho có trọng số là lũy thừa của hai.

• Lấy set =Node_Weight [node];

• Nếu set &&(! (Set &(set - 1))) trả về true thì nó là lũy thừa của hai (bitwise AND và sau đó là phủ định)

• Quyền hạn tăng dần theo tập hợp có giá trị là lũy thừa của 2.

• Cây ngang trong vector edge_graph [node] sử dụng vòng lặp for.

• Gọi power_two (nó, nút) cho nút tiếp theo trong vectơ.

• Ở cuối tất cả các hàm, chúng ta sẽ có lũy thừa là số nút có trọng số có giá trị là lũy thừa của hai.

Ví dụ

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

Đầu ra

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

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