트리 순회(전위, 중위, 후위) - JAVA

트리의 순회 방법에 대해 알아보자!

트리의 순회란 트리 구조의 자료형에서 모든 노드를 한번씩 방문하는 체계적인 방법을 말한다. 대표적으로 본 포스팅에서 다룰 전위순회(preorder[프리오더]), 중위순회(inorder[인오더]), 후위순회(postorder[포스트오더])가 있다. 알고리즘 문제에서 다룰 때 한국어로 다룰때도 있지만 영어 명칭으로 다룰때도 있고 많이 혼용되므로 정확한 명칭을 전무 알아두는 것이 좋다. 이진트리를 기준으로 각 순회방법에 대해 알아보자!

개요

결론부터 말하자면 위의 이미지를 이해하면 된다.

전위순회(preorder)

모든 순회의 시작은 루트노드부터 시작한다. A를 기준으로 B와 그 아래 트리를 왼쪽 서브트리, C 아래를 오른쪽 서브트리라 한다.

전위순회는 현재 노드를 방문하고 왼쪽 서브트리, 오른쪽 서브트리를 차례로 방문하며 각 노드에서 전위 순회를 반복하는 과정이다. 그림에서는 A노트를 방문하고 왼쪽의 B노드에서 전위순회를 하고, C 노드를 전위 순회하는 것이다.

코드로 과정을 살펴보는것이 이해가 빠르다.

class Node{
    int value;
    Node left;
    Node right;
}
void preorder(Node node) {
    // 노드 방문
    System.out.println(node.value);

    // 왼쪽 노드 전위 순회
    if(node.left != null){
        preorder(node.left);
    }

    // 오른쪽 노드 전위 순회
    if(node.right != null){
        preorder(node.right);
    }
}

중위순회(inorder)

중위 순회는 현재 노드를 살펴보기 전에 왼쪽 서브 트리를 먼저 방문하여 중위 순회를 하고, 현재 노드를 방문한 뒤 오른쪽 서브 트리를 중위 순회하는 과정이다.

void inorder(Node node) {
    // 왼쪽 서브 트리 순회
    if(node.left != null){
        inorder(node.left);
    }

    // 노드 방문
    System.out.println(node.value);

    // 오른쪽 서브 트리 순회
    if(node.right != null){
        inorder(node.right);
    }
}

후위순회(postorder)

후위 순회는 왼쪽, 오른쪽 서브트리를 먼저 순회하고 난 뒤 현재 노드를 방문하는 것이다.

void postorder(Node node) {
    // 왼쪽 서브 트리 순회
    if(node.left != null){
        postorder(node.left);
    }

    // 오른쪽 서브 트리 순회
    if(node.right != null){
        postorder(node.right);
    }

    // 노드 방문
    System.out.println(node.value);
}