এই টিউটোরিয়ালে কমপ্লিট বাইনারি ট্রি (Complete Binary Tree)-এ রুট নোড (root node) থেকে বাকি সব নোড পর্যন্ত পাথ প্রিন্ট করার প্রোগ্রাম আলোচনা করা হবে।
এই প্রোগ্রামে একটি সংখ্যা N দেওয়া থাকবে, যা বাইনারি ট্রিতে ১ থেকে N পর্যন্ত উপাদানের সংখ্যা বোঝাবে; ১ হলো রুট নোড। তাই রুট নোড থেকে বিভিন্ন উপাদান পর্যন্ত সব সম্ভাব্য পাথ প্রিন্ট করতে হবে।
সমাধান: নোড i-এর বাম চাইল্ড (left child) = 2*i, ডান চাইল্ড (right child) = 2*i+1। ব্যাকট্র্যাকিং (backtracking) ব্যবহার করে প্রতিটি উপাদানের পাথ একটি ভেক্টরে (vector) সংরক্ষণ করে সব পাথ প্রিন্ট করা।
উদাহরণ
#include <iostream> #include <vector> using namespace std; // রুট নোড থেকে সব সম্ভাব্য পাথ ক্যালকুলেট করা void calc_allpath(vectorpaths, 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); } // রুট নোড থেকে সব পাথ প্রিন্ট করা void print_allpath(int nth_node){ vector 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
