資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用 C++ 統計給定樹中權重為 2 的冪的節點數
給定一棵二叉樹，其中包含其節點的權重。目標是找到權重為 2 的冪的節點數。如果權重為 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.
| 節點 | 權重 | 權重^2 | 2 的冪 |
|---|---|---|---|
| 2 | 8 | 2*2*2 | 否 |
| 1 | 100 | 10*2 | 是 |
| 4 | 211 | 質數 | 否 |
| 3 | 16 | 4^2 | 是 |
| 8 | 1717 | 不可能 | 否 |
| 9 | 32 | 2*2*2*2*2 | 是 |
輸入
輸入值後建立的樹如下所示：
輸出
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.
| 節點 | 權重 | 權重 ^ 2 | 2 的冪 |
|---|---|---|---|
| 2 | 16 | 4^2 | 是 |
| 1 | 141 | 不可能 | 否 |
| 4 | 41 | 質數 | 否 |
| 3 | 64 | 8^2 | 是 |
| 8 | 81 | 9^2 | 是 |
下面程式中使用的方案如下：
在這種方法中，我們將對樹的圖形應用 DFS 來遍歷它並檢查節點的權重是否為 2 的冪。為此，請使用兩個向量 Node_Weight(100) 和 edge_graph[100]。
使用節點的權重初始化 Node_Weight[]。
使用向量 edge_graph 建立樹。
取一個全域性變數 sum 並將其初始化為 0。
函式 power_two(int node, int root) 獲取樹的節點和根節點，並返回給定樹中權重為 2 的冪的節點數。
取 set = Node_Weight[node];
如果 set && (!(set & (set − 1))) 返回 true，則它是 2 的冪（按位與然後取反）
由於 set 有一個值為 2 的冪的值，因此遞增 powers。
使用 for 迴圈遍歷向量 edge_graph[node] 中的樹。
為向量中的下一個節點呼叫 power_two(it, node)。
在所有函式結束時，我們將 power 作為具有值為 2 的冪的權重的節點數。
示例
#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
更新於： 2021 年 1 月 5 日
193 次檢視
廣告