इस ट्यूटोरियल में, हम दिए गए बाइनरी ट्री में रूट नोड से सभी पत्ती नोड्स तक के पथ को प्रिंट करने के प्रोग्राम पर चर्चा करेंगे।
उदाहरण के लिए, मान लें हमारे पास निम्नलिखित बाइनरी ट्री है:
इस बाइनरी ट्री में, हमारे पास 4 पत्ती नोड्स हैं। इसलिए रूट नोड से पत्ती नोड तक हमारे पास 4 पथ हो सकते हैं।
इसे हल करने के लिए, हम पुनरावृत्त दृष्टिकोण (iterative approach) का उपयोग करेंगे। बाइनरी ट्री के प्रीऑर्डर ट्रैवर्सल करते समय हम पैरेंट पॉइंटर्स को मैप में स्टोर कर सकते हैं। जब भी ट्रैवर्सल के दौरान हम एक पत्ती नोड का सामना करते हैं, तो हम पैरेंट पॉइंटर्स का उपयोग करके रूट नोड से उसके पथ को आसानी से प्रिंट कर सकते हैं।
उदाहरण
#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
