বাইনারি ট্রি দেওয়া হলে প্রোগ্রামটিকে অনেক প্রদত্ত পথের মধ্যে মূল থেকে পাতা পর্যন্ত সংক্ষিপ্ততম পথ খুঁজে বের করতে হবে৷
যেহেতু আমরা গাছটিকে বাম থেকে ডানে অতিক্রম করি, তাই যদি মূল থেকে পাতা পর্যন্ত একাধিক সংক্ষিপ্ততম পথ থাকে তবে প্রোগ্রামটি একটি গাছের বাম দিকে প্রথম ট্রাভার্স করা সংক্ষিপ্ততম পথটি প্রিন্ট করবে।
আমরা একটি সারি ব্যবহার করতে পারি যা লেভেল অর্ডার ট্রাভার্সাল ব্যবহার করে প্রতিটি স্তর অতিক্রম করবে এবং সর্বনিম্ন সংখ্যক লেভেল সহ পাথ প্রিন্ট করা হবে কারণ এটি রুট থেকে পাতা পর্যন্ত সংক্ষিপ্ততম পথ হবে
উপরের গাছে, মূল থেকে পাতা পর্যন্ত একাধিক পথ রয়েছে
10 -> 3 (this one is the shortest path amongst all) 10 -> 211 -> 100 10 -> 211 -> 146
উদাহরণ
Input : 10 3 211 100 146 Output : 10 3
অ্যালগরিদম
Step 1 -> create a structure of a node as struct node struct node *left, *right int data End Step 2 -> function to create a node node* newnode(int data) node *temp = new node temp->data = data temp->left = temp->right= NULL return temp Step 3 -> create function for calculating path void path(int data, unordered_map <int,int> prnt) IF prnt[data] = data Return End path(prnt[data], prnt) print prnt[data] step 4 -> function for finding out the left path void left(Node* root) create STL queue<Node*> que que.push(root) int leaf = -1 Node* temp = NULL Create STL unordered_map<int, int> prnt prnt[root->data] = root->data Loop While !que.empty() temp = que.front() que.pop() IF !temp->left && !temp->right leaf = temp->data break End Else IF temp->left que.push(temp->left) prnt[temp->left->data] = temp->data End IF temp->right que.push(temp->right) prnt[temp->right->data] = temp->data End End End path(leaf, prnt) print leaf Step 5 -> In main() Create tree using Node* root = newnode(90) root->left = newnode(21) call left(root) stop
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
// structure of a node
struct Node {
struct Node *left,*right;
int data;
};
//function to create a new node
Node* newnode(int data){
Node* temp = new Node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
//function to set a path
void path(int data, unordered_map <int,int> prnt) {
if (prnt[data] == data)
return;
path(prnt[data], prnt);
cout << prnt[data] << " ";
}
//function for a leaf path
void left(Node* root) {
queue<Node*> que;
que.push(root);
int leaf = -1;
Node* temp = NULL;
unordered_map<int, int> prnt;
prnt[root->data] = root->data;
while (!que.empty()){
temp = que.front();
que.pop();
if (!temp->left && !temp->right{
leaf = temp->data;
break;
} else {
if (temp->left){
que.push(temp->left);
prnt[temp->left->data] = temp->data;
}
if (temp->right){
que.push(temp->right);
prnt[temp->right->data] = temp->data;
}
}
}
path(leaf, prnt);
cout << leaf << " ";
}
int main(){
Node* root = newnode(90);
root->left = newnode(21);
root->right = newnode(32);
root->left->left = newnode(45);
root->right->left = newnode(52);
root->right->right = newnode(27);
root->left->left->left = newnode(109);
root->left->left->right = newnode(101);
root->right->right->left = newnode(78);
left(root);
return 0;
} আউটপুট
যদি আমরা উপরের প্রোগ্রামটি চালাই তাহলে এটি নিম্নলিখিত আউটপুট তৈরি করবে
90 32 52
