백준 - 트리 순회 (1991)

struct Node {
    let left: String
    let right: String
}

let N = Int(readLine()!)!
var tree = [String: Node]()
var answer = ""

// 이진트리 구축
for _ in 0..<N {
    let input = readLine()!.split(separator: " ").map { String($0) }
    tree[input[0]] = Node(left: input[1], right: input[2])
}

// 전위 순회
preOrder("A")
answer += "\n"

// 중위 순회
inOrder("A")
answer += "\n"

// 후위 순회
postOrder("A")
answer += "\n"

print(answer)

func preOrder(_ node: String) {
    if node == "." {
        return
    }
    answer += node
    preOrder(tree[node]!.left)
    preOrder(tree[node]!.right)
}

func inOrder(_ node: String) {
    if node == "." {
        return
    }
    inOrder(tree[node]!.left)
    answer += node
    inOrder(tree[node]!.right)
}

func postOrder(_ node: String) {
    if node == "." {
        return
    }
    postOrder(tree[node]!.left)
    postOrder(tree[node]!.right)
    answer += node
}

이진트리 자료구조 및 운행을 구현하는 기본적인 문제였다.

• 전위 순회: 루트 - 왼쪽 부분트리 - 오른쪽 부분트리
• 중위 순회: 왼쪽 부분트리 - 루트 - 오른쪽 부분트리
• 후위 순회: 왼쪽 부분트리 - 오른쪽 부분트리 - 루트

순으로 방문하면 되며, 이때 재귀의 개념이 사용된다.