Chuyển đổi một cây thành rừng các nút chẵn trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình chuyển đổi một cây thành một rừng các nút chẵn.

Đối với điều này, chúng ta sẽ được cung cấp một cây nhị phân gồm N nút nói trên. Nhiệm vụ của chúng tôi là tính toán số cạnh tối đa có thể bị loại bỏ để có được rừng các nút chẵn.

Ví dụ

#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;
}

Đầu ra

2