Morris Traversal


난이도 중급
자주 묻는 질문 아마존 페이스북 서비스 Fourkites 구글 Microsoft
나무 트리 순회

Morris traversal은 스택 및 재귀를 사용하지 않고 이진 트리의 노드를 탐색하는 방법입니다. 따라서 공간 복잡성을 선형으로 줄입니다.

Inorder Traversal

Morris 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. 노드와 관련된 변수와 포인터를 포함하는 클래스 Node를 초기화합니다.
  2. 루트 노드를 받아들이는 MorrisTraversal 함수를 만듭니다.
  3. 루트가 null이면 반환합니다.
  4. 참조 현재를 루트로 설정합니다. curr이 null이 아닌 동안 횡단합니다.
  5. curr의 왼쪽 자식이 null이면 curr에 저장된 값을 인쇄하고 오른쪽 자식이므로 curr을 업데이트합니다.
  6. 그렇지 않으면 curr을 왼쪽 하위 트리의 가장 오른쪽 노드의 오른쪽 노드로 업데이트하고 curr을 curr의 왼쪽 자식으로 업데이트합니다.

암호

Morris Traversal을 사용하여 이진 트리를 탐색하는 C ++ 프로그램

#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을 사용하여 이진 트리를 순회하는 Java 프로그램

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. 노드와 관련된 변수와 포인터를 포함하는 클래스 Node를 초기화합니다.
  2. 노드를 받아들이는 MorrisTraversal 함수를 만듭니다.
  3. 노드가 null이 아닌 동안 트래버스합니다.
  4. 노드의 왼쪽 자식이 null이면 노드에 저장된 값을 인쇄하고 오른쪽 자식으로 노드를 업데이트합니다.
  5. 다른 노드 유형 변수 curr에 노드의 왼쪽 자식을 저장합니다.
  6. curr의 오른쪽 자식이 null이 아니거나 노드와 같지 않을 때 트래버스하고 오른쪽 자식이므로 curr을 업데이트합니다.
  7. curr의 오른쪽 자식이 null이거나 노드와 같으면 curr의 오른쪽 자식을 null로 업데이트하고 노드를 오른쪽 자식으로 업데이트합니다.
  8. 그렇지 않으면 노드 데이터를 인쇄하고 curr의 오른쪽 자식을 노드로 업데이트하고 노드를 왼쪽 자식으로 업데이트합니다.

암호

Morris Traversal을 사용하여 이진 트리를 탐색하는 C ++ 프로그램

#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을 사용하여 이진 트리를 순회하는 Java 프로그램

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), 문제를 해결하기 위해 재귀 나 스택을 사용하지 않기 때문입니다. 우리는 일정한 공간 복잡성을 설명하는 일정한 수의 변수를 사용했습니다.