מוריס חוצה


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

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

מעבר לפי הזמנה

דוגמה

מוריס חוצה

9 7 1 6 4 5 3
            1

          /    \

        2        3

      /   \

   4        5
4 2 5 1 3
            7

          /   \

       14       21
14 7 21

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

  1. אתחל כיתה צומת המכילה משתנים ומצביעים הקשורים לצומת.
  2. צור פונקציה MorrisTraversal שמקבלת את צומת השורש.
  3. אם השורש אפס, חזור.
  4. הגדר את זרם ההתייחסות כשורש. לחצות תוך כדי גזר אינו אפס.
  5. אם הילד השמאלי של curr הוא ערך הדפסה null המאוחסן ב- curr ועדכן את curr מכיוון שהוא ילד ימני.
  6. אחרת עדכן את curr כצומת ימין של הצומת הימני ביותר של עץ המשנה השמאלי שלו ועדכן את curr כילד השמאלי של curr.

קופונים

תוכנית C ++ לחצות עץ בינארי באמצעות מוריס טרברסאל

#include <bits/stdc++.h> 
using namespace std;
  
struct Node{ 
    int data; 
    struct Node* left; 
    struct Node* right; 
}; 
  
void MorrisTraversal(struct Node* root){ 
    struct Node *curr, *pre; 
  
    if(root == NULL) 
        return; 
  
    curr = root; 
    while(curr != NULL){ 
  
        if(curr->left == NULL){ 
            printf("%d ", curr->data); 
            curr = curr->right; 
        } 
        else{ 
            pre = curr->left; 
            while (pre->right != NULL && pre->right != curr) 
                pre = pre->right; 
  
            if(pre->right == NULL) { 
                pre->right = curr; 
                curr = curr->left; 
            } 
            else{ 
                pre->right = NULL; 
                cout<<curr->data<<" "; 
                curr = curr->right; 
            }
        } 
    } 
} 
  
struct Node* newNode(int data){ 
    struct Node* node = new Node; 
    node->data = data; 
    node->left = NULL; 
    node->right = NULL; 
  
    return (node); 
} 
  
int main(){ 
    struct Node *root = newNode(5);
    root->left = newNode(7);
    root->right = newNode(3);
    root->left->left = newNode(9);
    root->left->right = newNode(6);
    root->left->right->left = newNode(1);
    root->left->right->right = newNode(4);
  
    MorrisTraversal(root); 
  
    return 0; 
}
9 7 1 6 4 5 3

תוכנית Java לחצות עץ בינארי באמצעות מוריס טרברסאל

class Node { 
    int data; 
    Node left, right; 
  
    Node(int item) 
    { 
        data = item; 
        left = right = null; 
    } 
} 
  
class BTree{ 
    Node root; 
  
    void MorrisTraversal(Node root){ 
        Node curr, pre; 
  
        if(root == null) 
            return; 
  
        curr = root; 
        while(curr != null){ 
            if(curr.left == null){ 
                System.out.print(curr.data + " "); 
                curr = curr.right; 
            } 
            else{ 
                pre = curr.left; 
                while(pre.right != null && pre.right != curr) 
                    pre = pre.right; 
  
                if(pre.right == null){ 
                    pre.right = curr; 
                    curr = curr.left; 
                } 
  
                else{ 
                    pre.right = null; 
                    System.out.print(curr.data + " "); 
                    curr = curr.right; 
                } 
            } 
        } 
    } 
  
    public static void main(String args[]){ 
        BTree tree = new BTree(); 
        tree.root = new Node(5);
        tree.root.left = new Node(7);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(9);
        tree.root.left.right = new Node(6);
        tree.root.left.right.left = new Node(1);
        tree.root.left.right.right = new Node(4);
  
        tree.MorrisTraversal(tree.root); 
    } 
}
9 7 1 6 4 5 3

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

מורכבות זמן

O (N) כי אנחנו חוצים את כל הצמתים בעץ הבינארי. מכיוון שיש N צמתים מורכבות הזמן היא ליניארית.

מורכבות בחלל

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

