[백준] 9934 완전 이진 트리

문제

www.acmicpc.net/problem/9934

 

 

코드

K = int(input()) # 입력 받는 K
building = list(map(int, input().split())) # 입력받는 배열
answer = [0] * (2 ** K + 1)
index = 0 # 입력 받은 배열 building을 순회할 때 사용하는 index

def inorder(i, depth): # 중위 순회
    global index
    if depth == K: # base condition
        answer[i] = building[index]
        index += 1
    else:
        inorder(i * 2, depth + 1)
        answer[i] = building[index]
        index += 1
        inorder(i * 2 + 1, depth + 1)

inorder(1,1)
count = 1 # answer[1] 부터 출력
for i in range(K):
    for j in range(2**i):
        print(answer[count], end=' ')
        count += 1
    print()

 

풀이

1. 첫 번째 생각: 트리를 만든 후, 값을 차례대로 넣어주고 level마다 출력하기 -> 노드를 초기화 해주는 작업이 추가로 필요하다.
2. 두 번째 생각: 완전 이진 트리 특성을 이용하여 트리 만들지 않고 배열로 해결하기

두 번째 생각

1. 완전 이진 트리 특성: 부모 node를 기준으로 left node는 부모 노드 index * 2, right node는 부모 노드 index * 2 + 1이 된다.
2. 위 문제는 중위 순회인 것을 파악하고 중위 순회를 한다.
   1. 중위 순회: left node -> parent node -> right node
   2. 앞서 얘기한 완전 이진 트리 특성 + 중위 순회 개념을 합쳐서 아래 코드 작성.

   3. inorder(i * 2, depth + 1)
      answer[i] = building[index]
      index += 1
      inorder(i * 2 + 1, depth + 1)

3. base condition은 depth가 K일 때로 하고 answer = building[index] 해준다.

개념

완전 이진 트리: 이진 트리 중 노드가 왼쪽 부터 차례대로 채워져 있는 트리

포화 이진 트리: 이진 트리 중 자식 노드 2개가 모두 채워져 있는 트리

 

아래 그림은 포화 이진 트리이면서 완전 이진 트리이다.

 

완전 이진 트리(포화 이진 트리)

 

완전 이진 트리 특성

1. root 노드 index를 1이라고 한다면, left node는 index * 2, right node는 index * 2 + 1이 된다.

 

전위 순회 (pre-order traversal) 

루트 노드 -> 왼쪽 노드 -> 오른쪽 노드 순으로 방문한다.

후위 순회 (post-order traversal)

왼쪽 노드 -> 오른쪽 노드 -> 루트 노드 순으로 방문한다.

 

중위 순회 (in-order traversal)

왼쪽 노드 -> 루트 노드 -> 오른쪽 노드 순으로 방문한다.