پیمایش تکراری پسورد با استفاده از دو پشته


سطح دشواری ساده
اغلب در خشت آمازون واقعیت فورکایت Paytm با
پشته درخت

بیان مسأله

مسئله "Iterative Postorder Traversal Using Two Stacks" بیان می کند که یک درخت باینری با n گره به شما داده می شود. برنامه را با استفاده از دو پشته برای پیمایش تکراری پس از سفارش بنویسید.

پیمایش تکراری پسورد با استفاده از دو پشته

مثال

ورودی

پیمایش تکراری پسورد با استفاده از دو پشته

 

4 5 2 6 7 3 1

ورودی

 

4 2 3 1

الگوریتم

  1. ساختاری برای گره متشکل از an ایجاد کنید عدد صحیح متغیر برای نگه داشتن داده ها و اشاره گرهای نوع دو گره به چپ و راست.
  2. بعد از آن ، برای ایجاد گره جدید تابع ایجاد کنید که یک مقدار صحیح را به عنوان پارامتر قبول می کند. درون آن گره ایجاد کنید. مقدار صحیح تصویب شده به عنوان پارامتر را در متغیر داده خود ذخیره کرده و گره اشاره گر راست و چپ را به صورت null به روز کنید. گره تازه ایجاد شده را برگردانید.
  3. به همین ترتیب ، عملکرد را برای تکرار ایجاد کنید پیمایش سفارش که نشانگر را به گره ریشه درخت باینری می پذیرد. بررسی کنید که آیا گره ریشه برابر با null باشد ، برگردید.
  4. ایجاد دو پشته ساختارهای داده ای از نوع Node * برای کمک به پیمایش.
  5. گره ریشه را در پشته فشار داده و وارد کنید 1. گره جدید دیگری ایجاد کنید.
  6. در حالی که پشته 1 خالی نیست ، یعنی اندازه پشته 1 برابر 0 نیست. گره را در بالای پشته 1 در گره جدید ذخیره کنید و آن را از پشته پاپ / بردارید. گره برداشته شده را در پشته فشار دهید / وارد کنید 2. بررسی کنید که آیا سمت چپ گره فعلی وجود دارد ، آن را فشار دهید / وارد کنید 1. به طور مشابه ، وجود راست گره را بررسی کنید ، آن را در پشته 1 فشار دهید.
  7. در حالی که پشته 1 خالی نیست ، دوباره عبور کنید ، گره را در بالای پشته 1 در پشته 2 ذخیره کنید و آن را از پشته 1 پاپ کنید.
  8. در آخر گره 2 را چاپ کنید.

رمز

برنامه 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

برنامه جاوا برای پیمایش تکراری پس از سفارش با استفاده از دو پشته

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

تحلیل پیچیدگی

پیچیدگی زمان

O (N) که n تعداد گره های درج شده است.

پیچیدگی فضا

O (N) زیرا ما از فضای گره استفاده کردیم.