C++ এ বন্ধনী সহ স্ট্রিং করার জন্য বাইনারি ট্রি

এই সমস্যায়, আমরা একটি বাইনারি গাছ দেওয়া হয়. আমাদের কাজ হল এমন একটি প্রোগ্রাম তৈরি করা যা একটি বাইনারি ট্রিকে C++ এ বন্ধনী সহ স্ট্রিং-এ রূপান্তর করবে।

বাইনারি ট্রির মান পূর্ণসংখ্যা এবং এটি একটি প্রি-অর্ডার ট্রাভার্সিং উপায়ে প্রোগ্রামে খাওয়ানো হবে। স্ট্রিংটিতে শুধুমাত্র পূর্ণসংখ্যা এবং বন্ধনী থাকা উচিত (), এছাড়াও এটি অপ্টিমাইজ করা উচিত অর্থাৎ সমস্ত খালি জোড়া বাদ দেওয়া উচিত।

বাইনারি ট্রি এটি একটি গাছ যার একটি বিশেষ অবস্থা রয়েছে যে প্রতিটি নোডে সর্বাধিক দুটি সন্তান থাকতে পারে৷

একটি বাইনারি গাছের উদাহরণ -

প্রি-অর্ডার ট্রাভার্সাল:[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 − যখন নোডে উভয় চাইল্ড নোড থাকে। আমরা উভয় সন্তানের জন্য বন্ধনী রাখব এবং বন্ধনীর ভিতরে তাদের মান রাখব এবং যদি থাকে তবে তাদের চাইল্ড নোডকে কল করব।

উদাহরণ − রুট নোডের জন্য উপরের উদাহরণ থেকে, 4 যেখানে উভয় চাইল্ড নোড উপস্থিত রয়েছে, 4(1)(9)।

কেস 2 − যখন নোডে শুধুমাত্র বাম-সন্তান থাকে। আমরা বাম সন্তানকে বন্ধনীতে রাখব, যেহেতু কোন ডান সন্তান উপস্থিত নেই তার বন্ধনীটি বাদ দেওয়া হবে। এবং শুধুমাত্র বাম শিশুর সাবট্রিগুলিকে বলা হয় যদি থাকে৷

উদাহরণ − 1 মান সহ নোডের জন্য উপরের উদাহরণ থেকে যেখানে শুধুমাত্র বাম চাইল্ড নোডটি উপস্থিত রয়েছে, 4(1(8()()))(9)৷

কেস 3 − যখন নোডে শুধুমাত্র রাইট-চাইল্ড থাকে। আমরা বাম সন্তানের জন্য একটি খালি বন্ধনী রাখব। এবং সঠিক সন্তানের মূল্য স্থাপন করা হবে এবং যদি থাকে তবে তার উপ-বৃক্ষ বলা হবে।

কেস 4 − যখন নোডের কোনো সন্তান নেই (লিফ নোড)। আমরা কোন বন্ধনী এবং শুধু মান রাখব না।

উদাহরণ − মান 5 সহ নোডের জন্য উপরের উদাহরণ থেকে যেখানে কোনও শিশু উপস্থিত নেই, 4(1(8(3)))(9(2)(5()()))।

বন্ধনী সহ বাইনারি ট্রিকে স্ট্রিং-এ রূপান্তর করার প্রোগ্রাম

//বন্ধনী সহ বাইনারি ট্রিকে স্ট্রিং-এ রূপান্তর করার প্রোগ্রাম

উদাহরণ

#include  namespace ব্যবহার করে std;struct Node {int data; নোড *বাম, *ডান;};নোড* ইনসার্ট নোড(ইনট ডেটা){ নোড* নোড =(নোড*)ম্যালক(সাইজওফ(নোড)); নোড->ডেটা =ডেটা; node->left =node->right =NULL; return (node);}void ConveryBinaryTreeToString(Node* root, string&str){ if (root ==NULL) রিটার্ন; str.push_back(root->ডেটা + '0'); যদি (!root->বামে &&!root->ডান) ফিরে আসে; str.push_back('('); ConveryBinaryTreeToString(root->left, str); str.push_back(')'); যদি (root->ডান) { 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<<"বন্ধনী সহ বাইনারি ট্রির প্রি-অর্ডার ট্রাভার্সাল সহ স্ট্রিং হল:"< 
আউটপুট
 
বন্ধনী সহ বাইনারি ট্রির প্রি-অর্ডার ট্রাভার্সাল সহ স্ট্রিং হল:4(1(8(3)))(9(2)(5))