資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學用 C++ 統計給定樹中權重各位數字之和為奇數的節點數
給定一棵二叉樹及其節點權重。目標是找到權重各位數字之和為奇數的節點個數。如果權重為 12，則各位數字之和為 3，這是一個奇數，因此將統計此節點。
例如
輸入
輸入值建立的樹如下所示：
輸出
Count of nodes in the given tree whose sum of digits of weight is odd are: 2
解釋
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 | 23 | 2+3=5 | 是 |
| 1 | 141 | 1+4+1=6 | 否 |
| 4 | 211 | 2+1+1=4 | 否 |
| 3 | 133 | 1+1+3=5 | 是 |
| 8 | 7171 | 7+1+7+1=16 | 否 |
| 9 | 101 | 7+0+1=8 | 否 |
輸入
輸入值建立的樹如下所示：
輸出
Count of nodes in the given tree whose sum of digits of weight is odd are: 4
解釋
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 | 5 | 5 | 是 |
| 1 | 141 | 1+4+1=6 | 否 |
| 4 | 41 | 4+1=4 | 是 |
| 3 | 322 | 3+2+2=7 | 是 |
| 8 | 717 | 7+1+7=15 | 是 |
**以下程式中使用的方案如下：**
在此方案中，我們將對樹的圖應用深度優先搜尋 (DFS) 來遍歷它並檢查每個節點權重的各位數字之和是否為奇數。為此，我們將使用兩個向量 Node_Weight(100) 和 edge_graph[100]。
用節點權重初始化 Node_Weight[]。
使用向量 edge_graph 建立一棵樹。
使用一個全域性變數 sum 並將其初始化為 0。
函式 sum_total(int check) 接收一個整數並返回其各位數字之和。
將初始總和設為 total=0。
使用 while 迴圈計算最右邊的數字為 check % 10 並將其新增到 total 中。將 check 減少 10。
返回 total 作為 check 的各位數字之和。
函式 odd_weight(int node, int root) 接收樹的節點和根節點，並返回給定樹中權重各位數字之和為奇數的節點個數。
計算 total = sum_total(Node_Weight[node]) 作為節點權重之和。
如果 total%2==1 為奇數，則遞增 sum。
如果 total%2==1 為奇數，則遞增 sum。
對向量中的下一個節點呼叫 odd_weight(it, node)。
在所有函式結束時，sum 將是權重各位數字之和為奇數的節點數。
示例
#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;
}輸出
如果我們執行上述程式碼，它將生成以下輸出：
Count the nodes in the given tree whose sum of digits of weight is odd are: 2
更新於：2021年1月5日
190 次瀏覽
廣告