এই টিউটোরিয়ালে, আমরা একটি বাইনারি ট্রিতে প্রথম সংক্ষিপ্ত রুট থেকে পাতার পথ প্রিন্ট করার জন্য একটি প্রোগ্রাম নিয়ে আলোচনা করব।
এতে, আমাদেরকে স্বতন্ত্র মান সহ একটি বাইনারি গাছ দেওয়া হবে, এবং আমাদের একটি প্রদত্ত বাইনারি গাছের রুট নোড থেকে লিফ নোড পর্যন্ত সংক্ষিপ্ততম পথটি খুঁজে বের করতে হবে৷
এটি সমাধান করার জন্য, আমরা একটি বাইনারি ট্রিতে লেভেল অর্ডার ট্রাভার্সাল করার জন্য একটি সারি ব্যবহার করতে পারি এবং নোডগুলিকে সংক্ষিপ্ততম পথে সংরক্ষণ করতে পারি। এর জন্য, একবার আমরা চূড়ান্ত স্তরের জন্য বামদিকের নোডে পৌঁছানোর পরে, আমরা সারি থেকে মানগুলি পুনরুদ্ধার করি এবং সংক্ষিপ্ততম পথটি প্রিন্ট করি৷
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
struct Node{
struct Node* left;
struct Node* right;
int data;
};
struct Node* create_node(int data){
struct Node* temp = new Node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
void print_spath(int Data, unordered_map<int, int> parent){
if (parent[Data] == Data)
return;
print_spath(parent[Data], parent);
cout << parent[Data] << " ";
}
void leftmost_path(struct Node* root){
queue<struct Node*> q;
q.push(root);
int LeafData = -1;
struct Node* temp = NULL;
unordered_map<int, int> parent;
parent[root->data] = root->data;
while (!q.empty()){
temp = q.front();
q.pop();
if (!temp->left && !temp->right){
LeafData = temp->data;
break;
}
else{
if (temp->left){
q.push(temp->left);
parent[temp->left->data] = temp->data;
}
if (temp->right) {
q.push(temp->right);
parent[temp->right->data] = temp->data;
}
}
}
print_spath(LeafData, parent);
cout << LeafData << " ";
}
int main(){
struct Node* root = create_node(21);
root->left = create_node(24);
root->right = create_node(35);
root->left->left = create_node(44);
root->right->left = create_node(53);
root->right->right = create_node(71);
root->left->left->left = create_node(110);
root->left->left->right = create_node(91);
root->right->right->left = create_node(85);
leftmost_path(root);
return 0;
} আউটপুট
21 35 53
