ਮੌਰਿਸ ਟ੍ਰਾਵਰਸਲ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਦਰਮਿਆਨੇ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ ਫੇਸਬੁੱਕ ਫੋਰਕਾਈਟਸ ਗੂਗਲ Microsoft ਦੇ
ਟ੍ਰੀ ਟ੍ਰੀ ਟ੍ਰੈਵਲ

ਮੌਰਿਸ ਟ੍ਰਾਵਰਸਲ ਇਕ ਬਾਈਨਰੀ ਰੁੱਖ ਵਿਚ ਨੋਡਾਂ ਨੂੰ ਸਟੈਕ ਅਤੇ ਦੁਬਾਰਾ ਵਰਤੇ ਬਿਨਾਂ ਪਾਰ ਕਰਨ ਦਾ ਇਕ ਤਰੀਕਾ ਹੈ. ਇਸ ਤਰ੍ਹਾਂ ਸਪੇਸ ਦੀ ਗੁੰਝਲਤਾ ਨੂੰ ਰੇਖਿਕ ਬਣਾਉਂਦਾ ਹੈ.

ਅੰਦਰੂਨੀ ਟ੍ਰਾਵਰਸਾਲ

ਉਦਾਹਰਨ

ਮੌਰਿਸ ਟ੍ਰਾਵਰਸਲ

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 ਨੂੰ ਰੂਟ ਦੇ ਤੌਰ ਤੇ ਸੈੱਟ ਕਰੋ. ਟ੍ਰਾਵਰਸ, ਜਦਕਿ ਕਰਰ ਖਾਲੀ ਨਹੀਂ ਹੁੰਦਾ.
  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. ਇਕ ਹੋਰ ਨੋਡ ਕਿਸਮ ਦੇ ਵੇਰੀਏਬਲ ਕਰਰ ਵਿਚ ਇਕ ਨੋਡ ਦਾ ਬੱਚਾ ਬਚਦਾ ਹੈ.
  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), ਕਿਉਂਕਿ ਅਸੀਂ ਸਮੱਸਿਆ ਨੂੰ ਹੱਲ ਕਰਨ ਲਈ ਦੁਹਰਾਓ ਜਾਂ ਸਟੈਕ ਦੀ ਵਰਤੋਂ ਨਹੀਂ ਕਰ ਰਹੇ ਹਾਂ. ਅਸੀਂ ਨਿਰੰਤਰ ਪਰਿਵਰਤਨ ਦੀ ਵਰਤੋਂ ਕੀਤੀ ਹੈ ਜੋ ਨਿਰੰਤਰ ਸਪੇਸ ਗੁੰਝਲਦਾਰਤਾ ਲਈ ਖਾਤੇ.