위성

지침

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

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

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

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

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

  a
 / \
i   x
   / \
  f   r

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

이 연습 문제는 한정절 문법(DCG)을 사용해 구현해야 해요. DCG는 시퀀스(배열)를 파싱하는 데뿐만 아니라, 그 시퀀스를 생성하고 완성하고 검사하는 데에도 사용할 수 있어요.

라이브러리

스텁 구현 파일에는 다음과 같은 줄이 들어 있어요:

:- use_module(library(dcg/basics)).

이 줄이 있으면 dcg/basics 라이브러리를 사용할 수 있고, 이 연습 문제를 푸는 데에는 이걸로 충분해요.

참고 자료

Prolog에서 DCG를 시작하는 데 도움이 되는 자료는 다음과 같아요:

• metalevel.at
• 위키백과
• swipl