ಮೋರಿಸ್ ಟ್ರಾವೆರ್ಸಲ್


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ ಫೇಸ್ಬುಕ್ ಫೋರ್‌ಕೈಟ್‌ಗಳು ಗೂಗಲ್ ಮೈಕ್ರೋಸಾಫ್ಟ್
ಮರ ಟ್ರೀ ಟ್ರಾವೆರ್ಸಲ್

ಮೋರಿಸ್ ಟ್ರಾವೆರ್ಸಲ್ ಎನ್ನುವುದು ಸ್ಟಾಕ್ ಮತ್ತು ಪುನರಾವರ್ತನೆಯನ್ನು ಬಳಸದೆ ಬೈನರಿ ಮರದಲ್ಲಿ ನೋಡ್ಗಳನ್ನು ಹಾದುಹೋಗುವ ಒಂದು ವಿಧಾನವಾಗಿದೆ. ಹೀಗಾಗಿ ಜಾಗದ ಸಂಕೀರ್ಣತೆಯನ್ನು ರೇಖೀಯಕ್ಕೆ ಇಳಿಸುತ್ತದೆ.

ಇನಾರ್ಡರ್ ಟ್ರಾವೆರ್ಸಲ್

ಉದಾಹರಣೆ

ಮೋರಿಸ್ ಟ್ರಾವೆರ್ಸಲ್

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

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್), ಏಕೆಂದರೆ ನಾವು ಬೈನರಿ ಮರದ ಎಲ್ಲಾ ನೋಡ್‌ಗಳನ್ನು ಹಾದುಹೋಗುತ್ತೇವೆ. ಎನ್ ನೋಡ್‌ಗಳು ಇರುವುದರಿಂದ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ರೇಖೀಯವಾಗಿರುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (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

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್), ಏಕೆಂದರೆ ನಾವು ಬೈನರಿ ಮರದ ಎಲ್ಲಾ ನೋಡ್‌ಗಳನ್ನು ಹಾದುಹೋಗುತ್ತೇವೆ. ಎನ್ ನೋಡ್‌ಗಳು ಇರುವುದರಿಂದ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ರೇಖೀಯವಾಗಿರುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (1), ಏಕೆಂದರೆ ನಾವು ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ಪುನರಾವರ್ತನೆ ಅಥವಾ ಸ್ಟಾಕ್ ಅನ್ನು ಬಳಸುತ್ತಿಲ್ಲ. ಸ್ಥಿರ ಸ್ಥಳಾವಕಾಶದ ಸಂಕೀರ್ಣತೆಗೆ ಕಾರಣವಾಗುವ ಸ್ಥಿರ ಸಂಖ್ಯೆಯ ಅಸ್ಥಿರಗಳನ್ನು ನಾವು ಬಳಸಿದ್ದೇವೆ.