Iterative पोष्टर्डर दुई स्ट्याक्स को उपयोग गरेर traversal


कठिनाई तह सजिलो
बारम्बार सोधिन्छ एडोब अमेजन तथ्य फोरकाइट्स पेटम
थाक ट्री

समस्या वक्तव्य

समस्या "दुई स्ट्याक्सको प्रयोग गरेर इटेरेटि Post पोष्टर्डर ट्राभर्सल" भन्छन कि तपाईंलाई एन नोडहरू भएको बाइनरी रूख दिइन्छ। यो दुई स्ट्याकको प्रयोग गरी पुनरावृत्तिक पोस्टअर्डर ट्राभर्सलका लागि प्रोग्राम लेख्नुहोस्।

Iterative पोष्टर्डर दुई स्ट्याक्स को उपयोग गरेर traversal

उदाहरणका

आगत

Iterative पोष्टर्डर दुई स्ट्याक्स को उपयोग गरेर traversal

 

4 5 2 6 7 3 1

आगत

 

4 2 3 1

अल्गोरिदम

  1. नोडको समावेश सहित एउटा संरचना सिर्जना गर्नुहोस् पूर्णांक डाटा र दुई-नोड प्रकार पोइन्टरहरू बाँया र दायाँ समात्न चर।
  2. त्यस पछि, नयाँ नोड सिर्जना गर्न प्रकार्य सिर्जना गर्नुहोस् जसले एक परिमाण मानलाई यसलाई प्यारामिटरको रूपमा स्वीकार गर्दछ। यस भित्र नोड सिर्जना गर्नुहोस्। यसको डाटा भेरिएबलमा प्यारामिटरको रूपमा पारित गरेको पूर्णांक मान भण्डार गर्नुहोस् र दायाँ र बाँया सूचक नोडलाई शून्यको रूपमा अद्यावधिक गर्नुहोस्। नयाँ सिर्जना गरिएको नोड फिर्ता गर्नुहोस्।
  3. त्यस्तै, पुनरावृत्तिको लागि प्रकार्य सिर्जना गर्नुहोस् पोष्ट अर्डर ट्राभर्सल जसले सूचकलाई बाइनरी रूखको मूल नोडमा स्वीकार गर्दछ। यदि रुट नोड बराबर हो भने जाँच गर्नुहोस्, फर्कनुहोस्।
  4. दुई सिर्जना गर्नुहोस् स्ट्याक traversal मा मद्दत गर्न टाइप नोड * को डेटा संरचनाहरू।
  5. स्ट्याकमा रूट नोड पुश गर्नुहोस् / घुसाउनुहोस् १ अर्को नयाँ नोड सिर्जना गर्नुहोस्।
  6. जबकि स्ट्याक १ खाली छैन, यस्तै स्ट्याक १ को आकार ० बराबर छैन। नयाँ नोडमा स्ट्याक १ को शीर्षमा नोड भण्डार गर्नुहोस् र स्ट्याकबाट पप / हटाउनुहोस्। स्ट्याकमा हटाइएको नोडलाई पुश / घुसाउनुहोस् २. हालको नोडको बायाँ अवस्थित छ कि छैन जाँच गर्नुहोस्, स्ट्याकमा धकेल्नुहोस् / घुसाउनुहोस् १ त्यस्तै गरी, नोडको दायाँ अवस्थित छ वा छैन जाँच गर्नुहोस्, यसलाई स्ट्याक १ मा थिच्नुहोस्।
  7. फेरी ट्र्याभर गर्नुहोस् जब स्ट्याक १ खाली छैन, दोस्रो स्ट्याकमा स्ट्याक १ को शीर्षमा नोड भण्डार गर्नुहोस् र यसलाई १ स्ट्याकबाट पप गर्नुहोस्।
  8. अन्तिममा दोस्रो नोड प्रिन्ट गर्नुहोस्।

कोड

C ++ Iterative पोष्टर्डर ट्राभर्सल दुई स्ट्याक्स प्रयोगको लागि प्रोग्राम

#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 पोष्टर्डर ट्राभर्सल दुई स्ट्याक्स प्रयोगको लागि जाभा कार्यक्रम

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 नोडहरूको लागि ठाउँ प्रयोग गर्‍यौं।