C++ में N-Ary ट्री की गहराई (Depth of N-Ary Tree)

आइए पहले उस स्ट्रक्ट को परिभाषित करें जो एक ट्री नोड को दर्शाता है जिसमें एक कैरेक्टर key और Node * का वेक्टर होता है।

struct Node{ 
    char key; 
    vector<Node *> children; 
};

इसके बाद हम createNode(int key) फंक्शन बनाते हैं जो एक int key मान लेता है और इसे नोड के key सदस्य को असाइन करता है। फंक्शन बने हुए स्ट्रक्ट नोड का पॉइंटर वापस करता है।

Node *createNode(int key){ 
    Node *node = new Node; 
    node->key = key; 
    return node; 
}

हमारा depthOfTree(struct Node* root) फंक्शन रूट नोड को पैरामीटर के रूप में लेता है। यदि रूट NULL है तो गहराई 0 वापस की जाती है।

int depthOfTree(struct Node *root){ 
    if (root==NULL) 
        return 0;

हम फिर maxDepth वेरिएबल को परिभाषित करते हैं और इसका मान 0 असाइन करते हैं। हम फिर ट्री के सभी चाइल्ड पर पुनरावृति करते हैं और प्रत्येक रिकर्सन पर maxDepth बढ़ाते हैं। एक बार आधार स्थिति पूरी हो जाने और रिकर्सन समाप्त हो जाने पर हम फिर maxDepth वापस करते हैं।

int depthOfTree(struct Node *root){ 
    if (root==NULL) 
        return 0; 
    int maxDepth = 0; 
    for(auto i: root->children){ 
        maxDepth = depthOfTree(i) + 1; 
    } 
    return maxDepth; 
}

उदाहरण

N-Ary ट्री की गहराई खोजने के लिए निम्नलिखित कार्यान्वयन देखें:

#include <iostream> 
#include <vector> 
using namespace std; 

struct Node{ 
    char key; 
    vector<Node *> children; 
}; 

Node *createNode(int key){ 
    Node *node = new Node; 
    node->key = key; 
    return node; 
} 

int depthOfTree(struct Node *root){ 
    if (root==NULL) 
        return 0; 
    int maxDepth = 0; 
    for(auto i: root->children){ 
        maxDepth = depthOfTree(i) + 1; 
    } 
    return maxDepth; 
} 

int main(){ 
    Node *root = createNode('S'); 
    (root->children).push_back(createNode('O')); 
    (root->children).push_back(createNode('A')); 
    (root->children).push_back(createNode('D')); 
    (root->children).push_back(createNode('N')); 
    (root->children[0]->children).push_back(createNode('L')); 
    (root->children[0]->children).push_back(createNode('I')); 
    (root->children[2]->children).push_back(createNode('R')); 
    (root->children[3]->children).push_back(createNode('C')); 
    (root->children[3]->children).push_back(createNode('H')); 
    (root->children[3]->children).push_back(createNode('I')); 
    cout << "The depth of the n-ary tree is " << depthOfTree(root) << endl; 
    return 0; 
}

आउटपुट

उपरोक्त कोड निम्नलिखित आउटपुट देगा:

The depth of the n-ary tree is 2