מעבר איטרטיבי של עץ בינארי


רמת קושי בינוני
עץ בינארי מעבר עץ

בבעיה "מעבר איטרטיבי של עץ בינארי" ניתן לנו עץ בינארי. עלינו לחצות את זה בצורה מסודרת "באופן איטרטיבי", בלי הרקורסיה.

דוגמה

                 2

              /     \

            1         3

          /   \

        4       5                

4 1 5 2 3
           1 
 
         /    \

       2        3

     /            \

    4               6

                      \

                        7

4 2 1 3 6 7

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

  1. אתחל משתנה "CurNode" כשורש העץ הבינארי
  2. אתחל ערימה ריקה, המכיל את הצמתים כשהם עוברים דרך
  3. בצע את הפעולות הבאות עד שהערימה אינה ריקה או curNode לא הפך ריק:
    • בעוד curNode is לֹא ריק:
      1. דחוף curNode לתוך הערימה
      2. המשך ללכת לילד השמאלי ביותר על ידי שינוי הצומת הנוכחי כ- curNode = curNode-> שמאל
    • כעת, הצומת העליון בערימה הוא הצומת השמאלי ביותר של עץ המשנה הנוכחי, לכן אנו מדפיסים את הערך של הצומת העליון בערימה
    • הקצה curNode כילד הימני של הצומת העליון בערימה כמו curNode = stack.top () -> ימינה 
    • המשך ללכת לילד השמאלי ביותר על ידי שינוי הצומת הנוכחי כ- curNode = curNode-> שמאל לעבד עץ משנה ימני של הצומת השמאלי ביותר
    • הוצא אלמנט מתוך הערימה

הסבר

התוכנית משתמשת ברעיון שהערימה קופצת את האלמנט האחרון שנוסף. באלגוריתם שהוסבר לעיל, אנו פשוט מסיקים שאם הצומת הנוכחי (שהוא בתחילה השורש של עץ) יש ילד שמאלי, ואז אנחנו ממשיכים לדחוף את הילד השמאלי שלו לערמה עד שלא יישארו עוד ילדים שמאלים

כאשר המקרה נוצר כך שלצומת הנוכחי אין ילד שמאל, ברור שהצומת העליון בערימה הוא ה- "הצומת הכי שמאלי ביותר" הוסיף. אז זה צריך להיות הראשון בסדר המעבר שנותר. לכן, אנו מתחילים להדפיס / להוסיף אותו לרשימת ההזמנות שלנו ולהקפיץ אותו מהערימה. לאחר שסיימנו, כעת ברור לנו העובדה שב- Left-curNode-Right (רצף ההזמנה), שמאל ו צומת חלקם עוברים דרך. אז תת העץ הימני של הצומת נמצא בתהליך!

באופן אינטואיטיבי, מכיוון שאנחנו רוצים להחיל את אותו התהליך על העץ התחתון הנכון של הצומת הנוכחי, אנחנו יכולים להכליל אותו כ: curNode = curNode-> ימינה.

מעבר איטרטיבי של עץ בינארי

יישום

תכנית C ++ של מעבר סדרי איטרטיבי של עץ בינארי

#include <bits/stdc++.h>

using namespace std;

struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};



void iterativeInorder(treeNode* root)
{
    stack <treeNode*> ;
    treeNode* curNode = root;elements

    while(curNode != NULL || !elements.empty())
    {
        while(curNode != NULL)
        {
            elements.push(curNode);
            curNode = curNode->left;
        }


        cout << elements.top()->value << " ";
        curNode = elements.top()->right;
        elements.pop();
    }
}


int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(1);
    root->right = new treeNode(3);
    root->left->left = new treeNode(4);
    root->left->right = new treeNode(5);

    iterativeInorder(root);
    cout << endl;
    return 0;
}
4 1 5 2 3 

תכנית ג'אווה לחציית סדר איטרטיבי של עץ בינארי

import java.util.Stack; 
  
class treeNode 
{ 
    int value; 
    treeNode left, right; 
  
    public treeNode(int x) 
    { 
        value= x; 
        left = right = null; 
    } 
} 
  
class Tree 
{ 
    treeNode root; 
    void iterativeInorder() 
    { 
        
        Stack<treeNode> elements = new Stack<treeNode>(); 
        treeNode curNode = root; 
  
        while (curNode != null || !elements.empty()) 
        { 
            while (curNode != null) 
            { 
                elements.push(curNode); 
                curNode = curNode.left; 
            } 
 
            curNode = elements.peek().right;
            System.out.print(elements.peek().value + " ");
            elements.pop();
        } 
    } 
  
    public static void main(String args[]) 
    { 
        Tree tree = new Tree(); 
        tree.root = new treeNode(2); 
        tree.root.left = new treeNode(1); 
        tree.root.left.left = new treeNode(4); 
        tree.root.left.right = new treeNode(5); 
        tree.root.right = new treeNode(3); 
        tree.iterativeInorder(); 
    } 
}
4 1 5 2 3

ניתוח מורכבות

מורכבות זמן של מעבר איטרטיבי של עץ בינארי

מורכבות הזמן היא עַל), כשאנחנו מבקרים בכל צומת בדיוק פעם אחת. כאן, N הוא מספר הצמתים בעץ הבינארי.

מורכבות בחלל של מעבר איטרטיבי של עץ בינארי

מורכבות החלל היא עַל). בהתחשב במקרה הגרוע ביותר, בו העץ יכול להיות מוטה, מורכבות החלל תהיה שווה למספר הצמתים בעץ הבינארי.