PHpullh
학습 라이브러리/Kotlin/트리 구조 (Tree Structure)

KOTLIN · 컬렉션

트리 구조 (Tree Structure)

제네릭 트리 자료구조를 구현하고 재귀적으로 순회합니다. DFS와 BFS를 모두 지원합니다.

컬렉션고급treedfsbfsrecursivedata-structure

핵심 설명

제네릭 트리 자료구조를 구현하고 재귀적으로 순회합니다. DFS와 BFS를 모두 지원합니다.

Kotlin code

data class TreeNode<T>(
    val value: T,
    val children: MutableList<TreeNode<T>> = mutableListOf()
) {
    fun addChild(value: T): TreeNode<T> {
        val child = TreeNode(value)
        children.add(child)
        return child
    }

    // DFS 순회
    fun dfs(action: (T, Int) -> Unit, depth: Int = 0) {
        action(value, depth)
        children.forEach { it.dfs(action, depth + 1) }
    }

    // BFS 순회
    fun bfs(action: (T) -> Unit) {
        val queue = ArrayDeque<TreeNode<T>>()
        queue.add(this)
        while (queue.isNotEmpty()) {
            val node = queue.removeFirst()
            action(node.value)
            queue.addAll(node.children)
        }
    }
}

fun main() {
    val root = TreeNode("회사")
    val dev = root.addChild("개발부")
    val sales = root.addChild("영업부")
    dev.addChild("프론트엔드")
    dev.addChild("백엔드")
    sales.addChild("국내")

    println("=== DFS ===")
    root.dfs { value, depth -> println("${"  ".repeat(depth)}$value") }

    println("=== BFS ===")
    root.bfs { print("$it ") }
}

학습 팁

ArrayDeque를 큐로 사용하면 LinkedList보다 캐시 친화적이어서 BFS 성능이 더 좋습니다.

주의할 점

트리에 순환 참조가 있으면 DFS/BFS가 무한 루프에 빠집니다. 방문 집합(visited set)을 사용하여 순환을 감지하세요.

자주 묻는 질문

트리 구조 (Tree Structure)란 무엇인가요?

제네릭 트리 자료구조를 구현하고 재귀적으로 순회합니다. DFS와 BFS를 모두 지원합니다.

트리 구조 (Tree Structure) 학습 시 주의할 점은 무엇인가요?

트리에 순환 참조가 있으면 DFS/BFS가 무한 루프에 빠집니다. 방문 집합(visited set)을 사용하여 순환을 감지하세요.