Моррис Траверсал


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Amazon Facebook Фуркайтҳо Google Microsoft
Дарахт Траверсал дарахт

Гузариши Моррис усули убур кардани гиреҳҳо дар дарахти дуӣ бидуни истифодаи стек ва рекурсия мебошад. Ҳамин тариқ, кам кардани мураккабии фазо ба хаттӣ.

Гузариши Inorder

мисол

Моррис Траверсал

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. Ҷараёни истинодро ҳамчун реша таъин кунед. Гузариш ҳангоми curl нул нест.
  5. Агар кӯдаки чапи кунҷ арзиши нули чопи дар ҷараён ҳифзшударо дошта бошад ва ҷарроҳиро навсозӣ кунад, зеро ин фарзанди рост аст.
  6. Курси навсозии дигар ҳамчун гиреҳи рости гиреҳи рости зердарахти чапи он ва навсозӣ ҳамчун фарзанди чапи гард.

рамз

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

Барномаи Java барои убур кардани дарахти дуӣ бо истифода аз 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

Таҳлили мураккабӣ

Мураккабии вақт

O (N), зеро мо ҳамаи гиреҳҳоро дарахти дуӣ убур мекунем. Азбаски N гиреҳ мавҷуд аст, мураккабии вақт хатӣ аст.

Мураккабии фазо

О (1), зеро мо рекурсия ё стекро барои ҳалли мушкилот истифода намебарем. Мо шумораи доимии тағирёбандаҳоро истифода бурдем, ки мураккабии доимии фазоро ҳисоб мекунанд.

Гузариши пешакӣ

мисол

            1

          /    \

        2        3

      /   \

   4        5
1 2 4 5 3
            7

          /   \

       14       21
7 14 21

Алгоритм

  1. Натиҷаи синфи гиреҳро дар бар мегирад, ки дорои тағирёбандаҳо ва нишондиҳандаҳои марбут ба гиреҳ мебошад.
  2. Функсияи MorrisTraversal созед, ки гиреҳро қабул кунад.
  3. Дар ҳоле ки гиреҳ нул нест.
  4. Агар фарзанди чапи гиреҳ арзиши чопи нодуруст дар гиреҳ нигоҳ дошта шуда бошад ва гиреҳро навсозӣ кунад, зеро ин фарзанди рост аст.
  5. Дигар мағоза фарзанди гиреҳро дар гардиши дигари тағирёбандаи навъи гиреҳ нигоҳ медорад.
  6. Гузаред, дар ҳоле ки кӯдаки рости кунҷ ба гиреҳ нул нест ё баробар нест ва ҷараёнро навсозӣ кунед, зеро ин фарзанди рост аст.
  7. Агар фарзанди рости кунҷ ба гиреҳ нул бошад ё ба он баробар бошад, фарзанди рости курро ҳамчун сифр ва гиреҳ навсозӣ кунед, зеро ин фарзанди рост аст.
  8. Дигар маълумоти гиреҳро чоп кунед ва фарзанди рости гардро ҳамчун гиреҳ ва гиреҳ ҳамчун кӯдаки чап навсозӣ кунед.

рамз

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

Барномаи Java барои убур кардани дарахти дуӣ бо истифода аз 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

Таҳлили мураккабӣ

Мураккабии вақт

O (N), зеро мо ҳамаи гиреҳҳоро дарахти дуӣ убур мекунем. Азбаски N гиреҳ мавҷуд аст, мураккабии вақт хатӣ аст.

Мураккабии фазо

О (1), зеро мо рекурсия ё стекро барои ҳалли мушкилот истифода намебарем. Мо шумораи доимии тағирёбандаҳоро истифода бурдем, ки мураккабии доимии фазоро ҳисоб мекунанд.