इस ट्यूटोरियल में, हम किसी दिए गए बाइनरी ट्री में रूट नोड से सभी लीफ नोड्स तक पाथ प्रिंट करने के लिए एक प्रोग्राम पर चर्चा करेंगे।
उदाहरण के लिए, मान लें कि हमारे पास निम्न बाइनरी ट्री है
इस बाइनरी ट्री में, हमारे पास 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