এই সমস্যায়, আমাদের একটি বাইনারি ট্রি দেওয়া আছে। আমাদের কাজ হল একটি প্রোগ্রাম তৈরি করা যা বাইনারি ট্রিকে ব্র্যাকেটসহ স্ট্রিং-এ রূপান্তর করবে সি++-এ।
বাইনারি ট্রির মানগুলি পূর্ণসংখ্যা এবং এটি প্রি-অর্ডার ট্রভারসাল পদ্ধতিতে প্রোগ্রামে দেওয়া হবে। স্ট্রিংটিতে শুধুমাত্র পূর্ণসংখ্যা এবং প্যারেনথেসিস () থাকবে, এটি অপ্টিমাইজড হওয়া উচিত অর্থাৎ সমস্ত খালি জোড়া বাদ দেওয়া উচিত।
বাইনারি ট্রি হল এমন একটি ট্রি যার একটি বিশেষ শর্ত রয়েছে যে প্রতিটি নোডে সর্বোচ্চ দুটি চাইল্ড থাকতে পারে।
বাইনারি ট্রির উদাহরণ
প্রি-অর্ডার ট্রভারসাল: [4, 1, 8, 3, 9, 2, 5]
একটি উদাহরণ নিয়ে সমস্যাটি বুঝি
ইনপুট
প্রি-অর্ডার: [4, 1, 8, 3, 9, 2, 5]
আউটপুট
ব্যাখ্যা
রুট -> 4()() -> 4(1()())(9) -> 4(1(8()())())(9) -> 4(1(8(3)())())(9) -> 4(1(8(3)())())(9(2)(5))
সমস্ত খালি প্যারেনথেসিস অপসারণ করার পর,
4(1(8(3)))(9(2)(5))
এখন, আমরা সমস্যাটি সমাধান করব, আমরা বাইনারি ট্রির প্রি-অর্ডার ট্রভারসাল করব এবং যেখানে প্রয়োজন সেখানে ব্র্যাকেট রাখব। এছাড়াও, আমাদের অতিরিক্ত ব্র্যাকেটের জোড়া বাদ দিতে হবে। এর জন্য, আমরা একটি ফাংশনের রিকার্সিভ কল ব্যবহার করব যা ব্র্যাকেট রাখবে।
আমরা একটি নোড প্রিন্ট করব এবং সেই নোডের উভয় চাইল্ডের জন্য রিকার্সিভ ফাংশন কল করব যতক্ষণ না কোনো নোডের চাইল্ড থাকে না অর্থাৎ লিফ নোড।
একটি নোডের চাইল্ড নোডের জন্য ফাংশন কল করার সময় আমরা নিম্নলিখিত ৪টি ক্ষেত্রের যেকোনো একটি দেখতে পাব:
ক্ষেত্র ১ - যখন নোডের উভয় চাইল্ড নোড উপস্থিত থাকে। আমরা উভয় চাইল্ডের জন্য ব্র্যাকেট রাখব এবং তাদের মান ব্র্যাকেটের ভিতরে রাখব এবং তাদের চাইল্ড নোড থাকলে কল করব।
উদাহরণ - উপরের উদাহরণ থেকে রুট নোড ৪-এর জন্য যেখানে উভয় চাইল্ড নোড উপস্থিত, 4(1)(9)।
ক্ষেত্র ২ - যখন নোডের শুধু বাম চাইল্ড থাকে। আমরা বাম চাইল্ডকে ব্র্যাকেটে রাখব, যেহেতু ডান চাইল্ড নেই তাই তার ব্র্যাকেট বাদ যাবে। এবং শুধু বাম চাইল্ডের সাবট্রি কল করা হবে যদি থাকে।
উদাহরণ - উপরের উদাহরণ থেকে মান ১-যুক্ত নোডের জন্য যেখানে শুধু বাম চাইল্ড নোড উপস্থিত, 4(1(8()()))(9)।
ক্ষেত্র ৩ - যখন নোডের শুধু ডান চাইল্ড থাকে। আমরা বাম চাইল্ডের জন্য একটি খালি ব্র্যাকেট রাখব। এবং ডান চাইল্ডের মান রাখব এবং এর সাব-ট্রি থাকলে কল করব।
ক্ষেত্র ৪ - যখন নোডের কোনো চাইল্ড নেই (লিফ নোড)। আমরা কোনো ব্র্যাকেট রাখব না শুধু মানটি রাখব।
উদাহরণ - উপরের উদাহরণ থেকে মান ৫-যুক্ত নোডগুলির জন্য যেখানে কোনো চাইল্ড নেই, 4(1(8(3)))(9(2)(5()()))।
ব্র্যাকেটসহ বাইনারি ট্রিকে স্ট্রিং-এ রূপান্তর করার প্রোগ্রাম
// ব্র্যাকেটসহ বাইনারি ট্রিকে স্ট্রিং-এ রূপান্তর করার প্রোগ্রাম
উদাহরণ
#include <iostream> using namespace std; struct Node { int data; Node *left, *right; }; Node* insertNode(int data){ Node* node = (Node*)malloc(sizeof(Node)); node->data = data; node->left = node->right = NULL; return (node); } void ConveryBinaryTreeToString(Node* root, string& str){ if (root == NULL) return; str.push_back(root->data + '0'); if (!root->left && !root->right) return; str.push_back('('); ConveryBinaryTreeToString(root->left, str); str.push_back(')'); if (root->right) { str.push_back('('); ConveryBinaryTreeToString(root->right, str); str.push_back(')'); } } int main() { struct Node* root = insertNode(4); root->left = insertNode(1); root->right = insertNode(9); root->left->left = insertNode(8); root->left->left->left = insertNode(3); root->right->left = insertNode(2); root->right->right = insertNode(5); string binaryTreeString = ""; ConveryBinaryTreeToString(root, binaryTreeString); cout<<"ব্র্যাকেটসহ বাইনারি ট্রির প্রি-অর্ডার ট্রভারসাল স্ট্রিং: "<<binaryTreeString; }
আউটপুট
ব্র্যাকেটসহ বাইনারি ট্রির প্রি-অর্ডার ট্রভারসাল স্ট্রিং: 4(1(8(3)))(9(2)(5))
