மோரிஸ் டிராவர்சல்


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது அமேசான் பேஸ்புக் ஃபோர்கைட்டுகள் கூகிள் மைக்ரோசாப்ட்
மரம் மரம் பயணம்

மோரிஸ் டிராவர்சல் என்பது பைனரி மரத்தில் முனைகளை அடுக்கு மற்றும் மறுநிகழ்வைப் பயன்படுத்தாமல் பயணிக்கும் ஒரு முறையாகும். இதனால் விண்வெளி சிக்கலை நேரியல் வரை குறைக்கிறது.

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. குறிப்பு கர்ரை ரூட்டாக அமைக்கவும். கர்ர் பூஜ்யமாக இல்லாதபோது பயணிக்கவும்.
  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. முனை ஏற்றுக்கொள்ளும் மோரிஸ்ட்ராவர்சல் என்ற செயல்பாட்டை உருவாக்கவும்.
  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), ஏனென்றால் சிக்கலைத் தீர்க்க நாங்கள் மறுநிகழ்வு அல்லது அடுக்கைப் பயன்படுத்தவில்லை. நிலையான இட சிக்கலான தன்மையைக் கொண்ட நிலையான மாறிகள் எண்ணிக்கையைப் பயன்படுத்தினோம்.