מוריס הדרכת מעבר


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

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

דוגמה

          2

       /      \

     1           3

  /      \

4          5
4 1 5 2 3
       3

    /      \

  1          4
            
          /      \
 
        2          5
1 3 2 4 5

גישה

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

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

מוריס Inorder Traversal C ++ הדרכה

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

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

  1. אתחל את הצומת הנוכחי כשורש העץ.
  2. המשך לחזור עד שנגיע למצב בו צומת הנוכחי הופך להיות ריק. 
    • אם עזבו עץ המשנה של השורש הנוכחי הוא NULL :
        • כעת אנו יכולים להדפיס את השורש ולעבור לעץ המשנה הימני, כך ש- currentNode = currentNode-> ימינה.
    • אם עזבו עץ המשנה של השורש הנוכחי הוא  לא NULL :
        • במקרה זה אנו שחרור / חוט הצומת הימני ביותר בעץ המשנה השמאלי (קודמת ההזמנה) של הצומת הנוכחי לעצמו
            • temp = currentNode-> שמאל;
            • בעוד temp-> ימין הוא לא NULL או טמפ 'הוא לא הנוכחי
              • temp = temp-> ימין
        • אם temp-> ימין הוא NULL:
            • הסר הברגה כ temp-> ימין = NULL
            • לעבד את עץ המשנה הנכון, currentNode = currentNode-> ימין
        • אם temp-> ימין הוא לא ריק:
            • השחיל את הצומת הזה כ- temp-> right = currentNode
            • עיבוד כעת של עץ העץ השמאלי, currentNode = currentNode-> שמאל

יישום מעבר מוריס

תוכנית 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 morrisInorder(treeNode* &root)
{
    treeNode* currentNode = root;
    while(currentNode != NULL)
    {
        if(currentNode->left == NULL)
        {
            cout << currentNode->value << " ";
            currentNode = currentNode->right;
        }
        else
        {
            treeNode* temp = currentNode->left;
            while((temp->right != NULL) && (temp->right != currentNode))
                temp = temp->right;

            if(temp->right == NULL)
            {
                temp->right = currentNode;
                //threading
                currentNode = currentNode->left;
            }
            else
            {
                cout << currentNode->value << " ";
                temp->right = NULL;
                //unthreading
                currentNode = currentNode->right;
            }
        }
    }
}

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);

    morrisInorder(root);
    return 0;
}
4 1 5 2 3

תוכנית Java

class treeNode
{
    int value;
    treeNode left, right;

    public treeNode(int x)
    {
        value = x;
        left = right = null;
    }
}

class BinaryTree
{
    treeNode root;
    void MorrisInorder()
    {
        treeNode currentNode = root;

        while(currentNode != null)
        {
            if(currentNode.left == null)
            {
                System.out.print(currentNode.value + " ");
                currentNode = currentNode.right;
            }
            else
            {
                treeNode temp = currentNode;
                while(temp.right != null && temp.right != currentNode)
                    temp = temp.right;

                if(temp.right == null)
                {
                    temp.right = currentNode;
                    currentNode = currentNode.left;
                }
                else
                {
                    temp.right = null;
                    System.out.print(currentNode.value + " ");
                    currentNode = currentNode.right;
                }
            }
        }

    }

    public static void main(String args[])
    {
        BinaryTree tree = new BinaryTree();
        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.MorrisInorder();
    }
}
4 1 5 2 3

ניתוח מורכבות של מעבר מוריס

מורכבות זמן

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

מורכבות בחלל

O (1), כאשר אנו משתמשים במרחב קבוע להכרזה על כמה משתנים. אבל, לא נעשה שימוש במרחב עזר אחר לכל מטרה שהיא. על כך מבטיח מוריס אינדרור טרברסאל.