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


Ниво на трудност M
Често задавани в Амазонка Facebook Fourkites Google 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. Създайте функция MorrisTraversal, която приема коренния възел.
  3. Ако коренът е нула, върнете.
  4. Задайте референтен curr като корен. Преминаване, докато 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

Програма 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

Анализ на сложността

Сложност във времето

НА), защото обхождаме всички възли в двоичното дърво. Тъй като има N възли, сложността на времето е линейна.

Вижте също
Изградете BST от даденото му обръщане на ниво ниво

Сложност на пространството

O (1), защото не използваме рекурсия или стек за решаване на проблема. Използвали сме постоянен брой променливи, които отчитат постоянната сложност на пространството.

Обръщане на предварителна поръчка  

Пример

            1

          /    \

        2        3

      /   \

   4        5
1 2 4 5 3
            7

          /   \

       14       21
7 14 21

алгоритъм

  1. Инициализирайте възел на клас, който съдържа променливи и указатели, свързани с възел.
  2. Създайте функция MorrisTraversal, която приема възел.
  3. Преминаване, докато възелът не е нула.
  4. Ако лявото дете на възел е нулева стойност за печат, съхранявано в node и актуализира възел, тъй като е дясно дете.
  5. В противен случай се съхранява лявото дете на възел в друга променлива curr от тип Node.
  6. Преминаване, докато дясното дете на curr не е нула или не е равно на възела и актуализирайте curr, тъй като е правилно дете.
  7. Ако дясното дете на curr е null или е равно на възела, актуализирайте правилното дете на 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

Програма 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

Анализ на сложността

Сложност във времето

НА), защото обхождаме всички възли в двоичното дърво. Тъй като има N възли, сложността на времето е линейна.

Вижте също
Оценка на Postfix Expression

Сложност на пространството

O (1), защото не използваме рекурсия или стек за решаване на проблема. Използвали сме постоянен брой променливи, които отчитат постоянната сложност на пространството.