資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C #
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚學
法學在 C++ 中將樹轉換成偶數節點林
在本文中，我們將討論一個將樹轉換成偶數節點林的程式。
為此，我們提供一棵 N 個節點的二叉樹。我們的任務是計算可以移出以獲取偶數節點林的最大邊數。
範例
#include<bits/stdc++.h>
#define N 12
using namespace std;
//returning the number of nodes of subtree
//having the root node
int depth_search(vector<int> tree[N], int visit[N], int *ans, int node){
int num = 0, temp = 0;
//marking nodes as visited
visit[node] = 1;
for (int i = 0; i < tree[node].size(); i++){
if (visit[tree[node][i]] == 0){
//finding total nodes of the sub subtree
temp = depth_search(tree, visit, ans, tree[node][i]);
//if nodes are even, increment the edges to be removed by 1
(temp%2)?(num += temp):((*ans)++);
}
}
return num+1;
}
//returning the maximum number of edges to be removed
int print_maxedge(vector<int> tree[N], int n){
int visit[n+2];
int ans = 0;
memset(visit, 0, sizeof visit);
depth_search(tree, visit, &ans, 1);
return ans;
}
int main(){
int n = 10;
vector<int> tree[n+2];
tree[1].push_back(3);
tree[3].push_back(1);
tree[1].push_back(6);
tree[6].push_back(1);
tree[1].push_back(2);
tree[2].push_back(1);
tree[3].push_back(4);
tree[4].push_back(3);
tree[6].push_back(8);
tree[8].push_back(6);
tree[2].push_back(7);
tree[7].push_back(2);
tree[2].push_back(5);
tree[5].push_back(2);
tree[4].push_back(9);
tree[9].push_back(4);
tree[4].push_back(10);
tree[10].push_back(4);
cout << print_maxedge(tree, n) << endl;
return 0;
}輸出
2
更新時間：06-Jan-2020
179 瀏覽量
廣告