सी ++ प्रोग्रामिंग में रिकर्सन का उपयोग किए बिना रूट को लीफ पथ पर प्रिंट करें।

बाइनरी ट्री को देखते हुए प्रोग्राम को रूट से लीफ तक के कई रास्तों का पता लगाना चाहिए, जिसका मतलब है कि सभी रास्तों को प्रिंट किया जाना चाहिए, लेकिन चुनौती यह है कि रिकर्सन का उपयोग किए बिना।

हम पेड़ को पुनरावृत्त रूप से पार करेंगे क्योंकि बाधा इसे बिना पुनरावृत्ति के करना है। तो इसे प्राप्त करने के लिए हम एक एसटीएल मानचित्र का उपयोग कर सकते हैं जो रूट तत्व को स्टोर करेगा और जब भी लीफ नोड को लेवल ऑर्डर ट्रैवर्सल के माध्यम से पहचाना जाएगा तो यह रूट से लीफ तक पथ को प्रिंट करेगा क्योंकि एक मैप पॉइंटर है जो रूट नोड को इंगित कर रहा है।

उपरोक्त पेड़ में, कई पथ हैं जो जड़ से पत्ती तक पहुँचने के लिए उत्पन्न किए जा सकते हैं -

10 -> 3 -> 140
10 -> 3 -> 162
10 -> 211 -> 100
10 -> 211 -> 146

इसलिए, प्रोग्राम को दिए गए सभी पथों को दिए गए बाइनरी ट्री के आउटपुट के रूप में प्रिंट करना चाहिए।

एल्गोरिदम

START
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->data = data
   node->left = node->right = NULL;
   return (node)
Step 3 -> create function to calculate the path
   void calculatePath(Node* curr, map<Node*, Node*> first)
   create STL stack<Node*> stk
   Loop While (curr)
      stk.push(curr)
      curr = first[curr]
   End
   Loop While !stk.empty()
      curr = stk.top()
      stk.pop()
      print curr->data
   End
Step 4 -> create function to find the leaf nodes
   void leaf(Node* root)
   IF root = NULL
      Return
   End
   Create STL stack<Node*> stc
   stc.push(root)
   Create STL map<Node*, Node*> prnt
   prnt[root] = NULL
   Loop while !stc.empty()
      Node* curr = stc.top()
      stc.pop()
      IF!(curr->left) && !(curr->right)
         calculatePath(curr, prnt)
      End
      IF curr->right
         prnt[curr->right] = curr
         stc.push(curr->right)
      End
      IF curr->left
         prnt[curr->left] = curr
         stc.push(curr->left)
      End
   End
STOP

उदाहरण

#include <bits/stdc++.h>
using namespace std;
//structure of a node
struct Node{
   int data;
   struct Node *left, *right;
};
//function to create a new node
Node* newNode(int data){
   Node* node = new Node;
   node->data = data;
   node->left = node->right = NULL;
   return node;
}
//this function will calculate the path
void calculatePath(Node* curr, map<Node*, Node*> first){
   stack<Node*> stk;
   while (curr){
      stk.push(curr);
      curr = first[curr];
   }
   while (!stk.empty()){
      curr = stk.top();
      stk.pop();
      cout << curr->data << " ";
   }
   cout << endl;
}
//this function will lead to the leafs
void leaf(Node* root){
   if (root == NULL)
      return;
   stack<Node*> stc;
   stc.push(root);
   map<Node*, Node*> prnt;
   prnt[root] = NULL;
   while (!stc.empty()){
      Node* curr = stc.top();
      stc.pop();
      if (!(curr->left) && !(curr->right))
         calculatePath(curr, prnt);
      if (curr->right){
         prnt[curr->right] = curr;
         stc.push(curr->right);
      }
      if (curr->left){
         prnt[curr->left] = curr;
         stc.push(curr->left);
      }
   }
}
int main(){
   Node* root = newNode(67); //it will insert the nodes to create a tree
   root->left = newNode(34);
   root->right = newNode(89);
   root->left->left = newNode(23);
   root->left->right = newNode(95);
   root->right->left = newNode(12);
   leaf(root); //call the function leaf
   return 0;
}

आउटपुट

यदि हम उपरोक्त प्रोग्राम चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा

67 34 23
67 34 95
67 89 12