위성

지침

대역폭이 제한된 상황에서 알파 센타우리로 다가가는 인공위성에 이진 트리를 전송해야 한다고 상상해 봐요. 트리에는 중복되는 항목이 없기 때문에, 전위 순회와 중위 순회 결과만으로 트리를 유일하게 표현할 수 있어요.

순회 결과로부터 트리를 복원하는 소프트웨어를 위성용으로 작성해 봐요.

전위 순회는 왼쪽 서브트리를 전위 순회로 읽기 전에(그래서 "전위"예요) 현재 노드의 값을 읽어요. 그다음 오른쪽 서브트리를 전위 순회로 읽어요.

중위 순회는 왼쪽 서브트리를 중위 순회로 읽고, 그다음 현재 노드를, 마지막으로 오른쪽 서브트리를 중위 순회로 읽어요. 즉 왼쪽에서 오른쪽 순서예요.

예를 들어 이 트리의 전위 순회는 [a, i, x, f, r]이고, 중위 순회는 [i, a, f, x, r]예요.

  a
 / \
i   x
   / \
  f   r

참고: 전위 순회의 첫 번째 항목은 항상 루트예요.