21. 트리 순회 (Tree Traversal)

  트리 구조의 탐색 앞서 이분 매칭에서 배운 대로 매우 유리하다. 반면에 순회 방법은 조금 복잡하다. 일정 조건에 의해 설계된 트리 구조는 자식 노드에 대한 조건이 명확하다면 내가 원하는 값을 쉽게 찾아낼 수 있다. 하지만, 트리구조 전체를 탐색하게 된다면 얘기가 조금 달라진다. 모든 노드를 방문하기 위해서는 트리 구조를 탐색하는 일정 조건이 필요하다. 트리 구조를 유지보수하는데 있어 순회 방법에 대한 정의는 필수적으로 필요하다. 이번 시간에는 트리 구조의 순회 방법에 대해 한번 알아보도록하자. 순회 방법을 쉽게 알 수 있게 이진 트리라는 조건으로 알아보지만, 다른 트리 구조에서도 충분히 적용할 수 있다.

1. 전위 순회 (Pre-order Traversal)

  전위 순회의 시작 점은 루트 노드이다. 루트 노드의 왼쪽 자식 부터 방문하게 되고. 그다음 오른쪽 자식을 만나는 구조다. 순회에서 중요한 것은 새로운 노드로 이동하게 된다면 해당 노드에 다시 전위 순회를 적용 시킨다. 아래의 트리 구조를 한번 살펴보자.

  위의 트리를 살펴보면 12번 시작 노드에서 시작해서 좌측 자식 노드인 8번 노드로 이동하게 된다. 그 다음 8번 노드에서 다시 전위 순회 방식을 적용하게 되어 1번 노드로 이동하게 된다. 1번 노드의 경우 왼쪽 자신 노드가 없으므로 8번 노드에서 방문하려고 했던 우측 자식 노드인 11번을 순서대로 방문한다. 그 다음 다시 12번 노드에서 가야되었던 우측 자식 노드인 25번 노드로 이동한다. 이와 같은 순서대로 이동하게 된다면 아래와 같은 순서로 이동한다.

12 -> 8 -> 1 -> 11 -> 25 -> 19 -> 27

2. 중위 순회 (In-order Traversal)

  중위 순회의 경우 트리의 왼쪽 자식 노드를 방문한 뒤 탐색하려는 노드를 방문하고 우측 자식 노드를 방문하는 구조이다. 위의 노드를 기준으로 다시 한번 살펴보자. 트리는 기본적으로 루트 노드에서 시작하게 된다. 루트 노드에서 탐색을 시작하기 위해 좌측 자식 노드인 8번 노드로 이동한다. 8번 노드 역시 좌측 자식 노드가 존재하므로 1번 노드까지 이동하게 된다. 따라서, 첫번 째 방문 노드는 1번 노드이고, 그 다음 8번 노드로 이동한다. 그리고 우측 자식 노드인 11번으로 이동한다. 8번 노드에 대한 탐색이 끝났으니 다시 1번 노드로 올라가서 탐색을 진행하고 오른쪽 자식 노드 방향으로 이동하고, 25번에 대한 중위 순회를 진행하게 되므로 19, 25, 27 순서대로 방문한다.

1 -> 8 -> 11 -> 12 -> 19 -> 25 -> 27

 3. 후위 순회 (Post-order Traversal)

  후위 순회는 방문하려는 노드를 가장 마지막에 방문하는 방식이다. 좌측 자식 노드, 우측 자식 노드를 방문 한 다음 자신을 방문하는 구조다. 위의 트리에서 살펴보면 루트에서 시작해 좌측 서브트리로 이동한다. 8번 노드에 도달해서도 좌측으로 이동해 가장 먼저 방문하게 되는 노드는 1번 노드가 된다. 그 다음 우측 자식 노드인 11번으로 이동한다. 좌측, 우측을 모두 방문한 다음 상위 노드인 8번으로 이동하게 된다. 이제 다시 1번 노드 지점으로 돌아오게 되고 1번 노드의 우측 서브트리로 이동해 후위 순회를 진행한다.

1 -> 11 -> 8 -> 19 -> 27 -> 25 -> 12

  트리 순회의 대표적인 3가지 방법이다. 트리 순회의 코드는 그리 어렵지 않으므로 직접 고민해보는 것도 좋은 방법이다. 아래 이진 트리 작성과 순회 방법에 대한 코딩을 첨부해 두었다.

import java.util.*;
 
class Node{
    // 데이터 선언
    private int data;
    private Node left;
    private Node right;
    
    // Constructor
    public Node(int data){
        this.setData(data);
        setRight(null);
        setLeft(null);
    }
    
    // getter, setter
    public int getData() {return data;}
    public void setData(int data) {this.data = data;}
    public Node getLeft() {return left;}
    public void setLeft(Node left) {this.left = left;}
    public Node getRight() {return right;}
    public void setRight(Node right) {this.right = right;}
}
 
public class Solution {
 
    public static Node root; 
    
    public static void insert(int data){
        Node node = new Node(data);
        
        if(root == null){
            root = node;
            return;
        }
        
        Node current = root;
        Node temp = current;
        while(true){
            if(current.getData()>data){
                current = current.getLeft();
                if(current == null){
                    temp.setLeft(node);
                    return;
                }
                temp = current;
            }
            else if(current.getData()<data){
                current = current.getRight();
                if(current == null){
                    temp.setRight(node);
                    return;
                }
                temp = current;
            }
            else{
                System.out.println("중복된 값입니다.");
                return;
            }
        }
        
    }
    
    public static void preorder(Node node){
        
        if (node == null){
            return;
        }
        
        System.out.println(node.getData());
        
        preorder(node.getLeft());
        
        preorder(node.getRight());
        
    }
    
    public static void inorder(Node node){
        
        if (node == null){
            return;
        }
        
        inorder(node.getLeft());
        
        System.out.println(node.getData());
        
        inorder(node.getRight());
        
    }
    
    public static void postorder(Node node){
        
        if (node == null){
            return;
        }
        
        postorder(node.getLeft());
        
        postorder(node.getRight());
 
        System.out.println(node.getData());
        
    }
 
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        // 데이터 입력
        insert(12);
        insert(8);
        insert(25);
        insert(1);
        insert(11);
        insert(19);
        insert(27);
        
        System.out.println("Preorder");
        preorder(root);
        
        System.out.println("Inorder");
        inorder(root);
        
        System.out.println("Postorder");
        postorder(root);
                
    }
    
    
}