इस ट्यूटोरियल में, हम बाइनरी ट्री में पहला सबसे छोटा रूट-टू-लीफ पथ प्रिंट करने के प्रोग्राम पर चर्चा करेंगे।
इसमें, हमें एक बाइनरी ट्री दिया जाएगा जिसमें विशिष्ट मान होंगे, और हमें दिए गए बाइनरी ट्री में रूट नोड से पत्ती नोड तक का सबसे छोटा पथ ज्ञात करना होगा।
इसे हल करने के लिए, हम बाइनरी ट्री में लेवल ऑर्डर ट्रैवर्सल करने के लिए एक कतार (queue) का उपयोग कर सकते हैं और सबसे छोटे पथ में नोड्स को स्टोर कर सकते हैं। इसके लिए, एक बार जब हम अंतिम स्तर के लिए सबसे बाएं नोड तक पहुंच जाते हैं, तो हम कतार से मान प्राप्त करते हैं और सबसे छोटा पथ प्रिंट करते हैं।
उदाहरण
#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 parent) {
if (parent[Data] == Data)
return;
print_spath(parent[Data], parent);
cout << parent[Data] << " ";
}
void leftmost_path(struct Node* root) {
queue q;
q.push(root);
int LeafData = -1;
struct Node* temp = NULL;
unordered_map 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
