Iterative पोस्टऑर्डर Traversal दो ढेर का उपयोग कर


कठिनाई स्तर आसान
में अक्सर पूछा एडोब वीरांगना FactSet चौपाई Paytm
धुआँरा पेड़

समस्या का विवरण

समस्या "Iterative Postorder Traversal Using Two Stacks" में कहा गया है कि आपको n नोड्स के साथ एक बाइनरी ट्री दिया जाता है। दो स्टैक्स का उपयोग करके पुनरावृत्त पोस्टऑर्डर ट्रैवर्सल के लिए प्रोग्राम लिखें।

Iterative पोस्टऑर्डर Traversal दो ढेर का उपयोग कर

उदाहरण

निवेश

Iterative पोस्टऑर्डर Traversal दो ढेर का उपयोग कर

 

4 5 2 6 7 3 1

निवेश

 

4 2 3 1

कलन विधि

  1. नोड से मिलकर एक संरचना बनाएं पूर्णांक चर डेटा और दो-नोड प्रकार इंगित करने के लिए बाएँ और दाएँ पकड़।
  2. उसके बाद, नया नोड बनाने के लिए फ़ंक्शन बनाएं जो पूर्णांक मान को पैरामीटर के रूप में स्वीकार करता है। इसके अंदर एक नोड बनाएं। पूर्णांक मान को उसके डेटा चर में पैरामीटर के रूप में संग्रहीत करें और दाएं और बाएं सूचक नोड को शून्य के रूप में अपडेट करें। नए बनाए गए नोड को वापस करें।
  3. इसी प्रकार, पुनरावृत्त के लिए फ़ंक्शन बनाएं पोस्ट ऑर्डर ट्रैवर्सल जो बाइनरी ट्री के रूट नोड को पॉइंटर स्वीकार करता है। जांचें कि क्या रूट नोड शून्य के बराबर है, वापस लौटें।
  4. दो बनाएँ धुआँरा ट्रैवर्सल में मदद करने के लिए टाइप नोड * की डेटा संरचनाएं।
  5. स्टैक में रूट नोड को पुश / सम्मिलित करें। एक और नया नोड बनाएं।
  6. जबकि स्टैक 1 खाली नहीं है अर्थात स्टैक 1 का आकार 0. के बराबर नहीं है। नए नोड में स्टैक 1 के शीर्ष पर नोड स्टोर करें और इसे स्टैक से हटा दें। स्टैक में हटाए गए नोड को पुश / सम्मिलित करें 2. जांचें कि क्या वर्तमान नोड का बाईं ओर मौजूद है, इसे स्टैक में डालें / डालें 1. इसी तरह, जांचें कि क्या नोड का अधिकार मौजूद है, इसे स्टैक 1 में धक्का दें।
  7. स्टैक 1 फिर से करें जबकि स्टैक 1 खाली नहीं है, 2 स्टैक में स्टैक 1 के शीर्ष पर नोड स्टोर करें और इसे XNUMX स्टैक से पॉप करें।
  8. आख़िर में दूसरा नोड प्रिंट करें।

कोड

सी + + Iterative पोस्टऑर्डर Traversal के लिए दो स्टैक का उपयोग करके प्रोग्राम

#include <bits/stdc++.h> 
using namespace std; 
  
struct Node{ 
    int data; 
    Node *left, *right; 
}; 
  
Node* newNode(int data){ 
    Node* node = new Node; 
    node->data = data; 
    node->left = node->right = NULL; 
    return node; 
} 

void postOrderIterative(Node* root){ 
    if(root == NULL){ 
        return; 
    }
  
    stack<Node *> s1, s2; 
  
    s1.push(root); 
    Node* node; 
  
    while(!s1.empty()){ 
        node = s1.top(); 
        s1.pop(); 
        s2.push(node); 
  
        if(node->left){ 
            s1.push(node->left);
        }
        if(node->right){ 
            s1.push(node->right);
        }
    } 
  
    while(!s2.empty()){ 
        node = s2.top(); 
        s2.pop(); 
        cout << node->data << " "; 
    } 
} 
  
int main(){ 
    Node* root = NULL; 
    root = newNode(1); 
    root->left = newNode(2); 
    root->right = newNode(3); 
    root->left->left = newNode(4); 
    root->left->right = newNode(5); 
    root->right->left = newNode(6); 
    root->right->right = newNode(7); 
  
    postOrderIterative(root); 
  
    return 0; 
}
4 5 2 6 7 3 1

दो ढेरियों का उपयोग करके Iterative Postorder Traversal के लिए जावा प्रोग्राम

import java.util.*; 

class IterativePostorder{ 
  
    static class node{ 
        int data; 
        node left, right; 
  
        public node(int data){ 
            this.data = data; 
        } 
    } 
  
    static Stack<node> s1, s2; 
  
    static void postOrderIterative(node root){ 
        s1 = new Stack<>(); 
        s2 = new Stack<>(); 
  
        if(root == null){ 
            return; 
        }
  
        s1.push(root); 
  
        while(!s1.isEmpty()){ 
            node temp = s1.pop(); 
            s2.push(temp); 
  
            if(temp.left != null){ 
                s1.push(temp.left);
            }
            
            if(temp.right != null){ 
                s1.push(temp.right);
            }
        } 
  
        while(!s2.isEmpty()){ 
            node temp = s2.pop(); 
            System.out.print(temp.data + " "); 
        } 
    } 
  
    public static void main(String[] args){ 
        
        node root = null; 
        root = new node(1); 
        root.left = new node(2); 
        root.right = new node(3); 
        root.left.left = new node(4); 
        root.left.right = new node(5); 
        root.right.left = new node(6); 
        root.right.right = new node(7); 
  
        postOrderIterative(root); 
    } 
}
4 5 2 6 7 3 1

जटिलता विश्लेषण

समय जटिलता

पर) जहां n नोड्स की संख्या डाली गई है।

अंतरिक्ष जटिलता

पर) क्योंकि हमने n नोड के लिए स्थान का उपयोग किया है।