এই টিউটোরিয়ালে বাইনারি ট্রিতে রুট নোড থেকে সব লিফ নোড (leaf nodes) পর্যন্ত পাথ প্রিন্ট করার প্রোগ্রাম আলোচনা করা হবে।
উদাহরণস্বরূপ, নিচের বাইনারি ট্রিতে ৪টি লিফ নোড রয়েছে। তাই রুট থেকে লিফ পর্যন্ত ৪টি পাথ থাকবে।
সমাধান: ইটারেটিভ (iterative) পদ্ধতি ব্যবহার করা হবে। প্রি-অর্ডার ট্রাভার্সাল (preorder traversal) করার সময় পেরেন্ট পয়েন্টার (parent pointers) একটি ম্যাপ (map) এ সংরক্ষণ করা। ট্রাভার্সালের সময় লিফ নোড পাওয়া গেলে পেরেন্ট পয়েন্টার ব্যবহার করে রুট থেকে সেটি পাথ সহজে প্রিন্ট করা যায়।
উদাহরণ
#include <bits/stdc++.h>> using namespace std; struct Node{ int data; struct Node *left, *right; };// নতুন নোড তৈরি Node* create_node(int data){ Node* node = new Node; node->data = data; node->left = node->right = NULL; return node; } // রুট থেকে লিফ পাথ প্রিন্ট করা void print_cpath(Node* curr, map parent){ stack nodes_stack; while (curr){ nodes_stack.push(curr); curr = parent[curr]; } while (!nodes_stack.empty()){ curr = nodes_stack.top(); nodes_stack.pop(); cout << curr->data << " "; } cout << endl; } // প্রি-অর্ডার ট্রাভার্সাল করা void preorder_traversal(Node* root){ if (root == NULL) return; stack nodeStack; nodeStack.push(root); map parent; parent[root] = NULL; while (!nodeStack.empty()){ Node* current = nodeStack.top(); nodeStack.pop(); if (!(current->left) && !(current->right)) print_cpath(current, parent); if (current->right){ parent[current->right] = current; nodeStack.push(current->right); } if (current->left){ parent[current->left] = current; nodeStack.push(current->left); } } } int main(){ Node* root = create_node(101); root->left = create_node(82); root->right = create_node(23); root->left->left = create_node(34); root->left->right = create_node(55); root->right->left = create_node(29); preorder_traversal(root); return 0; } আউটপুট
101 82 34 101 82 55 101 23 29
