Đếm các nút trong cây đã cho có tổng các chữ số có trọng số là lẻ 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 tổng các chữ số trong các trọng số đó cộng lại thành một số lẻ. Nếu trọng số là 12 thì tổng chữ số là 3 là số lẻ 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 of nodes in the given tree whose sum of digits of weight is odd are: 2

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.

Đầ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 of nodes in the given tree whose sum of digits of weight is odd are: 4

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 đồ thị của cây để duyệt qua nó và kiểm tra tổng các chữ số của mỗi nút, nếu nó là số lẻ. Lấy hai vectorsNode_Weight (100) và edge_graph [100] cho mục đích này.

• 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 tổng biến toàn cục và khởi tạo nó bằng 0.

• Hàm sum_total (kiểm tra int) nhận một số nguyên và trả về tổng các chữ số của nó.

• Lấy tổng ban đầu là tổng =0.

• Sử dụng vòng lặp while tính toán các chữ số tận cùng bên phải dưới dạng kiểm tra% 10 và cộng nó vào tổng. Giảm kiểm tra đi 10.

• Tổng trả lại dưới dạng tổng các chữ số của séc.

• Hàm retail_weight (int node, int root) lấy một nút và nút gốc của một cây và trả về số lượng các nút trong cây đã cho có tổng các chữ số của trọng số là lẻ.

• Tính tổng =sum_total (Node_Weight [node]) dưới dạng tổng trọng lượng của nút.

• Nếu tổng% 2 ==1 của nó là số lẻ thì tổng tăng dần.

• Nếu tổng% 2 ==1 của nó là số lẻ thì tổng tăng dần.

• Gọi lẻ_weight (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ó tổng là số nút với tổng trọng số của các chữ số là số lẻ.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
vector<int> Node_Weight(100);
vector<int> edge_graph[100];
int sum = 0;
int sum_total(int check){
   int total = 0;
   while(check){
      total += check % 10;
      check = check / 10;
   }
   return total;
}
void odd_weight(int node, int root){
   int total = sum_total(Node_Weight[node]);
   if (total % 2 == 1){
      sum++;
   }
   for (int it : edge_graph[node]){
      if(it == root){
         continue;
      }
      odd_weight(it, node);
   }
}
int main(){
   //weight of the nodes
   Node_Weight[2] = 23;
   Node_Weight[1] = 141;
   Node_Weight[4] = 211;
   Node_Weight[3] = 115;
   Node_Weight[8] = 7171;
   Node_Weight[9] = 701;
   //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);
   odd_weight(2, 2);
   cout<<"Count the nodes in the given tree whose sum of digits of weight is odd are: "<<sum;
   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 sum of digits of weight is odd are: 2