နှစ်ခု Stack သုံးပြီးကြားမှာ Postorder ဖြတ်သန်း


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Adobe က အမေဇုံ အချက်အလက် လေးကစ် Paytm
စုပုံထား သစ်ပင်

ပြProbleနာဖော်ပြချက်

ပြTwoနာက“ Stack Two ကိုသုံးပြီး Iterative Postorder ဖြတ်သန်းခြင်း” ပြ ”နာ ကသင့်အား n node များပါသည့် binary tree ပေးသည်ဟုဖော်ပြသည်။ stack နှစ်ခုသုံးပြီး iterative postorder ဖြတ်သန်းဘို့အစီအစဉ်ကိုရေးပါ။

နှစ်ခု Stack သုံးပြီးကြားမှာ Postorder ဖြတ်သန်း

နမူနာ

input

နှစ်ခု Stack သုံးပြီးကြားမှာ Postorder ဖြတ်သန်း

 

4 5 2 6 7 3 1

input

 

4 2 3 1

algorithm

  1. n တစ်ခုပါဝင်သော node အတွက်ဖွဲ့စည်းပုံတစ်ခုတည်ဆောက်ပါ ကိန်း ဒေတာကိုသိမ်းထားရန် variable ကိုနှင့်လက်ဝဲဘက်နှင့်နှစ်ခု-node ကို type ကိုထောက်ပြ။
  2. ပြီးနောက်၎င်းသည် parameter အနေဖြင့် integer တန်ဖိုးကိုလက်ခံသော node အသစ်ကိုဖန်တီးရန် function ကိုဖန်တီးပါ။ ၎င်းအတွင်း၌ node တစ်ခုဖန်တီးပါ။ ကိန်းဂဏန်းအနေဖြင့်သတ်မှတ်ထားသောကိန်းဂဏန်းအဖြစ် data variable တွင်သိမ်းဆည်းပြီးညာဘက်နှင့်ဘယ်ဘက် node ကို null အဖြစ် update လုပ်ပါ။ အသစ်ဖန်တီး node ကိုပြန်သွားပါ။
  3. အလားတူပင်ကြားမှာများအတွက် function ကိုဖန်တီးပါ အမှာစာဖြတ်သန်း post သော binary သစ်ပင်၏အမြစ် node ကိုမှ pointer ကိုလက်ခံ။ root node သည် null နှင့်တူညီမှုရှိမရှိပြန်လည်စစ်ဆေးပါ။
  4. နှစ်ခုဖန်တီးပါ စုပုံထား အဆိုပါဖြတ်သန်းရာတွင်ကူညီရန်အမျိုးအစား Node ကို * ၏ဒေတာဖွဲ့စည်းပုံ။
  5. နောက်ခံ node အသစ်တစ်ခုဖန်တီးပါ။
  6. stack 1 သည်အချည်းနှီးမဖြစ်သော်လည်းဆိုလိုသည်မှာ stack 1 ၏အရွယ်အစားသည်သုညနှင့်မတူပါ။ stack 0 ထိပ်ရှိ node ကို node အသစ်တွင်သိမ်းပြီး stack မှ pop / ဖယ်ရှားပါ။ ဖယ်ရှားထားသော node ကို stack ထဲသို့တွန်းထည့် / ထည့်ပါ။ ၂။ လက်ရှိ node ၏ဘယ်ဘက်ရှိသလားကိုစစ်ဆေးပါ၊ ၄ င်းကို stack ထဲသို့တွန်းချပါ။ ၁။ အလားတူစွာ node ၏ညာဘက်ရှိမရှိကိုစစ်ဆေးပါ၊ ၁ ကိုတွန်းပါ။
  7. stack 1 သည်အချည်းနှီးမဖြစ်ဘဲပြန်သွားပါ။ ဒုတိယထပ်တွင်ရှိသော node ကိုဒုတိယ stack တွင်သိမ်းဆည်းပြီး၎င်းကို 1st stack မှသိမ်းပါ။
  8. နောက်ဆုံးမှာ 2nd node ကို print ထုတ်ပါ။

ကုဒ်

နှစ်ပုံကိုအသုံးပြု။ ကြားမှာ Postorder ဖြတ်သန်းများအတွက် C ++ အစီအစဉ်

#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

နှစ်ခု Stack သုံးပြီး Iterative Postorder ဖြတ်သန်းများအတွက်ဂျာဗားအစီအစဉ်

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 ဖြည့်စွက် node များ၏အရေအတွက်သည်။

အာကာသရှုပ်ထွေးမှု

အို (ဎ) ဘာလို့လဲဆိုတော့ငါတို့ n node များအတွက်နေရာသုံးထားလို့ပါ။