הזמנה מוקדמת

דוגמה

            1

          /    \

        2        3

      /   \

   4        5
1 2 4 5 3
            7

          /   \

       14       21
7 14 21

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

  1. אתחל כיתה צומת המכילה משתנים ומצביעים הקשורים לצומת.
  2. צור פונקציה MorrisTraversal שמקבלת צומת.
  3. חצה בעוד הצומת אינו אפס.
  4. אם הילד השמאלי של הצומת הוא ערך ההדפסה null המאוחסן בצומת ועדכן את הצומת כיוון שהוא בן ימין.
  5. אחסן אחרת את הילד השמאלי של הצומת בזרם משתנה אחר מסוג הצומת.
  6. חצה בעוד הילד הימני של הגזירה אינו אפס או לא שווה לצומת ועדכן את הגוש כיוון שהוא ילד נכון.
  7. אם ילד הזכות של הגמר הוא אפס או שווה לצומת, עדכן את הבן הנכון של הגזירה כנקוד וצומת שכן מדובר בילד נכון.
  8. בחר / י בהדפס נתוני צומת ועדכן את הילד הימני של הזרם כצומת וצומת היות שהוא ילד שמאלי.

קופונים

תוכנית C ++ לחצות עץ בינארי באמצעות מוריס טרברסאל

#include <bits/stdc++.h> 
using namespace std;  
  
class node{  
    public: 
        int data;  
        node *left, *right;  
};  
  
node* newNode(int data){  
    node* temp = new node(); 
    temp->data = data;  
    temp->left = temp->right = NULL;  
    return temp;  
}  
  
void MorrisTraversal(node* root){  
    while(root){  
        if(root->left == NULL){  
            cout<<root->data<<" ";  
            root = root->right;  
        }  
        else{  
            node* curr = root->left;  
            while(curr->right && curr->right != root)  
                curr = curr->right;  
  
            if(curr->right == root){  
                curr->right = NULL;  
                root = root->right;  
            }  
  
            else{  
                cout<<root->data<<" ";  
                curr->right = root;  
                root = root->left;  
            }  
        }  
    }  
}  
  
int main(){  
    node *root = newNode(5);
    root->left = newNode(7);
    root->right = newNode(3);
    root->left->left = newNode(9);
    root->left->right = newNode(6);
    root->left->right->left = newNode(1);
    root->left->right->right = newNode(4);  
  
    MorrisTraversal(root);  
  
  
    return 0;  
}
5 7 9 6 1 4 3

תוכנית Java לחצות עץ בינארי באמצעות מוריס טרברסאל

class Node{ 
      
    int data; 
    Node left, right; 
      
    Node(int item){ 
        data = item; 
        left = right = null; 
    } 
}
  
class BTree{ 
      
    Node root; 
      
    void MorrisTraversal(){ 
        MorrisTraversal(root); 
    } 
  
    void MorrisTraversal(Node node) { 
        while(node != null){ 
            if(node.left == null) { 
                System.out.print(node.data + " "); 
                node = node.right; 
            } 
            else{ 
                Node curr = node.left; 
                while (curr.right != null && curr.right != node) { 
                    curr = curr.right; 
                } 
  
                if(curr.right == node){ 
                    curr.right = null; 
                    node = node.right; 
                } 
   
                else{ 
                    System.out.print(node.data + " "); 
                    curr.right = node; 
                    node = node.left; 
                } 
            } 
        } 
    } 
      
    public static void main(String args[]){ 
        BTree tree = new BTree(); 
        tree.root = new Node(5);
        tree.root.left = new Node(7);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(9);
        tree.root.left.right = new Node(6);
        tree.root.left.right.left = new Node(1);
        tree.root.left.right.right = new Node(4);
        
        tree.MorrisTraversal(); 
    } 
}
5 7 9 6 1 4 3

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

מורכבות זמן

O (N) כי אנחנו חוצים את כל הצמתים בעץ הבינארי. מכיוון שיש N צמתים מורכבות הזמן היא ליניארית.

מורכבות בחלל

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