[Python, 파이썬] SWEA 1231. [S/W 문제해결 기본] 9일차 - 중위순회

주어진 트리를 in-order, 중위 순회해 각 노드를 읽었을 때 나오는 단어를 구하는 문제.

def DFS(i):

    if(i > N): # 트리 노드 개수가 끝나면
        return

    DFS(2*i) # 왼쪽 노드 탐색
    print(node[i], end='')

    DFS(2*i+1) # 오른쪽 노드 탐색

T = 10 # 테스트케이스의 개수 T

for test_case in range(1, T+1):

    N = int(input()) # 노드 개수 N
    node = [0 for i in range(N+1)]

    # 트리 입력받기
    for _ in range(1, N+1):
        n, v = input().split()[:2]
        node[int(n)] = v

    # 탐색 시작
    print("\n#%d " %(test_case), end='')
    DFS(1)

 

 

 

[문제풀이]

---

 

중위 탐색이란 왼쪽 노드부터 시작해서 현재, 오른쪽 노드로 탐색하는 방식이다.

우선 트리를 배열에 저장하는데, 이진 트리는 1차원 배열의 형식으로 저장할 수 있다.

for _ in range(1, N+1):
        n, v = input().split()[:2]
        node[int(n)] = v

 

단순히 앞에서부터 차례로 채우는 게 아니라, 부모 노드의 index *2, index *2 +1 자리에 자식 노드가 들어오도록 한다. 주어진 트리는 루트가 1번부터 시작하며, 완전 이진 트리로 왼쪽부터 자식 노드가 꽉 채워진 형식이기 때문에 위치 계산 필요 없이 주어진대로 차례로 채우기만 하면 된다.

DFS(2*i) # 왼쪽 노드 탐색
print(node[i], end='')

DFS(2*i+1) # 오른쪽 노드 탐색

 

그 다음 탐색을 하는데 이렇게 왼쪽 노드, print문, 오른쪽 노드 순서대로 하면된다.

그럼 DFS로 자식으로 쭉 탐색해 내려간 다음 print문을 실행해 중위 순회가 구현된다.

 

이 3줄 코드 위치를 조정해 중위, 전위, 후위 탐색이 가능하다.

print문을 맨 위에 둘 시 전위, 중간에 두면 중위, 맨 마지막에 두면 후위 탐색이 된다.