બે સ્ટેક્સનો ઉપયોગ કરીને ઇટરેટિવ પોસ્ટorderર્ડર ટ્રાવર્સલ


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એડોબ એમેઝોન ફેક્ટસેટ ફોરકાઇટ્સ પેટીએમ
સ્ટેક વૃક્ષ

સમસ્યા નિવેદન

"બે સ્ટેક્સનો ઉપયોગ કરીને ઇટેરેટિવ પોસ્ટ Postર્ડર ટ્ર Traવર્સલ" સમસ્યા જણાવે છે કે તમને એન ગાંઠો સાથે બાઈનરી ટ્રી આપવામાં આવે છે. તેના માટે પુનરાવર્તિત પોસ્ટorderર્ડર ટ્ર traવર્સલ બે સ્ટેક્સનો ઉપયોગ કરીને પ્રોગ્રામ લખો.

બે સ્ટેક્સનો ઉપયોગ કરીને ઇટરેટિવ પોસ્ટorderર્ડર ટ્રાવર્સલ

ઉદાહરણ

ઇનપુટ

બે સ્ટેક્સનો ઉપયોગ કરીને ઇટરેટિવ પોસ્ટorderર્ડર ટ્રાવર્સલ

 

4 5 2 6 7 3 1

ઇનપુટ

 

4 2 3 1

અલ્ગોરિધમ

  1. એનનો સમાવેશ કરતા નોડ માટે સ્ટ્રક્ચર બનાવો પૂર્ણાંક ડેટા અને બે નોડ પ્રકારનાં પોઇંટરોને ડાબે અને જમણે પકડી રાખવા માટે ચલ.
  2. તે પછી, નોડ બનાવવા માટે ફંક્શન બનાવો જે પૂર્ણાંક હોવાથી પૂર્ણાંક મૂલ્યને સ્વીકારે છે. તેની અંદર નોડ બનાવો. તેના ડેટા વેરિયેબલમાં પરિમાણ તરીકે પસાર કરેલો પૂર્ણાંક મૂલ્ય સ્ટોર કરો અને જમણી અને ડાબી પોઇન્ટર નોડને નલ તરીકે અપડેટ કરો. નવો બનાવેલ નોડ પાછો.
  3. એ જ રીતે, પુનરાવર્તિત માટે કાર્ય બનાવો પોસ્ટ ઓર્ડર આડાની જે બાઈનરી ટ્રીના રુટ નોડ તરફના નિર્દેશકને સ્વીકારે છે. તપાસો કે રુટ નોડ બરાબર છે, પાછા.
  4. બે બનાવો સ્ટેક ટ્રેવર્સલમાં મદદ માટે નોડ * પ્રકારનાં ડેટા સ્ટ્રક્ચર્સ.
  5. સ્ટેકમાં રુટ નોડને દબાણ / દાખલ કરો. બીજો નવો નોડ બનાવો.
  6. જ્યારે સ્ટેક 1 ખાલી નથી એટલે કે સ્ટેક 1 નું કદ 0 ની બરાબર નથી. નવા નોડમાં સ્ટેક 1 ની ટોચ પર નોડ સ્ટોર કરો અને તેને સ્ટેકમાંથી પ popપ કરો / દૂર કરો. સ્ટેકમાં દૂર કરેલા નોડને દબાણ કરો / દાખલ કરો 2. વર્તમાન નોડની ડાબી બાજુ છે કે કેમ તે તપાસો, તેને સ્ટેક પર દબાણ કરો / દાખલ કરો. સમાન, નોડની જમણી બાજુ છે કે કેમ તે તપાસો, તેને સ્ટેક 1 માં દબાણ કરો.
  7. જ્યારે સ્ટ 1ક 1 ખાલી ન હોય ત્યારે ફરીથી ટ્રverseવર કરો, 2 જી સ્ટેકમાં 1 સ્ટેકની ટોચ પર નોડ સ્ટોર કરો અને તેને XNUMX લી સ્ટેકથી પ popપ કરો.
  8. છેલ્લે 2 જી નોડ છાપો.

કોડ

સી ++ પ્રોગ્રામ બે સ્ટેક્સનો ઉપયોગ કરીને ઇટેરેટિવ પોસ્ટorderર્ડર ટ્રversવર્સલ માટે

#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

બે સ્ટેક્સનો ઉપયોગ કરીને ઇટેરેટિવ પોસ્ટorderર્ડર ટ્રversવર્સલ માટે જાવા પ્રોગ્રામ

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 ગાંઠો માટે જગ્યા વાપરી છે.