6. 트리 순회(Traversal)

1. 순회란?

리스트는 그냥 단순 반복문으로 순회를 하면 끝이지만, 트리는 갈림길(왼쪽/오른쪽)이 있어서, "어떤 순서로 방문할지" 규칙을 정해야 한다.

 

가장 대표적인 3가지 방법이 존재한다. (루트, 왼쪽, 오른쪽을 언제 방문하는지에 대한 차이)

 

1. 전위 순회(Pre-order)
   • 설명: Root를 먼저 처리하고 자식들에게 간다.
   • 순서: Root → Left → Right
   • 용도: 트리를 복사할 때 사용한다. (부모를 먼저 만들어야 자식을 붙일 수 있기 때문이다. 쉽게 설명하자면 상위 폴더를 지정해서 그 안에 폴더를 생성할 때처럼..)
2. 중위 순회(In-order) (중요함)
   • 설명: 왼쪽부터 오른쪽으로 간다.
   • 순서: Left → Root → Right
   • 용도: 정렬된 순서로 데이터를 뽑을 때 사용된다. (이진 탐색 트리에서 사용하면 1, 2, 3, 4... 순서대로 나온다.)
3. 후위 순회(Post-order)
   • 자식들을 처리하고 Root를 마지막으로 간다.
   • 순서: Left → Right → Root
   • 용도: 폴더 용량 계산, 트리 삭제 시에 사용된다. (자식들이 다 없어져야 부모도 없어질 수 있기 때문이다.)

 

2. Java 코드 구현

트리 순회는 재귀 함수로 매우 쉽게 구현할 수 있다.

class Node {
    int data;
    Node left, right;
    public Node(int data) { this.data = data; }
}

public class TreeTraversal {
    Node root;

    // 1. 전위 순회 (Root -> L -> R)
    void preOrder(Node node) {
        if (node == null) return; // 더 이상 갈 곳이 없으면 되돌아감 (Base Case)

        System.out.print(node.data + " "); // 1. 나(Root) 출력
        preOrder(node.left);               // 2. 왼쪽으로 가!
        preOrder(node.right);              // 3. 오른쪽으로 가!
    }

    // 2. 중위 순회 (L -> Root -> R)
    void inOrder(Node node) {
        if (node == null) return;

        inOrder(node.left);                // 1. 왼쪽 끝까지 먼저 가!
        System.out.print(node.data + " "); // 2. 돌아오면서 나(Root) 출력
        inOrder(node.right);               // 3. 오른쪽으로 가!
    }

    // 3. 후위 순회 (L -> R -> Root)
    void postOrder(Node node) {
        if (node == null) return;

        postOrder(node.left);              // 1. 왼쪽 먼저!
        postOrder(node.right);             // 2. 오른쪽 먼저!
        System.out.print(node.data + " "); // 3. 마지막에 나(Root) 출력
    }
}