[백준] 01991. 트리 순회 풀이

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

 

주어진 트리를 전위순회, 중위순회, 후위회의 방식으로 탐색하고 그 탐색 순서를 출력하는 문제이다.

각 순회는 다음과 같은 규칙으로 탐색된다.

 

전위순회
현재 위치를 탐색하고 (현재 탐색중인 노드 출력)
왼쪽 자식 노드 탐색, 
그 다음 오른쪽 자식 노드 탐색

중위순회
왼쪽 자식 노드부터 탐색하고
현재 노드 탐색 (현재 탐색중인 노드 출력)
그 다음 오른쪽 자식 노드 탐색

후위 순회
왼쪽 자식 노드부터 탐색하고
오른쪽 자식 노드 탐색
그 다음 현재 노드 탐색 (현재 탐색중인 노드 출력)

 

위와 같은 규칙을 매 재귀때마다 적용할 수 있도록 한다.

 

입력받은 알파벳은 탐색의 편의를 위해 아스키코드를 이용해 숫자로 바꾼 후 A는 0, B는 1... 이 되도록 변환했다.

또한 dfs의 매개변수인 mode는 0이 전위순회, 1이 중위순회, 2가 후위순회를 의미한다.

---

C

#include <stdio.h>

int edge[26][2];

void dfs(int n, int mode){
    if(mode == 0) printf("%c", n+65);
    if(edge[n][0] != -1) dfs(edge[n][0], mode);
    if(mode == 1) printf("%c", n+65);
    if(edge[n][1] != -1) dfs(edge[n][1], mode);
    if(mode == 2) printf("%c", n+65);
}

int main(){
    int n; scanf("%d", &n);
    for(int i = 0; i < n; i++){
        char c1, c2, c3;
        scanf(" %c %c %c", &c1, &c2, &c3);
        int v1 = c1, v2 = c2, v3 = c3;
        v1 -= 65;
        edge[v1][0] = (v2 != 46) ? v2 - 65 : -1;
        edge[v1][1] = (v3 != 46) ? v3 - 65 : -1;
    }
    dfs(0, 0);
    printf("\n");
    dfs(0, 1);
    printf("\n");
    dfs(0, 2);
}

---

Python

import sys
sys.setrecursionlimit(10 ** 6)

def dfs(n, mode):
    if mode == 0: print(chr(n+65), end='')
    if edge[n][0] != -1: dfs(edge[n][0], mode) # 왼쪽 자식 노드 탐색
    if mode == 1: print(chr(n+65), end='')
    if edge[n][1] != -1: dfs(edge[n][1], mode) # 오른쪽 자식 노드 탐색
    if mode == 2: print(chr(n + 65), end='')
    return 0

n = int(input())
edge = [[0 for _ in range(2)] for _ in range(n)]

for i in range(n):
    v1, v2, v3 = map(ord, input().split())
    v1 -= 65
    v2 = v2-65 if v2 != 46 else -1
    v3 = v3 - 65 if v3 != 46 else -1
    edge[v1][0] = v2
    edge[v1][1] = v3

dfs(0, 0)
print()
dfs(0, 1)
print()
dfs(0, 2)