[java] 트리 순회 알고리즘

04 Dec 2023

java

트리는 계층적인 구조를 가지고 있는 자료구조로, 한 개 이상의 노드로 구성되어 있습니다. 트리 순회 알고리즘은 트리의 모든 노드를 일정한 순서로 방문하는 방법을 의미합니다. 트리 순회 알고리즘은 주로 깊이 우선 탐색(Depth First Search, DFS)과 너비 우선 탐색(Breadth First Search, BFS)로 나뉘어집니다.

깊이 우선 탐색 (DFS)

깊이 우선 탐색은 트리의 루트 노드부터 시작하여 한 노드의 자식 노드를 먼저 탐색하는 방법입니다. 이 방법은 스택(Stack) 자료구조를 이용하여 구현할 수 있습니다.

전위 순회 (Preorder Traversal)

전위 순회는 노드 방문 순서가 “현재 노드 - 왼쪽 서브트리 - 오른쪽 서브트리”인 순서로 방문하는 방법입니다.

public void preorderTraversal(TreeNode node) {
    if (node != null) {
        System.out.println(node.value);
        preorderTraversal(node.left);
        preorderTraversal(node.right);
    }
}

중위 순회 (Inorder Traversal)

중위 순회는 노드 방문 순서가 “왼쪽 서브트리 - 현재 노드 - 오른쪽 서브트리”인 순서로 방문하는 방법입니다.

public void inorderTraversal(TreeNode node) {
    if (node != null) {
        inorderTraversal(node.left);
        System.out.println(node.value);
        inorderTraversal(node.right);
    }
}

후위 순회 (Postorder Traversal)

후위 순회는 노드 방문 순서가 “왼쪽 서브트리 - 오른쪽 서브트리 - 현재 노드”인 순서로 방문하는 방법입니다.

public void postorderTraversal(TreeNode node) {
    if (node != null) {
        postorderTraversal(node.left);
        postorderTraversal(node.right);
        System.out.println(node.value);
    }
}

너비 우선 탐색 (BFS)

너비 우선 탐색은 트리의 레벨 순서대로 방문하는 방법입니다. 이 방법은 큐(Queue) 자료구조를 이용하여 구현할 수 있습니다.

public void levelOrderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.println(node.value);
        
        if (node.left != null) {
            queue.add(node.left);
        }
        
        if (node.right != null) {
            queue.add(node.right);
        }
    }
}

결론

트리 순회 알고리즘은 트리의 구조를 탐색하고 데이터를 처리하는 데 매우 유용합니다. 깊이 우선 탐색과 너비 우선 탐색은 각각 다른 방식으로 노드를 순회하며, 사용자에게 필요한 순회 방식을 선택할 수 있습니다.

참고 문서: