SWEA 1231 - 중위 순회 [파이썬]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV140YnqAIECFAYD 

SW Expert Academy

---

풀이 과정

완전 이진 트리가 주어질 때 중위 순회의 결과값을 출력하는 문제이다.

 

완전 이진 트리의 루트를 1번 노드라고 하면, 배열로 트리를 표현할 수 있다.

i번째 노드의 왼쪽 자식 노드는 2i, 오른쪽 자식 노드는 2i+1, 부모 노드는 i/2로 저장하면 배열로 트리의 표현이 가능하다.

 

전위 순회는 자신 -> 왼쪽 자식 -> 오른쪽 자식

중위 순회는 왼쪽 자식 -> 자신 -> 오른쪽 자식

후위 순회는 왼쪽 자식 -> 오른쪽 자식 -> 자신

 

순으로 순회한다. 보통 전, 중, 후위 순회를 구현할 때 재귀를 이용하는데, 재귀문의 위치를 조금만 바꿔주면 3가지의 순회를 쉽게 구현할 수 있다.

---

소스 코드

import sys
input = sys.stdin.readline


def dfs(cur):
    if cur > n: # 트리 크기보다 현재 방문점이 커지면 종료
        return
    dfs(cur*2) # 왼쪽 자식 노드 방문
    print(temp[cur][1], end="") # 현재 노드 출력
    dfs(cur*2+1) # 오른쪽 자식 노드 방문
    #왼쪽 -> 현재 -> 오른쪽 순으로 방문하는 중위 순회이며 위의 3줄의 코드의 위치에 따라
    #전위, 중위, 후위 순회가 결정된다


for tc in range(1, 11):
    n = int(input())
    temp = [0] # 0번 노드는 안쓸거니까 비워둔다

    for i in range(n):
        temp.append(list(map(str, input().split()))) # 입력

    print(f"#{tc} ", end="")
    dfs(1) # 1번 노드부터 재귀에 들어간다
    print()