트리(Tree)와 순회(Traversal) 완전 정리

트리는 계층적 구조를 표현하는 대표적인 비선형 자료구조입니다.
이 글에서는 트리의 기본 개념부터 BFS/DFS 순회 방법까지 코드와 함께 자세히 알아보겠습니다.

---

트리(Tree)의 정의

트리는 노드(Node)와 간선(Edge)으로 구성된 계층적 자료구조입니다.

• 루트 노드(Root): 최상위 노드 (부모가 없음)
• 부모-자식 관계: 상하 연결 구조
• 서브트리(Subtree): 트리 내부에 포함된 작은 트리

🌳 트리는 방향성 비순환 그래프(DAG)의 일종입니다.
간선 수 = 노드 수 - 1, 순환 구조가 없다는 특징이 있습니다.

---

트리 관련 핵심 개념

용어	설명	예시
노드(Node)	트리의 각 요소 (데이터 + 포인터)	A, B, C ...
간선(Edge)	노드 간 연결 선	A-B, B-C
루트(Root)	최상위 노드	트리의 시작점
리프(Leaf)	자식이 없는 최하위 노드	트리의 끝 노드
차수(Degree)	한 노드가 가진 자식 수	2진 트리: 최대 차수 2
레벨(Level)	루트(0)부터의 깊이	레벨 0 → 루트
높이(Height)	루트에서 가장 먼 리프까지의 거리	트리의 최대 깊이

---

트리 순회(Traversal) 방법

트리 순회는 모든 노드를 체계적으로 방문하는 기술입니다.
주요 방법으로 BFS(Level-order)와 DFS(Pre/In/Post-order)가 있습니다.

---

1. BFS (Level-order)

레벨별로 좌→우 방문하는 방식입니다.
큐(Queue)를 사용해 구현하며, 최단 경로 탐색에 유용합니다.

 {
if (root == null) return;

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

while (!q.isEmpty()) {
    Node cur = q.poll();
    System.out.print(cur.value + " ");

    for (Node child : cur.children) {
        q.add(child);
    }
}

}

**실행 결과**: A → B → C → D → E → F → G → H → I → J → K → L  
**시간 복잡도**: O(N) (모든 노드 한 번씩 방문)

---

### 2. DFS (Depth First Search)

한 경로를 끝까지 탐색 후 돌아와 다른 경로를 탐색합니다.  
**재귀** 또는 **스택**으로 구현하며, **전위/중위/후위** 세 가지 방식이 있습니다.

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

**노드 → 왼쪽 → 오른쪽** 순서로 방문합니다.  
트리 구조를 복제할 때 유용합니다.

