[java] 스택을 이용한 트리의 깊이 우선 탐색 구현하기

05 Dec 2023

java

트리 구조에서 깊이 우선 탐색(Depth First Search)은 트리의 노드를 한 방향으로 탐색하면서 그래프의 깊이를 우선으로 탐색하는 방법입니다. 이번에는 자바의 스택(Stack)을 이용하여 트리의 깊이 우선 탐색을 구현해보겠습니다.

트리 구조 정의하기

먼저, 트리 구조를 정의해보겠습니다. 각 노드는 값을 갖고 자식 노드들을 가질 수 있습니다. 이를 위해 TreeNode 클래스를 생성합니다.

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

이제 트리를 구성하기 위해 샘플 데이터를 사용하겠습니다.

TreeNode rootNode = new TreeNode(1);
rootNode.left = new TreeNode(2);
rootNode.right = new TreeNode(3);
rootNode.left.left = new TreeNode(4);
rootNode.left.right = new TreeNode(5);

스택을 이용한 깊이 우선 탐색 구현하기

이제 스택을 이용하여 트리의 깊이 우선 탐색을 구현해보겠습니다. 스택에는 탐색할 노드들이 저장됩니다.

import java.util.Stack;

void dfs(TreeNode node) {
    if (node == null) {
        return;
    }

    Stack<TreeNode> stack = new Stack<>();
    stack.push(node);

    while (!stack.isEmpty()) {
        TreeNode currNode = stack.pop();
        System.out.println(currNode.val);

        if (currNode.right != null) {
            stack.push(currNode.right);
        }

        if (currNode.left != null) {
            stack.push(currNode.left);
        }
    }
}

위의 코드는 깊이 우선 탐색을 수행하는 dfs 메소드입니다. 노드가 null일 경우 탐색을 종료하고, 그렇지 않은 경우 스택에 노드를 추가합니다. 스택이 비어있지 않은 동안 스택에서 노드를 꺼내고, 해당 노드의 값을 출력합니다.

또한, 스택에 오른쪽 자식 노드를 먼저 추가하고 왼쪽 자식 노드를 추가함으로써 깊이 우선 탐색을 구현했습니다.

트리의 깊이 우선 탐색 실행하기

위에서 정의한 트리와 dfs 메소드를 사용하여 깊이 우선 탐색을 실행해보겠습니다.

dfs(rootNode);

실행 결과는 다음과 같습니다.

이처럼 스택을 이용하여 트리의 깊이 우선 탐색을 구현할 수 있습니다.

트리 구조 정의하기

스택을 이용한 깊이 우선 탐색 구현하기

트리의 깊이 우선 탐색 실행하기

참고 자료