সি++-এ N-এরি ট্রির গভীরতা

প্রথমে স্ট্রাক্ট ডিফাইন করি যা ট্রি নোড রিপ্রেজেন্ট করবে যাতে একটি ক্যারেক্টার key এবং Node * এর একটি ভেক্টর থাকে।

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

পরবর্তীতে createNode(int key) ফাংশন তৈরি করি যা একটি int key মান নেয় এবং সেটি নোডের key মেম্বরে অ্যাসাইন করে। ফাংশনটি তৈরি হওয়া struct node-এর পয়েন্টার ফেরত দেয়।

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

আমাদের depthOfTree(struct Node* root) ফাংশন রুট নোড প্যারামিটার হিসেবে নেয়। যদি রুট NULL হয় তবে ডেপথ ০ ফেরত দেয়।

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

তারপর maxDepth ভেরিয়েবল ডিক্লেয়ার করি এবং এর মান ০ অ্যাসাইন করি। তারপর ট্রির সব চাইল্ডের ওপর ইটারেট করি এবং প্রতিটি রিকার্শনে 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-এরি ট্রির ডেপথ বের করার ইমপ্লিমেন্টেশন:

#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