دو اسٹیکس کا استعمال کرتے ہوئے Iterative پوسٹ آرڈر ٹروراسل


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایڈوب ایمیزون حقیقت فورکائٹس پی ٹی ایم ایم
اسٹیک درخت

مسئلہ یہ بیان

"دو اسٹیکس کا استعمال کرتے ہوئے Iterative Postorder Traversal" مسئلہ یہ بتاتا ہے کہ آپ کو نود کے ساتھ بائنری ٹری دیا گیا ہے۔ اس کے لئے دو اسٹیکس کا استعمال کرتے ہوئے پوسٹورڈر ٹروراسل کے لئے پروگرام لکھیں۔

دو اسٹیکس کا استعمال کرتے ہوئے Iterative پوسٹ آرڈر ٹروراسل

مثال کے طور پر

ان پٹ

دو اسٹیکس کا استعمال کرتے ہوئے Iterative پوسٹ آرڈر ٹروراسل

 

4 5 2 6 7 3 1

ان پٹ

 

4 2 3 1

الگورتھم

  1. ایک پر مشتمل نوڈ کے لئے ایک ڈھانچہ بنائیں عددی ڈیٹا اور دو نوڈ قسم کے پوائنٹرز کو بائیں اور دائیں رکھنے کے لئے متغیر کریں۔
  2. اس کے بعد ، نیا نوڈ بنانے کے لئے فنکشن بنائیں جو پیرامیٹر کی حیثیت سے ایک انٹیجر ویلیو کو قبول کرتا ہے۔ اس کے اندر نوڈ بنائیں۔ انٹیگر ویلیو کو پیرامیٹر کی حیثیت سے اس کے ڈیٹا متغیر میں اسٹور کریں اور دائیں اور بائیں پوائنٹر نوڈ کو کالعدم بنائیں۔ نو تشکیل شدہ نوڈ کو واپس کریں۔
  3. اسی طرح ، تکرار کرنے والے کے لئے فنکشن تشکیل دیں پوسٹ آرڈر ٹرورسال جو بائنری ٹری کے جڑ نوڈ پر پوائنٹر کو قبول کرتا ہے۔ چیک کریں کہ جڑ نوڈ ناخن کے برابر ہے ، واپس لو۔
  4. دو بنائیں ڈھیر لگانا traversal میں مدد کے لئے نوڈ * قسم کے ڈیٹا ڈھانچے.
  5. اسٹیک میں جڑ نوڈ کو پش / ڈالیں 1. دوسرا نیا نوڈ بنائیں۔
  6. جبکہ اسٹیک 1 خالی نہیں ہے یعنی اسٹیک 1 کا سائز 0 کے برابر نہیں ہے ۔نیک کو اسٹیک 1 کے اوپر نوڈ کو نئے نوڈ میں اسٹور کریں اور اسٹیک سے پاپ / ہٹائیں۔ اسٹیک میں ہٹا دیا ہوا نوڈ کو پش / ڈالیں۔ 2. چیک کریں کہ موجودہ نوڈ کا بائیں موجود ہے تو ، اسے اسٹیک میں دبائیں / ڈالیں۔ 1 اسی طرح ، چیک کریں کہ آیا نوڈ کا دایاں موجود ہے ، اسٹیک 1 میں دبائیں۔
  7. ایک بار پھر عبور کریں جب اسٹیک 1 خالی نہیں ہے تو ، اسٹیک 1 کے اوپر نوڈ کو دوسرے اسٹیک میں اسٹور کریں اور اسے پہلی اسٹیک سے پاپ کریں۔
  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 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 نوڈس کیلئے جگہ استعمال کی۔