বাইনারি ট্রিতে স্বরবর্ণ বিশিষ্ট স্ট্রিং ওজন সম্পন্ন নোড গণনা C++-এ

একটি বাইনারি ট্রি দেওয়া আছে যার নোডগুলোর ওজন স্ট্রিং হিসেবে আছে। লক্ষ্য হলো সেই নোডগুলোর সংখ্যা বের করা যাদের ওজন স্ট্রিং-এ স্বরবর্ণ (vowel) থাকে। যদি ওজন 'aer' হয় তবে এতে 'a' এবং 'e' স্বরবর্ণ আছে, সুতরাং নোডটি গণনা হবে।

ইনপুট

ইনপুট ভ্যালুগুলো থেকে যে ট্রি তৈরি হবে वो নিচে দেওয়া আছে:

আউটপুট

Count the nodes of the tree whose weighted string contains a vowel are: 5

ব্যাখ্যা

আমাদের ট্রি নোডগুলো এবং প্রতিটি নোডের সাথে যুক্ত স্ট্রিং ওজন দেওয়া আছে। এখন চেক করা হচ্ছে নোডগুলোর স্ট্রিং-এ স্বরবর্ণ আছে কিনা।

ইনপুট

ইনপুট ভ্যালুগুলো থেকে যে ট্রি তৈরি হবে वो নিচে দেওয়া আছে:

আউটপুট

Count the nodes of the tree whose weighted string contains a vowel are: 3

ব্যাখ্যা

ট্রি নোডগুলো এবং প্রতিটি নোডের সাথে যুক্ত স্ট্রিং ওজন দেওয়া আছে। এখন চেক করা হচ্ছে নোডগুলোর স্ট্রিং-এ স্বরবর্ণ আছে কিনা।

প্রোগ্রামে ব্যবহৃত পদ্ধতি:

এই পদ্ধতিতে আমরা ট্রির গ্রাফে DFS অ্যাপ্লাই করি ট্রভারস করতে এবং চেক করি নোডের ওজন স্ট্রিং-এ স্বরবর্ণ আছে কিনা। দুটি ভেক্টর Node_Weight(100) এবং edge_graph[100] নেওয়া হয়।

• Node_Weight[] নোডের ওজন দিয়ে ইনিশিয়ালাইজ করা হয়।
• edge_graph ভেক্টর দিয়ে ট্রি তৈরি করা হয়।
• গ্লোবাল ভেরিয়েবল vowel ০ দিয়ে ইনিশিয়ালাইজ।
• check(string check_it) ফাংশন স্ট্রিং নিয়ে স্বরবর্ণ আছে কিনা চেক করে true/false রিটার্ন করে।
• স্ট্রিং দৈর্ঘ্য নির্ণয় করে ফর লুপে ট্রভারস করা হয়।
• প্রতিটি ক্যারেক্টর লোয়ারকেসে কনভার্ট করে c-তে স্টোর করা হয়।
• c যদি 'a', 'e', 'i', 'o', 'u'-র সাথে মিলে যায় তবে true রিটার্ন, অন্যথায় false।
• string_vowel(int node, int root) ফাংশন নোড এবং রুট নোড নিয়ে স্বরবর্ণ বিশিষ্ট ওজনয়ুক্ত নোড কাউন্ট রিটার্ন করে।
• str = Node_Weight[node] নিয়ে check(str) true হলে vowel++।
• edge_graph[node] ট্রভারস করে রিকারসিভ কল string_vowel(it, node)।
• শেষে vowel ভেরিয়েবলে প্রয়োজনীয় কাউন্ট পাওয়া যায়।

উদাহরণ

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

vector<string> Node_Weight(100);
vector<int> edge_graph[100];
int vowel = 0;

bool check(string check_it) {
    int length = check_it.length();
    for (int i = 0; i < length; i++) {
        char c = tolower(check_it[i]);
        if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
            return true;
        }
    }
    return false;
}

void string_vowel(int node, int root) {
    string str = Node_Weight[node];
    if (check(str)) {
        vowel++;
    }
    for (int it : edge_graph[node]) {
        if (it == root) {
            continue;
        }
        string_vowel(it, node);
    }
}

int main() {
    // নোডের ওজন
    Node_Weight[2] = "ae";
    Node_Weight[1] = "bcd";
    Node_Weight[4] = "io";
    Node_Weight[3] = "gfe";
    Node_Weight[8] = "tptpa";
    Node_Weight[9] = "iou";
    // গ্রাফ এজ তৈরি
    edge_graph[2].push_back(1);
    edge_graph[2].push_back(4);
    edge_graph[4].push_back(3);
    edge_graph[4].push_back(8);
    edge_graph[8].push_back(9);
    string_vowel(2, 2);
    cout << "Count the nodes of the tree whose weighted string contains a vowel are: " << vowel;
    return 0;
}

আউটপুট

Count the nodes of the tree whose weighted string contains a vowel are: 5