এই টিউটোরিয়ালে বাইনারি ট্রিতে রুট নোড (root node) থেকে একটি নির্দিষ্ট নোড (given node) পর্যন্ত পাথ প্রিন্ট করার প্রোগ্রাম আলোচনা করা হবে।
একটি বাইনারি ট্রিতে সব নোড ভিন্ন (distinct) হলে, একটি নির্দিষ্ট নোড পর্যন্ত রুট থেকে পূর্ণ পাথ প্রিন্ট করতে হবে।
সমাধান: রিকারশন (recursion) ব্যবহার করা হবে। বাইনারি ট্রি ট্রাভার্সালের সময় রিকারসিভলি (recursively) নির্দিষ্ট উপাদানটি খুঁজে বের করা এবং পাশাপাশি সেটি পাওয়ার পাথ সংরক্ষণ করা।
উদাহরণ
#include <bits/stdc++.h> using namespace std; struct Node{ int data; Node *left, *right; }; struct Node* create_node(int data){ struct Node *new_node = new Node; new_node->data = data; new_node->left = new_node->right = NULL; return new_node; } // রুট নোড থেকে উপাদান পর্যন্ত পাথ আছে কিনা চেক করা bool is_path(Node *root, vector& arr, int x){ if (!root) return false; arr.push_back(root->data); if (root->data == x) return true; if (is_path(root->left, arr, x) || is_path(root->right, arr, x)) return true; arr.pop_back(); return false; } // রুট নোড থেকে উপাদান পর্যন্ত পাথ প্রিন্ট করা void print_path(Node *root, int x){ vector arr; if (is_path(root, arr, x)){ for (int i=0; i "; cout << arr[arr.size() - 1]; } else cout << "Path doesn't exists" << endl; } int main(){ struct Node *root = create_node(13); root->left = create_node(21); root->right = create_node(43); root->left->left = create_node(34); root->left->right = create_node(55); root->right->left = create_node(68); root->right->right = create_node(79); int x = 68; print_path(root, x); return 0; } আউটপুট
13 -> 43 -> 68
