এই টিউটোরিয়ালে, আমরা একটি বাইনারি গাছের রুট নোড থেকে প্রদত্ত বাইনারি ট্রিতে উপস্থিত অন্যান্য সমস্ত নোডের পথ প্রিন্ট করার জন্য একটি প্রোগ্রাম নিয়ে আলোচনা করব।
এই প্রোগ্রামে, আমাদের একটি সংখ্যা দেওয়া হবে, যা 1 থেকে N পর্যন্ত বাইনারি ট্রিতে উপস্থিত উপাদানের সংখ্যা নির্দেশ করে; 1 হল বাইনারি ট্রির রুট নোড৷ অতএব, আমাদের কাজ হল রুট নোড থেকে বাইনারি ট্রিতে উপস্থিত অন্যান্য উপাদানগুলিতে সমস্ত সম্ভাব্য পথ প্রিন্ট করা৷
এই প্রোগ্রামটি সমাধান করার জন্য, আমরা জানি যে প্রদত্ত নোড I এর জন্য, এর বাম চাইল্ডকে 2*i হিসাবে গণনা করা যেতে পারে এবং এর ডান চাইল্ডটিকে 2*i+1 হিসাবে গণনা করা যেতে পারে। তারপরে আমরা ব্যাকট্র্যাকিং ব্যবহার করে সেই নির্দিষ্ট উপাদানটির পথ একটি ভেক্টরে সংরক্ষণ করতে পারি এবং তারপরে সম্ভাব্য সমস্ত পথ চূড়ান্তভাবে মুদ্রণ করতে পারি।
উদাহরণ
#include <iostream>
#include <vector>
using namespace std;
//calculating all the possible paths from the root node
void calc_allpath(vector<int> paths, int nth_node, int kth_node){
if (kth_node > nth_node)
return;
paths.push_back(kth_node);
for (int i = 0; i < paths.size(); i++)
cout << paths[i] << " ";
cout << endl;
calc_allpath(paths, nth_node, kth_node * 2);
calc_allpath(paths, nth_node, kth_node * 2 + 1);
}
//printing all the possible paths from the root node
void print_allpath(int nth_node){
vector<int> paths;
calc_allpath(paths, nth_node, 1);
}
int main(){
int nth_node = 9;
print_allpath(nth_node);
return 0;
} আউটপুট
1 1 2 1 2 4 1 2 4 8 1 2 4 9 1 2 5 1 3 1 3 6 1 3 7
