مورس ٹراورسال


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایمیزون فیس بک فورکائٹس گوگل مائیکروسافٹ
درخت درخت ٹراورسال

موریس ٹراورسال اسٹیک اور تکرار کا استعمال کیے بغیر بائنری درخت میں نوڈس کو عبور کرنے کا ایک طریقہ ہے۔ اس طرح خلا کی پیچیدگی کو لکیری تک کم کرنا۔

انڈر ٹراورسال

مثال کے طور پر

مورس ٹراورسال

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

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (N) ، کیونکہ ہم بائنری ٹری میں موجود تمام نوڈس کو عبور کرتے ہیں۔ چونکہ N نوڈس موجود ہیں اس وقت کی پیچیدگی لکیری ہے۔

خلائی پیچیدگی

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

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (N) ، کیونکہ ہم بائنری ٹری میں موجود تمام نوڈس کو عبور کرتے ہیں۔ چونکہ N نوڈس موجود ہیں اس وقت کی پیچیدگی لکیری ہے۔

خلائی پیچیدگی

O (1) ، کیونکہ ہم مسئلہ کو حل کرنے کے لئے تکرار یا اسٹیک استعمال نہیں کررہے ہیں۔ ہم نے متغیرات کی ایک مستقل تعداد کا استعمال کیا ہے جو جگہ کی مستقل پیچیدگی کا سبب بنتا ہے۔