트리 구현 방식 정리

      0
     / \
    1   2
       / \
      3   4

 

1. 인접 리스트 (Adjacency List)

트리를 표현할 때 가장 많이 쓰이는 방식
트리는 본질적으로 방향성이 있는 그래프이므로, 인접 리스트 형태로 표현이 가능함

구현 방식

방식	자료형	특징
2차원 배열	int[][]	입력이 배열 형태로 주어질 때 편리
2차원 리스트	List<List<Integer>>	노드 번호가 연속적일 때 자주 사용
해시맵	Map<Integer, List<Integer>>	노드 번호가 불연속적일 때 적합

(1) 2차원 배열

int[][] tree = {
    {1, 2},  // 0번 노드 자식
    {},      // 1번 노드 자식 없음
    {3, 4},  // 2번 노드 자식
    {},      // 3번 노드 자식 없음
    {}       // 4번 노드 자식 없음
};

(2) 2차원 리스트

int n = 5;
List<List<Integer>> tree = new ArrayList<>();
for (int i = 0; i < n; i++) tree.add(new ArrayList<>());
tree.get(0).add(1);
tree.get(0).add(2);
tree.get(2).add(3);
tree.get(2).add(4);

(3) 해시맵

Map<Integer, List<Integer>> tree = new HashMap<>();
tree.putIfAbsent(0, new ArrayList<>());
tree.get(0).add(1);
tree.get(0).add(2);

tree.putIfAbsent(2, new ArrayList<>());
tree.get(2).add(3);
tree.get(2).add(4);

 

2. 간선 리스트 (Edge List)

트리를 부모-자식 간 연결(간선)만 저장하는 방식
입력이 보통 간선 리스트로 제공되므로, 이를 인접 리스트로 변환해 사용함.

int[][] edges = {
    {0, 1},
    {0, 2},
    {2, 3},
    {2, 4}
};

변환 예시 (2차원 리스트)

List<List<Integer>> tree = new ArrayList<>();
for (int i = 0; i < n; i++) tree.add(new ArrayList<>());
for (int[] edge : edges) tree.get(edge[0]).add(edge[1]);

변환 예시 (해시맵)

Map<Integer, List<Integer>> tree = new HashMap<>();
for (int[] edge : edges) {
    tree.putIfAbsent(edge[0], new ArrayList<>());
    tree.get(edge[0]).add(edge[1]);
}

*해시맵으로 구현 시 자식이 없는 노드는 키가 없을 수 있으므로 getOrDefault(key, Collections.emptyList())로 안전하게 접근

3. 클래스 기반 이진 트리 (Binary Tree)

각 노드가 최대 두 개의 자식을 가지는 트리
구현이 직관적이고 다양한 문제에서 사용된다.

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
    TreeNode(int value) { this.value = value; }
}

순회 예시

System.out.println(root.left);
System.out.println(root.right);

 

4. 클래스 기반 일반 트리 (N-ary Tree)

자식 노드의 수가 정해져 있지 않은 일반 트리
자식들을 List로 관리

class TreeNode {
    int value;
    List<TreeNode> children;
    TreeNode(int value) {
        this.value = value;
        this.children = new ArrayList<>();
    }
}

순회 예시

for (TreeNode child : root.children) {
    System.out.println(child.value);
}

 

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

완전 이진 트리는 배열로 표현하면 효율적

int[] tree = {0, 1, 2, -1, -1, 3, 4}; // -1: 비어 있는 노드

인덱스 관계

• 왼쪽 자식: 2*i + 1
• 오른쪽 자식: 2*i + 2
• 부모: (i - 1) / 2

6. 배열로 자식 정보 표현

int[][] links = {
    {-1, -1}, // 0번 자식 없음
    {-1, -1}, // 1번 자식 없음
    {-1, 0},  // 2번 오른쪽 자식 → 0
    {2, 1}    // 3번 왼쪽 자식 → 2, 오른쪽 자식 → 1
};