[자료구조] 코틀린 Tree 전위, 중위, 후위 순회 구현하기 (백준 1991)

코틀린에서 트리를 구현하기 위하여 자바와 동일한 방법을 사용한다.

트리의 개념은 별도로 정리하지 않았다.

 

// 노드 데이터 클래스
data class TreeNode<T>(
    var data: T,
    var left: TreeNode<T>? = null,
    var right: TreeNode<T>? = null
)

데이터와 연결상태를 저장할 데이터 클래스를 선언해준다. 이진트리로 좌우 연결 상태만 표시하였다.

별도의 타입을 지정하지 않고 제네릭 타입으로 T로 선언해주었다.

 

문제 : https://www.acmicpc.net/problem/1991

1991번: 트리 순회

이제 이 노드로 트리 순회를 구현해보자.

 

// String 트리 클래스
class Tree{
    var root : TreeNode<String>? = null

    // 트리 추가
    fun add(data: String, left: String, right: String){
        // 루트가 NULL 일 때 (트리 내에 존재하지 않을 때)
        if(root == null){
            // 새로 생성
            if(data != ".") root = TreeNode(data)
            if(left != ".") root!!.left = TreeNode(left)
            if(right != ".") root!!.right = TreeNode(right)
        }
        // 트리 내에 존재할 때
        else search(root!!,data,left,right)
    }

    private fun search(root: TreeNode<String>, data: String, left: String, right: String){
        // 찾았을 때, left right 연결
        if(root.data == data){
            if(left != ".") root!!.left = TreeNode(left)
            if(right != ".") root!!.right = TreeNode(right)
        }

        // 못 찾았을 때, 좌우 탐색
        else {
            if(root.left != null) search(root.left!!,data,left,right)
            if(root.right != null) search(root.right!!,data,left,right)
        }
    }
}

트리의 루트, 좌우 노드를 입력받을 수 있는 add 함수를 추가한다.

입력받은 루트가 이미 트리 내에 존재할 경우 새로 생성하지 않고 원래 존재하는 트리에 좌우를 붙여주어야 하기 때문에 트리 내부 데이터를 찾는 search 함수를 구현하여 연결해준다.

 

백준 1991번. 트리 순회

 

이제 순회 순서에 따라 재귀로 탐색해준다.

 

전체코드

import java.util.*

// 노드 데이터 클래스
data class TreeNode<T>(
    var data: T,
    var left: TreeNode<T>? = null,
    var right: TreeNode<T>? = null
)

// String 트리 클래스
class Tree{
    var root : TreeNode<String>? = null

    // 트리 추가
    fun add(data: String, left: String, right: String){
        // 루트가 NULL 일 때 (트리 내에 존재하지 않을 때)
        if(root == null){
            // 새로 생성
            if(data != ".") root = TreeNode(data)
            if(left != ".") root!!.left = TreeNode(left)
            if(right != ".") root!!.right = TreeNode(right)
        }
        // 트리 내에 존재할 때
        else search(root!!,data,left,right)
    }

    private fun search(root: TreeNode<String>, data: String, left: String, right: String){
        // 찾았을 때, left right 연결
        if(root.data == data){
            if(left != ".") root!!.left = TreeNode(left)
            if(right != ".") root!!.right = TreeNode(right)
        }

        // 못 찾았을 때, 좌우 탐색
        else {
            if(root.left != null) search(root.left!!,data,left,right)
            if(root.right != null) search(root.right!!,data,left,right)
        }
    }

    // 전위 순회 (루트, 왼쪽 자식, 오른쪽 자식)
    fun preOrder(root: TreeNode<String>){
        print(root.data)
        if(root.left != null) preOrder(root.left!!)
        if(root.right != null) preOrder(root.right!!)
    }

    // 중위 순회 (왼쪽 자식, 루트, 오른쪽 자식)
    fun inOrder(root: TreeNode<String>){
        if(root.left != null) inOrder(root.left!!)
        print(root.data)
        if(root.right != null) inOrder(root.right!!)
    }

    // 후위 순회 (왼쪽 자식, 오른쪽 자식, 루트)
    fun postOrder(root: TreeNode<String>){
        if(root.left != null) postOrder(root.left!!)
        if(root.right != null) postOrder(root.right!!)
        print(root.data)
    }
}

fun main() = with(Scanner(System.`in`)) {
    val n = nextLine().toInt()
    val tree = Tree()

    // 트리 만들기
    for(i in 0 until n){
        val (a,b,c) = nextLine().split(" ")
        tree.add(a,b,c)
    }

    tree.preOrder(tree.root!!)
    println()
    tree.inOrder(tree.root!!)
    println()
    tree.postOrder(tree.root!!)
}