数据结构
网络
关系数据库管理系统
操作系统
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 次查看
广告