트리의 재귀

1. 트리의 재귀적 정의

트리는 계층 구조를 가진 대표적인 비선형 자료구조

트리는 다음과 같이 재귀적으로 정의할 수 있다.

1. 노드가 전혀 없는 구조(빈 트리)도 트리이다.
2. 노드가 하나만 있는 경우(루트 노드만 있는 경우)도 트리이다.
3. 루트 노드 아래에 0개 이상의 자식 노드가 있고, 각 자식 노드 또한 트리라면 전체도 트리이다.

즉, 트리는 “하나의 노드 + 그 노드의 하위 트리(서브트리)” 구조로 표현된다.

서브트리(Subtree)

트리의 임의의 노드를 루트로 생각했을 때, 그 노드와 연결된 모든 하위 노드를 포함한 부분 구조를 서브트리라고 한다.

예:

    A
   / \
  B   C
 / \
D   E

• B를 루트로 생각하면 다음과 같은 서브트리가 된다.

   B
  / \
 D   E

이처럼 트리는 트리 안에 또 다른 트리가 포함된 재귀 구조를 가지고 있다.

2. 트리와 재귀 탐색

트리는 부모-자식 관계를 기반으로 하며, 부모가 하는 일을 자식도 반복한다는 성질을 가지고 있다.
이 특성 때문에 트리 탐색은 재귀(Recursion) 방식으로 구현하기에 매우 적합하다!

재귀 탐색 기본 원리

• 부모 노드에서 수행하는 작업은 자식 노드에도 동일하게 적용된다.
• 각 노드의 하위 구조도 또 다른 트리이므로, 재귀 호출을 통해 쉽게 순회할 수 있다.
• 서브트리 단위로 문제를 나누면 설계가 단순해진다.

3. 기본 탐색 알고리즘 (DFS)

트리를 순회할 때 가장 흔히 사용하는 방법은 깊이 우선 탐색(DFS, Depth-First Search)이다.

수도코드

FUNCTION dfs(node):
    IF node IS NULL:
        RETURN
    PROCESS(node)  // 현재 노드 처리
    FOR each child IN node.children:
        dfs(child) // 자식 노드 탐색

 

일반 트리 구현 예시

class Node {
    int value;
    List<Node> children = new ArrayList<>();

    Node(int value) {
        this.value = value;
    }
}

public class TreeDFS {
    public static void dfs(Node node) {
        System.out.println(node.value); // 현재 노드 처리
        for (Node child : node.children) {
            dfs(child); // 자식 노드 탐색
        }
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);

        root.children.add(node2);
        root.children.add(node3);
        node2.children.add(node4);
        node2.children.add(node5);

        System.out.println("DFS 순회 결과:");
        dfs(root);
    }
}

 

이진 트리 구현 예시

class Node {
    int value;
    Node left;
    Node right;

    Node(int value) {
        this.value = value;
    }
}

public class BinaryTreeDFS {
    public static void dfs(Node node) {
        if (node == null) return;
        System.out.println(node.value); // 현재 노드 처리
        dfs(node.left);
        dfs(node.right);
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);

        System.out.println("DFS 순회 결과:");
        dfs(root);
    }
}

 

4. 그래프 형태의 트리 탐색

4-1. 무방향 트리 (양방향 인접 리스트)

무방향 간선이 있는 트리는 부모로 되돌아가지 않도록 visited 집합 또는 parent 매개변수를 사용한다.

visited 사용 예시:

static Map<Integer, List<Integer>> tree = Map.of(
    1, List.of(2, 3),
    2, List.of(1, 4, 5),
    3, List.of(1),
    4, List.of(2),
    5, List.of(2)
);

static void dfs(int cur, Set<Integer> visited) {
    System.out.println(cur);
    visited.add(cur);
    for (int nxt : tree.get(cur)) {
        if (!visited.contains(nxt)) dfs(nxt, visited);
    }
}

 

4-2. 방향 트리 (부모 → 자식)

부모에서 자식으로만 간선이 존재한다면, 별도의 방문 처리 없이 재귀 호출만으로 탐색할 수 있다.

static Map<Integer, List<Integer>> tree = Map.of(
    1, List.of(2, 3),
    2, List.of(4, 5),
    3, List.of(),
    4, List.of(),
    5, List.of()
);

static void dfs(int cur) {
    System.out.println(cur);
    for (int nxt : tree.get(cur)) dfs(nxt);
}

 

5. 배열 기반 트리 (완전 이진 트리)

완전 이진 트리나 힙은 배열 인덱스로 표현할 수 있다.

• 왼쪽 자식 = 2 * i + 1
• 오른쪽 자식 = 2 * i + 2

int[] tree = {1, 2, 3, 4, 5, -1, -1};

static void dfs(int idx) {
    if (idx >= tree.length || tree[idx] == -1) return;
    System.out.println(tree[idx]);
    dfs(2 * idx + 1); // 왼쪽 자식
    dfs(2 * idx + 2); // 오른쪽 자식
}