Morris Traversal

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Facebook Fourkites google microsoft
Ağac Ağacın keçidiBaxılıb 79

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Morris traversal, yığın və rekursiya istifadə etmədən ikili ağacdakı qovşaqları keçmək üçün bir üsuldur. Beləliklə məkan mürəkkəbliyini xətti azaldır.

Daxili keçid

misal

Morris TraversalPin

9 7 1 6 4 5 3
            1

          /    \

        2        3

      /   \

   4        5
4 2 5 1 3
            7

          /   \

       14       21
14 7 21

Alqoritm

  1. Düyünlə əlaqəli dəyişənləri və göstəriciləri ehtiva edən bir sinif Node başlatın.
  2. Kök düyünü qəbul edən bir MorrisTraversal funksiyası yaradın.
  3. Kök boşdursa, geri qayıdın.
  4. Referans cərəyanını kök olaraq təyin edin. Cərrah sıfır deyilsə keçin.
  5. Sol curd uşağı boşluqda saxlanılan boş qiymət dəyəridirsə və düzgün bir uşaq olduğu üçün curr-ı yeniləyin.
  6. Başqa bir yeniləmə cərəyanını sol alt ağacının ən sağ qovşağının sağ qovşağı və cərəyanın sol uşağı olaraq yeniləyin.

Kodu

Morris Traversal istifadə edərək ikili bir ağac keçmək üçün C ++ proqramı

#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

Morris Traversal istifadə edərək ikili bir ağac keçmək üçün Java Proqramı

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), çünki ikili ağacdakı bütün qovşaqları keçirik. N düyünü olduğundan zaman mürəkkəbliyi xətti olur.

Kosmik Mürəkkəblik

O (1), çünki problemi həll etmək üçün rekursiya və ya yığından istifadə etmirik. Biz daimi kosmik mürəkkəbliyi hesab edən dəyişənlərin daimi sayını istifadə etdik.

Əvvəlcədən Traversal

misal

            1

          /    \

        2        3

      /   \

   4        5
1 2 4 5 3
            7

          /   \

       14       21
7 14 21

Alqoritm

  1. Düyünlə əlaqəli dəyişənləri və göstəriciləri ehtiva edən bir sinif Node başlatın.
  2. Düyünü qəbul edən bir MorrisTraversal funksiyası yaradın.
  3. Düyün boş deyilsə keçin.
  4. Bir düyünün sol uşağı qovluqda saxlanılan null çap dəyəridirsə və hüququ uşaq olduğu üçün düyünü yeniləsə.
  5. Başqa bir qovşaq növü dəyişən cərəyanında bir qovşağın başqa uşağını saxlayır.
  6. Sağ cərəyan uşağı null deyilsə və ya düyünə bərabər deyilsə, keçin və düzgün uşaq olduğu üçün cərəyanı yeniləyin.
  7. Sağ cərəyan uşağı boş və ya düyünə bərabərdirsə, sağ bala uşağını sıfır və qovşaq kimi yeniləyin.
  8. Başqa bir qovşaq məlumatlarını çap edin və sağ uşağı sol uşaq olduğu üçün qovşaq və qovşaq kimi yeniləyin.

Kodu

Morris Traversal istifadə edərək ikili bir ağac keçmək üçün C ++ proqramı

#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

Morris Traversal istifadə edərək ikili bir ağac keçmək üçün Java Proqramı

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), çünki ikili ağacdakı bütün qovşaqları keçirik. N düyünü olduğundan zaman mürəkkəbliyi xətti olur.

Kosmik Mürəkkəblik

O (1), çünki problemi həll etmək üçün rekursiya və ya yığından istifadə etmirik. Biz daimi kosmik mürəkkəbliyi hesab edən dəyişənlərin daimi sayını istifadə etdik.

Crack Sistemi Dizayn Müsahibələri
Translate »