پیمایش موریس


سطح دشواری متوسط
اغلب در آمازون فیس بوک فورکایت گوگل مایکروسافت
درخت عبور از درخت

پیمایش موریس روشی است برای عبور از گره ها در یک درخت باینری بدون استفاده از پشته و بازگشت. بنابراین پیچیدگی فضا را به خطی کاهش می دهد.

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. یک تابع MorrisTraversal ایجاد کنید که گره ریشه را بپذیرد.
  3. اگر ریشه پوچ است ، برگردید.
  4. curr مرجع را به عنوان root تنظیم کنید. عبور در حالی که curr پوچ نیست.
  5. اگر فرزند سمت چپ curr مقدار خالی چاپ را در curr ذخیره کرده و curr را به عنوان فرزند مناسب به روز کنید.
  6. curr را به عنوان گره راست از گره راست ترین زیر شاخه سمت چپ آن به روز کنید و curr را به عنوان فرزند چپ curr به روز کنید.

رمز

برنامه C ++ برای عبور از یک درخت باینری با استفاده از Morris Traversal

#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

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 وجود دارد ، پیچیدگی زمان خطی است.

پیچیدگی فضا

O (1) ، زیرا ما برای حل مشکل از بازگشت یا پشته استفاده نمی کنیم. ما از تعداد ثابت متغیرهایی استفاده کرده ایم که پیچیدگی فضا را ثابت می کنند.

پیش خرید پیمایش

مثال

            1

          /    \

        2        3

      /   \

   4        5
1 2 4 5 3
            7

          /   \

       14       21
7 14 21

الگوریتم

  1. گره کلاس را که شامل متغیرها و اشاره گرهای مربوط به یک گره است ، ابتدا شروع کنید.
  2. یک تابع MorrisTraversal ایجاد کنید که گره را بپذیرد.
  3. عبور کنید در حالی که گره صفر نیست.
  4. اگر فرزند چپ گره مقدار چاپی null ذخیره شده در گره باشد و گره را به عنوان فرزند مناسب به روز کنید.
  5. فروشگاه Else فرزند گره را در curr دیگر متغیر نوع Node باقی می گذارد.
  6. عبور کنید در حالی که فرزند مناسب curr تهی یا برابر گره نیست و curr را به عنوان فرزند مناسب به روز کنید.
  7. اگر فرزند راست curr تهی یا برابر با گره است ، کودک راست curr را به عنوان null و node را به عنوان فرزند مناسب به روز کنید.
  8. داده های گره را چاپ کنید و فرزند راست curr را به عنوان گره و گره را به عنوان فرزند چپ به روز کنید.

رمز

برنامه C ++ برای عبور از یک درخت باینری با استفاده از Morris Traversal

#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

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 وجود دارد ، پیچیدگی زمان خطی است.

پیچیدگی فضا

O (1) ، زیرا ما برای حل مشکل از بازگشت یا پشته استفاده نمی کنیم. ما از تعداد ثابت متغیرهایی استفاده کرده ایم که پیچیدگی فضا را ثابت می کنند.