मोरिस ट्राभर्सल


कठिनाई तह मध्यम
बारम्बार सोधिन्छ अमेजन फेसबुक फोरकाइट्स गुगल माइक्रोसफ्ट
ट्री रूख ट्राभर्सल

मोरिस ट्राभर्सल स्ट्याक र रिकर्सन प्रयोग नगरी बाइनरी रूखमा नोडहरू पार गर्ने एक विधि हो। यसैले ठाँउ जटिलता लाई लिनियर गर्न।

Inorder Traversal

उदाहरणका

मोरिस ट्राभर्सल

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. मूल करीव सन्दर्भ curr सेट गर्नुहोस्। ट्र्याभर्स जबकि curr खाली छैन।
  5. यदि curr को बायाँ बच्चा curr मा भण्डार गरिएको शून्य प्रिन्ट मान हो र curr अपडेट गर्नुहोस् किनकि यो सहि बच्चा हो।
  6. अर्को अपडेट curr को दायाँ नोड को दायाँ नोड को रूप मा यसको बाँया subtree को अपडेट र curr को बायाँ बच्चाको रूपमा अपडेट गर्नुहोस्।

कोड

सी ++ प्रोग्राम मोरिस ट्राभर्सल प्रयोग गरी बाइनरी रूख पार गर्न

#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

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

समय जटिलता

O (N), किनभने हामी बाइनरी रूखमा सबै नोडहरू पार गर्दछौं। त्यहाँ एन नोडहरू हुनाले समय जटिलता रेखीय हुन्छ।

ठाउँ जटिलता

O (१), किनभने हामी समस्या समाधान गर्न रिकर्सन वा स्ट्याक प्रयोग गरिरहेको छैन। हामीले भेरियबल्सको स्थिर संख्या प्रयोग गर्‍यौं जुन स्थिर ठाउँ जटिलताको लागि खाता हो।

प्रिअर्डर ट्राभर्सल

उदाहरणका

            1

          /    \

        2        3

      /   \

   4        5
1 2 4 5 3
            7

          /   \

       14       21
7 14 21

अल्गोरिदम

  1. एउटा क्लास नोड सुरू गर्नुहोस् जसले नोडसँग सम्बन्धित चर र पोइन्टर्स समावेश गर्दछ।
  2. फंक्शन मोरिसट्राभर्सल सिर्जना गर्नुहोस् जसले नोड स्वीकार गर्दछ।
  3. नोड शून्य छैन जबकि ट्रान्सभर्स।
  4. यदि एक नोडको बायाँ बच्चा नलमा भण्डार गरिएको छ र नोड अपडेट गर्नुहोस् नोडको रूपमा यो सहि बच्चा हो।
  5. अर्को भण्डारले नोडको अर्को बाँच्ने बच्चा अर्को नोड प्रकार भ्यारीएबल कर्सरमा राख्दछ।
  6. ट्र्याभर्स जबकि कर्सरको दाँया बच्चा नल हुँदैन वा नोडको बराबर छैन र कर्सर अपडेट गर्नुहोस् किनकि यो सहि बच्चा हो।
  7. यदि curr को दाँया बच्चा नोड वा नोडको बराबर छ भने, curr को दायाँ बच्चा शून्य र नोडको रूपमा अपडेट गर्नुहोस् किनकि यो सहि बच्चा हो।
  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

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

समय जटिलता

O (N), किनभने हामी बाइनरी रूखमा सबै नोडहरू पार गर्दछौं। त्यहाँ एन नोडहरू हुनाले समय जटिलता रेखीय हुन्छ।

ठाउँ जटिलता

O (१), किनभने हामी समस्या समाधान गर्न रिकर्सन वा स्ट्याक प्रयोग गरिरहेको छैन। हामीले भेरियबल्सको स्थिर संख्या प्रयोग गर्‍यौं जुन स्थिर ठाउँ जटिलताको लागि खाता हो।