C++ में ट्री में सभी नोड्स तक जानकारी पास करने के लिए न्यूनतम पुनरावृत्तियों की संख्या

हमें 'n' संख्या में नोड्स के साथ एक ट्री डेटा संरचना दी गई है। दिया गया ट्री एक रूट नोड और संबंधित चाइल्ड्स होगा जो किसी भी संख्या में हो सकते हैं और आगे चाइल्ड के किसी भी संख्या में चाइल्ड हो सकते हैं। कार्य ट्री के रूट नोड द्वारा ट्री में सभी नोड्स तक जानकारी पास करने के लिए आवश्यक न्यूनतम पुनरावृत्तियों की संख्या ढूंढना है। एक समय में, एक नोड अपने एक चाइल्ड को जानकारी पास कर सकता है और आगे उसका एक चाइल्ड अपने एक चाइल्ड को जानकारी पास कर सकता है और इस बीच रूट नोड दूसरे चाइल्ड को जानकारी पास कर सकता है।

विभिन्न इनपुट-आउटपुट परिदृश्य देखते हैं:

इनपुट:

आउटपुट: ट्री में सभी नोड्स तक जानकारी पास करने के लिए न्यूनतम पुनरावृत्तियों की संख्या: 5

व्याख्या: हमें रूट और अन्य सभी नोड्स सहित कुल 11 नोड्स वाला एक ट्री दिया गया है। दिए गए ट्री का रूट नोड 0 है जो पहले नोड 1 को डेटा पास करेगा क्योंकि इसके कई चाइल्ड्स हैं फिर अन्य नोड्स, फिर रूट नोड नोड 4 को डेटा पास करेगा, फिर यह 3 को पास करेगा, फिर 6 को पास करेगा और अंत में 2 को पास करेगा। तो, कुल मिलाकर आवश्यक पुनरावृत्तियां 5 हैं।

इनपुट:

आउटपुट: ट्री में सभी नोड्स तक जानकारी पास करने के लिए न्यूनतम पुनरावृत्तियों की संख्या: 1

व्याख्या: हमें रूट और अन्य सभी नोड्स सहित कुल 2 नोड्स वाला एक ट्री दिया गया है। चूंकि दिए गए ट्री में रूट नोड का केवल एक चाइल्ड है इसलिए आवश्यक न्यूनतम पुनरावृत्तियों की संख्या 1 होगी।

नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण:

• ट्री बनाने के लिए एक क्लास बनाएं और नोड्स को इसके डेटा मेंबर के रूप में जोड़ें और List_children के रूप में एक लिस्ट पॉइंटर घोषित करें और एक प्राइवेट मेथड void Iteration(int vertices, int arr[]) घोषित करें। एक पैरामीट्राइज्ड कंस्ट्रक्टर Tree(int nodes), void insert_node(int a, int b), 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[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() पर सेट करें।
  • *ptr को new int[arr[vertices]] पर सेट करें।
  • temp को 0 और temp_2 को 0 पर सेट करें।
  • it के रूप में एक इटरेटर घोषित करें।
  • it को List_children[vertices].begin() से List_children[vertices].end() तक प्री-इंक्रीमेंट करते हुए लूप चलाएं। अंदर Iteration(*it, arr) सेट करें और ptr[temp++] को arr[*it] पर सेट करें।
  • क्विक सॉर्ट के लिए qsort(ptr, arr[vertices], sizeof(int), check) कॉल करें।
  • temp को 0 से List_children[vertices].size() से कम तक पोस्ट-इंक्रीमेंट करते हुए लूप चलाएं। अंदर, 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 वेरिएबल घोषित करें।
  • i को 0 से nodes से कम तक i++ के साथ लूप चलाएं। अंदर, ptr[i] को 0 पर सेट करें।
  • Iteration(0, ptr) कॉल करें और temp को ptr[0] पर सेट करें और delete[] ptr करें।
  • temp लौटाएं।
• क्लास मेथड int Tree::check(const void * a_1, const void * b_1) कॉल करें:
  • result को ( *(int*)b_1 - *(int*)a_1 ) के रूप में घोषित करें।
  • result लौटाएं।
• main() फंक्शन में:
  • पैरामीट्राइज्ड कंस्ट्रक्टर का उपयोग करके एक ट्री ऑब्जेक्ट बनाएं।
  • ट्री क्लास के ऑब्जेक्ट का उपयोग करके 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:
    // क्लास का कंस्ट्रक्टर
    Tree(int nodes);
    // ट्री में नोड डालने की विधि
    void insert_node(int a, int b);
    // न्यूनतम पुनरावृत्तियों की गणना करने की विधि
    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) {
    return (*(int*)b_1 - *(int*)a_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_2.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: 1