এই টিউটোরিয়ালে, আমরা একটি প্রদত্ত বাইনারি গাছের রুট নোড থেকে সমস্ত লিফ নোডের পথ প্রিন্ট করার জন্য একটি প্রোগ্রাম নিয়ে আলোচনা করব৷
উদাহরণস্বরূপ, আসুন আমরা বলি যে আমাদের নিম্নলিখিত বাইনারি ট্রি রয়েছে
এই বাইনারি গাছে, আমাদের 4টি পাতার নোড রয়েছে। তাই আমাদের রুট নোড থেকে লিফ নোড পর্যন্ত 4টি পথ থাকতে পারে।
এটি সমাধান করার জন্য, আমরা পুনরাবৃত্তিমূলক পদ্ধতি ব্যবহার করব। বাইনারি গাছের প্রি-অর্ডার ট্রাভার্সাল করার সময় আমরা একটি মানচিত্রে প্যারেন্ট পয়েন্টার সংরক্ষণ করতে পারি। যখনই ট্র্যাভার্সালের সময় আমরা একটি লিফ নোডের মুখোমুখি হই তখনই আমরা প্যারেন্ট পয়েন্টার ব্যবহার করে রুট নোড থেকে এর পথ সহজেই প্রিন্ট করতে পারি।
উদাহরণ
#include <bits/stdc++.h>>
using namespace std;
struct Node{
int data;
struct Node *left, *right;
};
//to create a new node
Node* create_node(int data){
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
//printing the path from root to leaf
void print_cpath(Node* curr, map<Node*, Node*> parent){
stack<Node*> 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;
}
//to perform pre order traversal
void preorder_traversal(Node* root){
if (root == NULL)
return;
stack<Node*> nodeStack;
nodeStack.push(root);
map<Node*, Node*> 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
