المسح التكراري للبريد باستخدام مجموعتين


مستوى الصعوبة سهل
كثيرا ما يطلب في أدوبي أمازون مجموعة الحقائق فوركايتس Paytm
كومة شجرة

المشكلة بيان

تشير مشكلة "المسح التكراري للبريد اللاحق باستخدام مجموعتين" إلى أنه تم إعطاؤك شجرة ثنائية تحتوي على عُقد. اكتب البرنامج لاجتيازه التكراري اللاحق باستخدام مكدسين.

المسح التكراري للبريد باستخدام مجموعتين

مثال

إدخال

المسح التكراري للبريد باستخدام مجموعتين

 

4 5 2 6 7 3 1

إدخال

 

4 2 3 1

خوارزمية

  1. قم بإنشاء هيكل للعقدة يتكون من عدد صحيح متغير للاحتفاظ بالبيانات ومؤشرات نوع العقدة لليسار واليمين.
  2. بعد ذلك ، قم بإنشاء وظيفة لإنشاء العقدة الجديدة التي تقبل قيمة عدد صحيح كمعامل. قم بإنشاء عقدة بداخلها. قم بتخزين قيمة العدد الصحيح الذي تم تمريره كمعامل في متغير البيانات الخاص به وقم بتحديث عقدة المؤشر اليمنى واليسرى على أنها خالية. قم بإرجاع العقدة التي تم إنشاؤها حديثًا.
  3. وبالمثل ، قم بإنشاء وظيفة للتكرار اجتياز طلب آخر الذي يقبل المؤشر إلى العقدة الجذرية للشجرة الثنائية. تحقق مما إذا كانت العقدة الجذر تساوي قيمة خالية ، ثم عُد
  4. قم بإنشاء اثنين كومة هياكل البيانات من نوع العقدة * للمساعدة في الاجتياز.
  5. ادفع / أدخل عقدة الجذر في المكدس 1. أنشئ عقدة جديدة أخرى.
  6. بينما المكدس 1 ليس فارغًا ، أي أن حجم المكدس 1 لا يساوي 0. قم بتخزين العقدة أعلى المكدس 1 في العقدة الجديدة وقم بإزالتها / إزالتها من المكدس. ادفع / أدخل العقدة التي تمت إزالتها في المكدس 2. تحقق مما إذا كان يسار العقدة الحالية موجودًا ، وادفعها / أدخلها في المكدس 1. وبالمثل ، تحقق مما إذا كان يمين العقدة موجودًا ، وادفعها في المكدس 1.
  7. قم بالمرور مرة أخرى عندما لا تكون المكدس 1 فارغة ، وقم بتخزين العقدة في أعلى المكدس 1 في المجموعة الثانية وقم بإخراجها من المجموعة الأولى.
  8. أخيرًا ، قم بطباعة العقدة الثانية.

رمز

برنامج 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 هو عدد العقد المدرجة.

تعقيد الفضاء

O (ن) لأننا استخدمنا مساحة لعدد n من العقد.