मॉरिस ट्रॅव्हर्सल  


अडचण पातळी मध्यम
वारंवार विचारले ऍमेझॉन फेसबुक फोरकाइट्स 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. रूट नोड स्वीकारणारा मॉरिसट्राव्हर्सल फंक्शन तयार करा.
  3. जर रूट शून्य असेल तर परत या.
  4. संदर्भ करीर मूळ म्हणून सेट करा. आडवा असताना कर्ल शून्य नाही.
  5. जर कररचा डावा मुलगा कर्ल मध्ये संग्रहित शून्य प्रिंट व्हॅल्यू असेल तर त्याचे योग्य मुल आहे कारण ते curr अद्यतनित करते.
  6. डाव्या मुलाच्या डाव्या मुलाच्या उजव्या नोडच्या उजव्या नोडच्या रूपात अन्यथा करीर अद्यतनित करा आणि करीयरच्या डाव्या मुलाच्या रूपात अद्यतनित करा.

कोड

मॉरिस ट्राव्हर्सलचा वापर करून बायनरी ट्री ओलांडण्यासाठी सी ++ प्रोग्राम

#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

जावा प्रोग्राम मॉरिस ट्राव्हर्सलचा वापर करून बायनरीच्या झाडावर जाण्यासाठी

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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन), कारण आम्ही बायनरी ट्री मधील सर्व नोड्स ओलांडत आहोत. एन नोड्स असल्याने वेळची जटिलता रेखीय असते.

हे सुद्धा पहा
दिलेल्या लेव्हल ऑर्डर ट्रॅव्हर्सलपासून बीएसटी बांधा

स्पेस कॉम्प्लेक्सिटी

ओ (1), कारण आम्ही समस्येचे निराकरण करण्यासाठी पुनरावृत्ती किंवा स्टॅक वापरत नाही. आम्ही निरंतर जागेची गुंतागुंत करण्यासाठी स्थिर असणारी अनेक चल वापरली आहेत.

प्रीऑर्डर ट्रॅव्हर्सल  

उदाहरण

            1

          /    \

        2        3

      /   \

   4        5
1 2 4 5 3
            7

          /   \

       14       21
7 14 21

अल्गोरिदम

  1. एक नोड वर्ग आरंभ करा ज्यात नोडशी संबंधित व्हेरिएबल्स आणि पॉईंटर्स आहेत.
  2. नोड स्वीकारणारे मॉरिसट्राव्हर्सल फंक्शन तयार करा.
  3. नोड शून्य नसताना ट्रॅव्हर्स करा.
  4. नोडचे डावे मूल नल मध्ये संग्रहित नल प्रिंट व्हॅल्यू असल्यास आणि योग्य नॉड म्हणून नोड अद्यतनित करते.
  5. अन्य नोडच्या व्हेरिएबल curr मध्ये नोडची डावी मुल संचयित करा.
  6. क्रॉसची उजवी मुल शून्य नसली किंवा नोडच्या बरोबरीने न जुमानता आडवा करा आणि योग्य करर म्हणून अद्यतनित करा
  7. जर कररचे उजवे मूल शून्य किंवा नोडच्या समान असेल तर, योग्य मुलास कुरूरचे उजवे मूल शून्य आणि नोड म्हणून अद्यतनित करा.
  8. अन्यथा नोड डेटा मुद्रित करा आणि डाव्या मुलाला म्हणून curr चे उजवे मूल नोड आणि नोड म्हणून अद्यतनित करा.

कोड

मॉरिस ट्राव्हर्सलचा वापर करून बायनरी ट्री ओलांडण्यासाठी सी ++ प्रोग्राम

#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

जावा प्रोग्राम मॉरिस ट्राव्हर्सलचा वापर करून बायनरीच्या झाडावर जाण्यासाठी

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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन), कारण आम्ही बायनरी ट्री मधील सर्व नोड्स ओलांडत आहोत. एन नोड्स असल्याने वेळची जटिलता रेखीय असते.

हे सुद्धा पहा
पोस्टफिक्स एक्सप्रेशनचे मूल्यांकन

स्पेस कॉम्प्लेक्सिटी

ओ (1), कारण आम्ही समस्येचे निराकरण करण्यासाठी पुनरावृत्ती किंवा स्टॅक वापरत नाही. आम्ही निरंतर जागेची गुंतागुंत करण्यासाठी स्थिर असणारी अनेक चल वापरली आहेत.