```java
void preOrder(Node root) {
    if (root == null) return;
    
    System.out.print(root.value + " "); // 현재 노드
    preOrder(root.left);  // 왼쪽 서브트리
    preOrder(root.right); // 오른쪽 서브트리
}

실행 결과: A → B → E → F → C → G → H → D → I → J → K → L

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

왼쪽 → 노드 → 오른쪽 순서로 방문합니다.
이진 탐색 트리(BST)에서 값 정렬 시 사용됩니다.

void inOrder(Node root) {
    if (root == null) return;
    
    inOrder(root.left);   // 왼쪽 서브트리
    System.out.print(root.value + " "); // 현재 노드
    inOrder(root.right);  // 오른쪽 서브트리
}

실행 결과: E → B → F → A → G → C → H → D → J → I → K → L

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

왼쪽 → 오른쪽 → 노드 순서로 방문합니다.
트리 삭제 작업 시 유용합니다.

void postOrder(Node root) {
    if (root == null) return;
    
    postOrder(root.left);  // 왼쪽 서브트리
    postOrder(root.right); // 오른쪽 서브트리
    System.out.print(root.value + " "); // 현재 노드
}

실행 결과: E → F → B → G → H → C → J → K → L → I → D → A

시간 복잡도: 세 방식 모두 O(N) (각 노드 한 번씩 방문)

---

마무리

트리 순회는 알고리즘 문제 해결의 기초입니다.

• BFS: 레벨별 탐색, 최단 경로
• DFS: 깊이 우선 탐색, 구조 분석

문제 유형에 맞춰 적절한 순회 방식을 선택해보세요!
궁금한 점이나 보완할 내용이 있다면 댓글로 남겨주세요 😊

---

velog에 복사하여 바로 사용 가능합니다.
추가 설명이나 예시가 필요하면 언제든 요청해 주세요!

트리(Tree) 구현 방식 정리

트리는 노드와 간선으로 구성된 계층적 자료구조로, 다양한 구현 방식이 존재합니다. 아래는 실전 코딩테스트와 알고리즘 문제에서 자주 등장하는 트리 구현 패턴들을 한눈에 정리한 내용입니다.

---

1. 인접 리스트 (Adjacency List)

트리를 구현할 때 가장 많이 사용하는 방법 중 하나입니다.
트리는 그래프의 일종이므로, 그래프에서 널리 쓰이는 인접 리스트 방식을 그대로 사용할 수 있습니다.
트리는 부모-자식 관계가 명확하고 방향성이 있으므로 단방향 그래프로 구현합니다.

인접 리스트 구현 방식

방식	자료형	특징
2차원 배열	int[][]	입력이 배열 형태로 주어질 때 사용, 정적 구조
2차원 리스트	List>	노드 번호가 연속적일 때, edge 리스트를 바탕으로 직접 구성
해시맵	Map>	노드 번호가 불연속적이거나 문자열일 때 적합

(1) 2차원 배열

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

자식 노드 순회:

for (int child : tree[0]) {
    System.out.println(child);   // 1, 2
}

(2) 2차원 리스트

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

자식 노드 순회:

for (int child : tree.get(0)) {
    System.out.println(child);   // 1, 2
}

(3) 해시맵

Map> 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);

자식 노드 순회:

for (int child : tree.get(0)) {
    System.out.println(child);  // 1, 2
}

---

2. 간선 리스트 (Edge List)

트리의 각 간선을 부모-자식 쌍으로 저장하는 방식입니다.
문제의 입력이 간선 리스트 형태일 때가 많으며, 보통 간선 리스트 → 인접 리스트로 변환해서 사용합니다.

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

(1) 간선 리스트 → 인접 리스트(2차원 리스트)

List> tree = new ArrayList<>();
for (int i = 0; i ());
for (int[] edge : edges) {
    int parent = edge[0], child = edge[1];
    tree.get(parent).add(child);
}

(2) 간선 리스트 → 인접 리스트(해시맵)

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

주의: 해시맵 기반 인접 리스트는 자식이 없는 노드가 Map에 포함되지 않을 수 있습니다.
탐색 시 containsKey() 또는 getOrDefault()를 활용해 안전하게 순회하세요.

for (int child : tree.getOrDefault(1, Collections.emptyList())) {
    // 안전하게 순회
}

---

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

각 노드가 최대 두 개의 자식만 가지는 구조입니다.
클래스 기반 트리 구현은 Leetcode 등에서 가장 흔하게 사용됩니다.

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

자식 노드 접근:

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

---

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

자식의 수가 정해져 있지 않은 트리 구조입니다.
각 노드가 자식 노드 리스트를 직접 관리합니다.

class Node {
    int val;
    List children;
    Node() {}
    Node(int val) { this.val = val; }
    Node(int val, List children) {
        this.val = val;
        this.children = children;
    }
}

자식 노드 순회:

for (Node child : root.children) {
    System.out.println(child.val);
}

---

5. 레벨 순서 배열 (완전 이진 트리, 힙)

완전 이진 트리에서는 노드를 레벨 순서대로 배열에 저장하는 방법이 효율적입니다.

int[] tree = {0, 1, 2, -1, -1, 3, 4}; // -1은 빈 자리

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

---

6. 배열 기반 자식 정보 (특정 문제형)

각 노드의 자식 정보를 배열로 주는 경우도 있습니다.

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

• links[i]는 i번 노드의 [왼쪽 자식, 오른쪽 자식] 정보
• 자식이 없으면 -1

---

마무리

트리는 문제의 입력 형태에 따라 다양한 방식으로 구현할 수 있습니다.

• 인접 리스트: 가장 범용적, 그래프/트리 모두 사용
• 간선 리스트: 입력이 edge list일 때
• 클래스 기반: 이진 트리, N-ary 트리 등 객체지향적 구현
• 배열/레벨 순서: 완전 이진 트리, 힙 등

문제에 따라 적합한 구현 방식을 선택하는 것이 중요합니다.

---

트리와 재귀

트리는 계층적 구조와 재귀적 정의가 핵심인 자료구조입니다. 트리의 본질, 재귀적 탐색 원리, 다양한 구현 및 탐색 패턴을 예제 코드와 함께 정리합니다.

---

1. 트리의 재귀적 정의

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

1. 빈 트리(Empty Tree)도 트리이다.
2. 노드가 하나만 있는 트리(루트만 존재)도 트리이다.
3. 루트 노드 + 0개 이상의 자식 트리가 모이면 전체로 하나의 트리이다.

즉, 트리는 “어떤 노드 + 그 노드의 서브트리들(subtrees)”로 완성되는 계층 구조입니다.

서브트리(Subtree)란?

트리에서 임의의 노드를 루트로 잡고, 그 하위 노드들을 모두 포함한 부분 구조를 서브트리라고 합니다.
트리는 "트리 안에 또 트리"가 들어있는 재귀 구조이기 때문에, 트리 문제를 풀 때 서브트리 개념이 매우 중요합니다.

예시:

    A
   / \
  B   C
 / \
D   E

• B를 루트로 보면, B-D-E가 하나의 서브트리입니다.

---

2. 트리와 재귀적 탐색

트리는 부모가 하는 일을 자식도 반복한다는 특성 때문에, 재귀적 접근이 매우 자연스럽습니다.

• 트리의 모든 노드 값을 출력하려면?
  → 부모 노드 값을 출력하고, 자식 노드들을 재귀 호출로 탐색

• 트리에서 특정 값을 계산하려면?
  → 자식 노드들의 결과를 모아 최종 결론 도출

재귀적 접근법의 핵심

• 서브트리 단위로 문제를 나누기
• 부모가 하는 일을 자식도 반복한다고 가정
• 재귀 함수로 자식 노드를 호출하여 트리를 순회

---

3. 트리 탐색 – 코드 템플릿

(1) 일반 트리(자식 리스트) – DFS

void dfs(Node node) {
    // 현재 노드 처리
    System.out.println(node.value);
    for (Node child : node.children) {
        dfs(child);
    }
}

예제

class Node {
    int value;
    List 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 child1 = new Node(2);
        Node child2 = new Node(3);
        Node child3 = new Node(4);
        Node child4 = new Node(5);
        root.children.add(child1);
        root.children.add(child2);
        child1.children.add(child3);
        child1.children.add(child4);
        dfs(root);
    }
}

---

(2) 이진 트리 – DFS

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

예제

class Node {
    int value;
    Node left, 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);
        dfs(root);
    }
}

---

(3) 무방향 트리(양방향 인접 리스트)

Map> tree = new HashMap<>() {{
    put(1, List.of(2, 3));
    put(2, List.of(1, 4, 5));
    put(3, List.of(1));
    put(4, List.of(2));
    put(5, List.of(2));
}};

• visited 집합 사용: 이미 방문한 노드 재방문 방지

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

• parent 변수 사용: 부모로 돌아가는 역방향 이동 방지

void dfs(int cur, int parent) {
    System.out.println(cur);
    for (int nxt : tree.get(cur)) {
        if (nxt == parent) continue;
        dfs(nxt, cur);
    }
}

---

(4) 일방향 트리(Directed Tree)

Map> tree = new HashMap<>() {{
    put(1, List.of(2, 3));
    put(2, List.of(4, 5));
    put(3, List.of());
    put(4, List.of());
    put(5, List.of());
}};

• 방향성이 있으므로 visited 없이 탐색 가능
• 필요하면 visited를 써도 무방

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

---

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

• 배열 인덱스 규칙
  • 왼쪽 자식: 2 * i + 1
  • 오른쪽 자식: 2 * i + 2

int[] arr = {1, 2, 3, 4, 5, -1, -1};
void dfs(int index) {
    if (index >= arr.length || arr[index] == -1) return;
    System.out.println(arr[index]);
    dfs(2 * index + 1); // 왼쪽
    dfs(2 * index + 2); // 오른쪽
}

---

4. 마무리

• 트리는 재귀적 정의와 서브트리 개념이 핵심
• DFS 재귀로 트리 순회/탐색이 매우 자연스럽고 코드가 간결
• 무방향 트리는 visited나 parent로 역방향 방지
• 완전 이진 트리/힙은 배열로도 구현 가능

트리 문제를 만날 때는 "부모가 하는 일을 자식도 반복"하는 구조를 떠올리면, 자연스럽게 재귀로 설계할 수 있습니다.

---

트리 순회(Tree Traversal)

트리 순회는 트리의 모든 노드를 체계적으로 방문하는 기술입니다.
주요 방법으로 DFS 기반 전위/중위/후위 순회와 BFS 기반 레벨 순회가 있습니다.
각 순회 방식의 특징과 구현 방법을 예제 코드와 함께 알아보겠습니다.

---

트리 순회의 기본 개념

방문(Visit) vs 순회(Traversal)

• 방문: 노드의 값을 출력/계산/저장하는 구체적인 행위
• 순회: 모든 노드를 체계적으로 방문하기 위한 전체적인 동선

트리 구조 예시

       A
      / \
     B   C
    / \   \
   D   E   F

---

깊이 우선 순회(DFS)

1. 전위 순회 (Pre-order)

순서: 부모 → 왼쪽 자식 → 오른쪽 자식
활용: 트리 구조 복제, 표현식 전위 표기법

void preOrder(Node root) {
    if (root == null) return;
    System.out.print(root.value); // 현재 노드 방문
    preOrder(root.left);          // 왼쪽 서브트리
    preOrder(root.right);         // 오른쪽 서브트리
}

실행 결과: ABDECF

2. 중위 순회 (In-order)

순서: 왼쪽 자식 → 부모 → 오른쪽 자식
활용: 이진 탐색 트리(BST) 값 정렬

void inOrder(Node root) {
    if (root == null) return;
    inOrder(root.left);           // 왼쪽 서브트리
    System.out.print(root.value); // 현재 노드 방문
    inOrder(root.right);          // 오른쪽 서브트리
}

실행 결과: DBEACF

3. 후위 순회 (Post-order)

순서: 왼쪽 자식 → 오른쪽 자식 → 부모
활용: 트리 삭제, 표현식 후위 표기법

void postOrder(Node root) {
    if (root == null) return;
    postOrder(root.left);         // 왼쪽 서브트리
    postOrder(root.right);        // 오른쪽 서브트리
    System.out.print(root.value); // 현재 노드 방문
}

실행 결과: DEBFCA

---

너비 우선 순회(BFS)

4. 레벨 순회 (Level-order)

순서: 레벨 0 → 레벨 1 → 레벨 2
활용: 최단 경로 탐색, 계층별 데이터 처리

void levelOrder(Node root) {
    Queue q = new LinkedList<>();
    q.add(root);
    
    while (!q.isEmpty()) {
        Node cur = q.poll();
        System.out.print(cur.value);
        
        if (cur.left != null) q.add(cur.left);
        if (cur.right != null) q.add(cur.right);
    }
}

실행 결과: ABCDEF

---

시간 복잡도 비교

순회 방식	시간 복잡도	공간 복잡도
전위/중위/후위	O(N)	O(H)
레벨 순회	O(N)	O(W)

• N: 전체 노드 수
• H: 트리 높이
• W: 트리 최대 너비

---

활용 팁

1. 트리 복제 → 전위 순회
2. 값 정렬 필요 → 중위 순회
3. 후처리 필요 → 후위 순회
4. 레벨별 처리 → 레벨 순회
5. 메모리 제약 → 반복문 구현 권장

---