सी ++ में एन-आरी पेड़ में भी आकार उपट्री

इस समस्या में, हमें एक आसन्न सूची दी गई है जो एक n-ary पेड़ को दर्शाती है। हमारा कार्य n-ary ट्री में सम आकार के सबट्री की संख्या ज्ञात करना है।

एन-आरी ट्री को नोड्स के एक संग्रह के रूप में परिभाषित किया जाता है जिसे सामान्य रूप से निम्न तरीके से पदानुक्रम में दर्शाया जाता है।

पेड़ को रूट नोड पर प्रारंभ किया गया है।

पेड़ का प्रत्येक नोड अपने चाइल्ड नोड्स के लिए पॉइंटर्स की एक सूची रखता है।

चाइल्ड नोड्स की संख्या मी से कम या उसके बराबर है।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट:

<मजबूत>

आउटपुट: 4

स्पष्टीकरण:

7 के साथ जड़ वाले पेड़ का आकार समान होता है।
2 के साथ जड़ वाले पेड़ का आकार समान होता है।
0 के साथ जड़ वाले पेड़ का आकार समान होता है।
3 जड़ वाले पेड़ का आकार समान होता है।

समाधान दृष्टिकोण -

किसी दिए गए नोड के लिए सभी चाइल्ड नोड्स को गिनने का एक सरल तरीका है, अगर यह इवनट्रीकाउंट को भी बढ़ाता है। इसके लिए हम DFS का उपयोग करेंगे, और दिए गए नोड के लिए SubTree की लंबाई ज्ञात करेंगे।

हम पेड़ पर एक ट्रैवर्सल का उपयोग करके ऐसा कर सकते हैं। प्रत्येक बच्चे के नोड के सबट्री के आकार को दोबारा ढूंढकर और फिर आकार की जांच करें और यदि यह भी है, तो भी ट्रीकाउंट बढ़ाएं अन्यथा इसे छोड़ दें।

हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,

उदाहरण

#include <bits/stdc++.h>
using namespace std;

int countEventSizeSubTree(vector<int> adj[], int n, int v, int&amp; EvenCount){

   int size = 1;
   for (auto ele : adj[v]) {
      size += countEventSizeSubTree(adj, n, ele, EvenCount);
   }
   if (size % 2 == 0)
      EvenCount++;
   return size;
}

int main(){

   int n;
   n = 10;

   vector<int> adj[n + 1];
   adj[7].push_back(2);
   adj[7].push_back(9);
   adj[2].push_back(0);
   adj[2].push_back(1);
   adj[9].push_back(3);
   adj[3].push_back(8);
   adj[0].push_back(5);

   int EvenCount = 0;
   countEventSizeSubTree(adj, n, 1, EvenCount);
   cout<<"Even Size SubTree are "<<EvenCount;
   return 0;
}

आउटपुट -

Even Size SubTree are 0