1991번: 트리 순회

1991번: 트리 순회

 

트리 순회

 

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

입력

첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.

출력

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

예제 입력 1 

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

예제 출력 1 

ABDCEFG
DBAECFG
DBEGFCA

---

풀이

 

문제를 이해해보자.

 

주어진 이진트리에서 전위 순회, 중위 순회, 후위 순회한 결과를 출력하면 된다.

 

위의 3종 순회 알고리즘 수업때 공부했었는데 오랜만에 들어본다 ㅎㅎ

아무튼 주어진 트리를 어떻게 연결리스트로 구현할지에 대한 고민이 들었다. 

 

 

처음에 내가 생각한 건 ,

 

입력값이 문자이기 때문에 문자의 아스키코드를 이용하여 0~N까지의 리스트로 구현하려 했다.

연결리스트로 노드들을 연결했지만, 이제 3종 순회를 하고 다시 문자로 보여주는데 어려움이 있었다.

다시 아스키코드를 이용하여 문자 -> 숫자로 바꾼 노드를 다시 문자로 바꿔 출력해야하기 때문이다.

 

let N = Int(readLine()!)!
var graph = [[String]](repeating: [String](repeating: "", count: 0), count: N )

var result = [Int](repeating: 0, count: N+1)

for _ in 0..<N{
    let input = readLine()!.split(separator: " ").map{String($0)}
    let node = Int(UnicodeScalar(input[0])!.value) - 65
    let a = input[1], b = input[2]

    graph[node].append(a)
    graph[node].append(b)
}

preorder("A")

func preorder(_ node: String){
    if node == "." {
        return
    }
    
    let t = String(UnicodeScalar(graph[0]+65)!)
    print(t, terminator: "")
    preorder(graph[t][0])
    preorder(graph[t][1])
}

 

---

설계

이진트리이니 왼쪽과 오른쪽의 노드, 최대 2개의 자식 노드르 가질 수 있다.

그렇기 때문에 구조체를 이용하여 연결리스트를 구현하면 되겠다.

 

3종 순회에 대해 이해하고 구현해보자.

 

1️⃣ 전위 순회

 

 

 

2️⃣ 중위 순회

 

 

 

3️⃣ 후위 순회

 

 

---

구현

 

1️⃣ 연결리스트 구현

 

Node라는 구조체를 선언하고, left와 right라는 프로퍼티를 선언하여 왼쪽과 오른쪽 자식 노드를 나타냈다.

graph는 딕셔너리로 만들어 입력받은 노드들을 딕셔너리에 추가하였다.

 

 

2️⃣ 3종 순회

 

• 전위 순회 => (root -> 왼쪽 - >오른쪽)

 

 

• 중위 순회 => (왼쪽 -> root -> 오른쪽)

 

• 후위 순회 => (왼쪽 -> 오른쪽 -> root)

 

 

 

 

 

---

전체코드

 

let N = Int(readLine()!)!

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

var graph: [String: Node] = [:]

for _ in 0..<N{
    let input = readLine()!.split(separator: " ").map{String($0)}
    graph[input[0]] = Node(left: input[1], right: input[2])
    
}

func preorder(_ node: String){
    if node == "." {
        return
    }
    
    print(node, terminator: "")
    preorder(graph[node]!.left)
    preorder(graph[node]!.right)
}

func inorder(_ node: String){
    if node == "." {
        return
    }
    
    inorder(graph[node]!.left)
    print(node, terminator: "")
    inorder(graph[node]!.right)
}

func postorder(_ node: String){
    if node == "." {
        return
    }
    
    postorder(graph[node]!.left)
    postorder(graph[node]!.right)
    print(node, terminator: "")
}

let orders = [preorder, inorder, postorder]
orders.forEach {
    $0("A")
    print()
}