트리 노드 데이터 모델

N-ary 트리 구조를 표현하기 위해 식별자, 레이블, 그리고 하위 노드 컬렉션을 필드로 구성한다. 불변성을 유지하면서 안전한 객체 생성이 가능하도록 생성자 기반 초기화 방식을 채택한다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class TreeNode {
    private final String identifier;
    private final String label;
    private final List<TreeNode> descendants;

    public TreeNode(String identifier, String label) {
        this.identifier = identifier;
        this.label = label;
        this.descendants = new ArrayList<>();
    }

    public void attachChild(TreeNode child) {
        this.descendants.add(child);
    }

    public String getIdentifier() { return identifier; }
    public String getLabel() { return label; }
    public List<TreeNode> getDescendants() { 
        return Collections.unmodifiableList(descendants); 
    }

    @Override
    public String toString() {
        return String.format("[%s:%s]", identifier, label);
    }
}

재귀 호출을 활용한 순회 로직

재귀 방식은 시스템 호출 스택이 실행 흐름과 상태 보존을 자동으로 관리한다. 현재 노드를 출력한 후 하위 컬렉션의 각 요소에 대해 메서드를 재호출하는 전위 순회 구조를 취한다.

import java.util.List;

public class RecursiveTraverser {
    private static int executionStep = 0;

    public static void traverse(TreeNode node) {
        logState("재귀 실행 큐", List.of(node));
        emitNode(node);

        List<TreeNode> children = node.getDescendants();
        if (!children.isEmpty()) {
            for (TreeNode child : children) {
                traverse(child);
            }
        }
    }

    private static void emitNode(TreeNode node) {
        System.out.println(node.getIdentifier() + " :: " + node.getLabel());
    }

    private static void logState(String phase, List<TreeNode> queue) {
        executionStep++;
        System.out.printf("Step %d | %s : %s%n", executionStep, phase, queue);
    }
}

명시적 자료구조를 이용한 반복문 전환

재귀 로직을 반복 구조로 치환하려면 호출 스택의 역할을 대신할 명시적 저장소가 필요하다. java.util.Deque를 LIFO 스택으로 활용하여 노드를 관리한다. 루프 내에서 최상위 노드를 추출하여 처리하고, 자식 노드들을 역순으로 스택에 적재함으로써 재귀와 동일한 순회 경로를 구현한다. 이 방식은 깊이가 깊은 트리에서도 스택 오버플로우를 방지할 수 있다.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class IterativeTraverser {
    private static int executionStep = 0;

    public static void traverse(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            List<TreeNode> snapshot = new ArrayList<>(stack);
            logState("반복 실행 스택", snapshot);

            TreeNode current = stack.pop();
            emitNode(current);

            List<TreeNode> children = current.getDescendants();
            for (int i = children.size() - 1; i >= 0; i--) {
                stack.push(children.get(i));
            }
        }
    }

    private static void emitNode(TreeNode node) {
        System.out.println(node.getIdentifier() + " :: " + node.getLabel());
    }

    private static void logState(String phase, List<TreeNode> stack) {
        executionStep++;
        System.out.printf("Step %d | %s : %s%n", executionStep, phase, stack);
    }
}

테스트 환경 구성 및 실행 결과

동일한 트리 형상을 생성하여 두 가지 접근법의 동작 흐름을 비교한다. 루트 노드에 두 개의 직계 자식을 연결하고, 첫 번째 자식에만 추가 하위 노드를 할당하여 비대칭 구조를 만든다.

public class TraversalDemo {
    public static void main(String[] args) {
        TreeNode root = constructTestTree();

        System.out.println("=== 재귀 기반 순회 ===");
        RecursiveTraverser.traverse(root);

        System.out.println("\n=== 반복문 기반 순회 ===");
        IterativeTraverser.traverse(root);
    }

    private static TreeNode constructTestTree() {
        TreeNode n001 = new TreeNode("001", "루트");
        TreeNode n002 = new TreeNode("002", "자식 A");
        TreeNode n003 = new TreeNode("003", "자식 B");
        TreeNode n004 = new TreeNode("004", "손자 A1");

        n002.attachChild(n004);
        n001.attachChild(n002);
        n001.attachChild(n003);

        return n001;
    }
}

=== 재귀 기반 순회 ===
Step 1 | 재귀 실행 큐 : [[001:루트]]
001 :: 루트
Step 2 | 재귀 실행 큐 : [[002:자식 A]]
002 :: 자식 A
Step 3 | 재귀 실행 큐 : [[004:손자 A1]]
004 :: 손자 A1
Step 4 | 재귀 실행 큐 : [[003:자식 B]]
003 :: 자식 B

=== 반복문 기반 순회 ===
Step 1 | 반복 실행 스택 : [[001:루트]]
001 :: 루트
Step 2 | 반복 실행 스택 : [[002:자식 A], [003:자식 B]]
002 :: 자식 A
Step 3 | 반복 실행 스택 : [[004:손자 A1], [003:자식 B]]
004 :: 손자 A1
Step 4 | 반복 실행 스택 : [[003:자식 B]]
003 :: 자식 B