מעבר איטרטיבי לאחר הזמנה באמצעות שתי ערימות


רמת קושי קַל
נשאל לעתים קרובות Adobe אמזון בעברית סט עובדות פורקיטים Paytm
לערום עֵץ

הצהרת בעיה

הבעיה "מעבר איטרטיבי לאחר הזמנה באמצעות שתי ערימות" קובעת שאתה מקבל עץ בינארי עם צמתים. כתוב את התוכנית למעבר איטרטיבי לאחר ההזמנה באמצעות שתי ערימות.

מעבר איטרטיבי לאחר הזמנה באמצעות שתי ערימות

דוגמה

קֶלֶט

מעבר איטרטיבי לאחר הזמנה באמצעות שתי ערימות

 

4 5 2 6 7 3 1

קֶלֶט

 

4 2 3 1

אַלגוֹרִיתְם

  1. צור מבנה לצומת המורכב מ- מספר שלם משתנה להחזקת נתונים ומצביעים מסוג שני צומתים שמאלה וימינה.
  2. לאחר מכן, צור את הפונקציה כדי ליצור את הצומת החדש המקבל ערך שלם כפרמטר. צור צומת בתוכו. אחסן את ערך המספר השלם שהועבר כפרמטר במשתנה הנתונים שלו ועדכן את צומת המצביע הימני והשמאלי כ- null. החזר את הצומת החדש שנוצר.
  3. באופן דומה, צור את הפונקציה עבור האיטרטיבי חציית הזמנה שמקבל את המצביע לצומת השורש של העץ הבינארי. בדוק אם צומת השורש שווה ל- null, חזור.
  4. צור שניים לערום מבני נתונים מסוג Node * כדי לסייע במעבר.
  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

תוכנית Java למעבר איטרטיבי לאחר הזמנה באמצעות שתי ערימות

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) כי השתמשנו במרחב לצמתים.