트리

1. 트리(Tree)란?

트리는 노드(Node)가 계층적으로 연결된 비선형 자료구조입니다. 최상위에는 루트(Root)가 있고, 각 노드는 0개 이상의 자식 노드를 가진다.

 

비선형 자료구조란?

데이터가 단순히 일렬로 연결되는 것이 아니라 계층적 또는 네트워크 형태로 연결된 구조이다.

2. 트리 관련 기본 용어

• 노드(Node): 트리를 구성하는 기본 단위
• 루트 노드(Root Node): 트리의 시작점, 부모가 없는 노드
• 부모 노드(Parent Node): 다른 노드를 자식으로 가지는 노드
• 자식 노드(Child Node): 특정 부모 노드에 연결된 하위 노드
• 형제 노드(Sibling Node): 같은 부모를 가진 노드들
• 리프 노드(Leaf Node): 자식이 없는 노드(끝점)
• 서브트리(Subtree): 특정 노드를 루트로 하는 부분 트리
• 차수(Degree): 한 노드가 가진 자식의 개수
• 높이(Height): 루트에서 가장 깊은 리프까지의 거리
• 레벨(Level): 루트에서 특정 노드까지의 깊이

3. 트리의 특징

1. 트리는 그래프의 일종 → 방향성이 있는 비순환 그래프(DAG)
2. 간선(Edge)의 개수 = 노드 개수(N) - 1
3. 트리에는 반드시 하나의 루트가 존재

4. 트리 순회(Traversal)

트리는 선형 자료구조(배열, 리스트)와 달리 순회 방법이 여러 가지이다.
대표적으로 BFS(Level Order)와 DFS(Pre-order, In-order, Post-order)가 있다.

BFS (Level-order Traversal)

BFS는 루트부터 시작해 레벨(깊이)별로 탐색하는 방법이다.
→ 큐(Queue)를 이용해 구현한다.

코드 예시

import java.util.*;

class Node {
    int value;
    List<Node> children;

    Node(int value) {
        this.value = value;
        this.children = new ArrayList<>();
    }
}

public class TreeTraversal {

    public static void levelOrder(Node root) {
        if (root == null) return;

        Queue<Node> q = new ArrayDeque<>();
        q.add(root);

        while (!q.isEmpty()) {
            Node curNode = q.remove();
            System.out.println(curNode.value);

            for (Node child : curNode.children) {
                q.add(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);
        node3.children.add(node5);

        levelOrder(root);
    }
}

시간복잡도: 모든 노드를 한 번씩 방문 → O(n)

DFS (깊이 우선 탐색)

DFS는 한 방향으로 깊게 내려가며 탐색하는 방식이다.
순회 순서에 따라 3가지 종류가 있다.

(1) 전위 순회 (Pre-order)

• 방문 → 왼쪽 자식 → 오른쪽 자식

void preorder(Node root) {
    if (root == null) return;
    System.out.println(root.value);
    preorder(root.left);
    preorder(root.right);
}

(2) 중위 순회 (In-order)

• 왼쪽 자식 → 방문 → 오른쪽 자식

void inorder(Node root) {
    if (root == null) return;
    inorder(root.left);
    System.out.println(root.value);
    inorder(root.right);
}

(3) 후위 순회 (Post-order)

• 왼쪽 자식 → 오른쪽 자식 → 방문

void postorder(Node root) {
    if (root == null) return;
    postorder(root.left);
    postorder(root.right);
    System.out.println(root.value);
}

시간복잡도: 모든 노드를 한 번씩 방문 → O(n)