मॉरिस ट्रैवर्सल


कठिनाई स्तर मध्यम
में अक्सर पूछा वीरांगना Facebook चौपाई गूगल माइक्रोसॉफ्ट
पेड़ वृक्ष का त्राटक

मॉरिस ट्रैवर्सल एक ऐसी विधि है जो स्टैक और पुनरावृत्ति का उपयोग किए बिना नोड्स को एक द्विआधारी पेड़ में फंसाने के लिए है। इस प्रकार रैखिक के लिए अंतरिक्ष जटिलता को कम करना।

इनवर्टर ट्रैवर्सल

उदाहरण

मॉरिस ट्रैवर्सल

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. यदि वक्र का बायाँ बच्चा अशक्त प्रिंट मान है जो वक्र में संग्रहीत है और वक्र को सही बच्चा है।
  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

जटिलता विश्लेषण

समय जटिलता

पर), क्योंकि हम बाइनरी ट्री में सभी नोड्स को पार करते हैं। चूँकि N नोड हैं समय जटिलता रैखिक है।

अंतरिक्ष जटिलता

ओ (1), क्योंकि हम समस्या को हल करने के लिए पुनरावृत्ति या स्टैक का उपयोग नहीं कर रहे हैं। हमने निरंतर अंतरिक्ष जटिलता के लिए खाते में चर की एक निरंतर संख्या का उपयोग किया है।

त्राटक ट्रैवराल

उदाहरण

            1

          /    \

        2        3

      /   \

   4        5
1 2 4 5 3
            7

          /   \

       14       21
7 14 21

कलन विधि

  1. एक वर्ग नोड की शुरुआत करें जिसमें नोड से संबंधित चर और संकेत शामिल हैं।
  2. एक फ़ंक्शन बनाएँ MorrisTraversal जो नोड को स्वीकार करता है।
  3. ट्राउजर जबकि नोड शून्य नहीं है।
  4. यदि किसी नोड का बायाँ बच्चा नोड में संग्रहित है, तो यह एक सही बच्चा है और नोड को अपडेट करें।
  5. अन्य नोड प्रकार चर वक्र में नोड के बाएं बच्चे का स्टोर।
  6. ट्रैवस जबकि वक्र का सही बच्चा शून्य नहीं है और नोड के बराबर नहीं है और यह सही बच्चे के रूप में वक्र को अद्यतन करता है।
  7. यदि वक्र का सही बच्चा शून्य या नोड के बराबर है, तो वक्र के सही बच्चे को शून्य और नोड के रूप में अपडेट करें क्योंकि यह एक सही बच्चा है।
  8. एल्स प्रिंट नोड डेटा और वक्र के दाएं बच्चे को नोड और नोड के रूप में अपडेट करें क्योंकि यह एक बाएं बच्चा है।

कोड

मॉरिस ट्रैवर्सल का उपयोग करके एक द्विआधारी पेड़ को पार करने का सी ++ प्रोग्राम

#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

जटिलता विश्लेषण

समय जटिलता

पर), क्योंकि हम बाइनरी ट्री में सभी नोड्स को पार करते हैं। चूँकि N नोड हैं समय जटिलता रैखिक है।

अंतरिक्ष जटिलता

ओ (1), क्योंकि हम समस्या को हल करने के लिए पुनरावृत्ति या स्टैक का उपयोग नहीं कर रहे हैं। हमने निरंतर अंतरिक्ष जटिलता के लिए खाते में चर की एक निरंतर संख्या का उपयोग किया है।