हमें 'n' नोड्स की संख्या के साथ एक ट्री डेटा संरचना दी गई है। दिए गए पेड़ में एक रूट नोड और संबंधित बच्चे होंगे जो कि कोई भी संख्या हो सकती है और आगे के बच्चे के कितने भी बच्चे हो सकते हैं। कार्य एक पेड़ के सभी नोड्स को जानकारी पास करने के लिए एक पेड़ के रूट नोड द्वारा आवश्यक पुनरावृत्तियों की न्यूनतम संख्या को खोजना है। एक समय में, एक नोड अपने बच्चों में से किसी एक को जानकारी पास कर सकता है और आगे उसके बच्चों में से एक अपने बच्चों में से एक को जानकारी पास कर सकता है और इस बीच रूट नोड दूसरे बच्चे को जानकारी पास कर सकता है।
आइए इसके लिए विभिन्न इनपुट आउटपुट परिदृश्य देखें -
इन −
बाहर − न्यूनतम संख्या ट्री में सभी नोड्स को सूचना पास करने के लिए पुनरावृत्तियों की संख्या हैं:5
स्पष्टीकरण - हमें रूट और अन्य सभी नोड्स सहित कुल 11 नोड्स वाला एक पेड़ दिया गया है। किसी दिए गए पेड़ का रूट नोड 0 है जो पहले डेटा को नोड 1 में पास करेगा क्योंकि इसमें कई बच्चे हैं फिर अन्य नोड्स हैं, फिर रूट नोड डेटा को नोड 4 में पास करेगा, फिर यह डेटा को 3 पास करेगा, फिर यह पास होगा डेटा को 6 तक और अंत में यह 2 को डेटा पास कर देगा। इसलिए, कुल मिलाकर आवश्यक पुनरावृत्तियों 5 हैं।
इन −
बाहर − न्यूनतम संख्या ट्री में सभी नोड्स को सूचना पास करने के लिए पुनरावृत्तियों की संख्या हैं:1
स्पष्टीकरण - :हमें एक पेड़ दिया जाता है जिसमें रूट और अन्य सभी नोड्स सहित कुल 2 नोड होते हैं। चूंकि किसी दिए गए पेड़ में रूट नोड का केवल एक बच्चा होता है, इसलिए आवश्यक पुनरावृत्तियों की न्यूनतम संख्या 1 होगी।
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है -
-
पेड़ बनाने के लिए एक वर्ग बनाएं और उसके डेटा सदस्य के रूप में नोड्स जोड़ें और List_children के रूप में एक सूची सूचक बनाएं और एक निजी विधि को शून्य पुनरावृत्ति (int vertices, int arr []) के रूप में घोषित करें। एक पैरामीटरयुक्त कंस्ट्रक्टर को ट्री (इंट नोड्स), शून्य इन्सर्ट_नोड (इंट ए, इंट बी), इंट मिन_इटरेशन () और स्टेटिक इंट चेक (कॉन्स्ट शून्य * ए_1, कॉन्स्ट शून्य * बी_1) के रूप में घोषित करें।
-
बाहरी पैरामीटरयुक्त कंस्ट्रक्टर को ट्री ::ट्री (इंट नोड्स) के रूप में कॉल करें
-
इसे सेट करें->नोड्स को नोड्स में।
-
List_children को नई सूची में सेट करें [नोड्स]
-
-
एक वर्ग विधि को शून्य वृक्ष के रूप में कॉल करें ::insert_node (int a, int b)
-
List_children[a] को push_back(b) पर सेट करें
-
-
एक वर्ग विधि को शून्य वृक्ष के रूप में कॉल करें ::Iteration(int vertices, int arr[])
-
गिरफ्तारी [कोने] को List_children[vertices] पर सेट करें। आकार ()
-
*ptr को नए int[arr[vertices]]
. पर सेट करें -
अस्थायी को 0 और temp_2 को 0 पर सेट करें
-
एक पुनरावर्तक को सूची के रूप में घोषित करें ::इसे पुनरावृत्त करें
-
इसके लिए लूप शुरू करें List_children[vertices].begin() तक जब तक कि यह List_children[vertices].end() के बराबर न हो जाए और इसे पहले से बढ़ा दें। लूप के अंदर Iteration(*it, arr) सेट करें और ptr[temp++] को arr[*it]
पर सेट करें -
क्विक सॉर्ट के लिए qsort(ptr, arr[vertices], sizeof(int), check) पर कॉल करें
-
अस्थायी रूप से 0 के लिए लूप प्रारंभ करें और List_children[vertices] से कम अस्थायी। आकार() और वेतन वृद्धि अस्थायी पोस्ट करें। लूप के अंदर, temp_2 को ptr[temp] + temp + 1 और arr[vertices] से max(arr[vertices], temp_2) पर सेट करें और हटाएं [] ptr
-
-
एक वर्ग विधि को int Tree::Min_Iteration()
. के रूप में कॉल करें-
एक पॉइंटर को int *ptr =new int[nodes]
. के रूप में घोषित करें -
एक चर को int temp =-1 के रूप में घोषित करें
-
i से 0 तक i <नोड्स और i++ तक लूप प्रारंभ करें। लूप के अंदर, ptr[i] को 0
. पर सेट करें -
Iteration(0, ptr) को कॉल करें और अस्थायी को ptr[0] पर सेट करें और हटाएं [] ptr
-
वापसी अस्थायी
-
-
एक वर्ग विधि को int Tree::check(const void * a_1, const void * b_1)
के रूप में कॉल करें-
एक चर को int परिणाम के रूप में घोषित करें ( *(int*)b_1 - *(int*)a_1 )
-
वापसी परिणाम
-
-
मुख्य () फ़ंक्शन में
-
एक पैरामीटरयुक्त कंस्ट्रक्टर का उपयोग करके एक ट्री ऑब्जेक्ट बनाएं।
-
फिर ट्री क्लास के ऑब्जेक्ट का उपयोग करके ट्री में नोड डेटा डालने के लिए insert_node () विधि को कॉल करें
-
ट्री में सभी नोड्स को जानकारी पास करने के लिए न्यूनतम संख्या में पुनरावृत्तियों की गणना करने के लिए Min_Iteration() विधि को कॉल करें
-
उदाहरण
#include<bits/stdc++.h>
using namespace std;
class Tree
{
int nodes;
list<int> *List_children;
void Iteration(int vertices, int arr[]);
public:
//constructor of a class
Tree(int nodes);
//method to insert a node in a tree
void insert_node(int a, int b);
//method to calculate the minimum iterations
int Min_Iteration();
static int check(const void *a_1, const void *b_1);
};
Tree::Tree(int nodes)
{
this->nodes = nodes;
List_children = new list<int>[nodes];
}
void Tree::insert_node(int a, int b)
{
List_children[a].push_back(b);
}
void Tree::Iteration(int vertices, int arr[])
{
arr[vertices] = List_children[vertices].size();
int *ptr = new int[arr[vertices]];
int temp = 0;
int temp_2 = 0;
list<int>::iterator it;
for(it = List_children[vertices].begin(); it!= List_children[vertices].end(); ++it)
{
Iteration(*it, arr);
ptr[temp++] = arr[*it];
}
qsort(ptr, arr[vertices], sizeof(int), check);
for(temp = 0; temp < List_children[vertices].size(); temp++)
{
temp_2 = ptr[temp] + temp + 1;
arr[vertices] = max(arr[vertices], temp_2);
}
delete[] ptr;
}
int Tree::Min_Iteration()
{
int *ptr = new int[nodes];
int temp = -1;
for (int i = 0; i < nodes; i++)
{
ptr[i] = 0;
}
Iteration(0, ptr);
temp = ptr[0];
delete[] ptr;
return temp;
}
int Tree::check(const void * a_1, const void * b_1)
{
}
int main()
{
Tree T_1(8);
T_1.insert_node(0, 1);
T_1.insert_node(0, 3);
T_1.insert_node(0, 4);
T_1.insert_node(0, 6);
T_1.insert_node(0, 2);
T_1.insert_node(1, 7);
T_1.insert_node(1, 2);
T_1.insert_node(1, 3);
T_1.insert_node(4, 6);
T_1.insert_node(4, 7);
cout<<"Minimum no. of iterations to pass information to all nodes in the tree are:"<<T_1.Min_Iteration();
Tree T_2(2);
T_2.insert_node(0, 1);
cout<<"\nMinimum no. of iterations to pass information to all nodes in the tree are:" <<T_1.Min_Iteration();
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा
Minimum no. of iterations to pass information to all nodes in the tree are: 8 Minimum no. of iterations to pass information to all nodes in the tree are: 8