[문제해설] 다음 트리를 Postorder로 운행한 결과를 쓰시오.

전자계산기조직응용기사 실기 필답형 기출문제 (트리 순회) - 2015년1회

---

다음 트리를 Postorder로 운행한 결과를 쓰시오.

 

---

- 문제 해설 -

2진 트리 순회 문제입니다. 트리 순회는 수식 표기법과 노드의 값이 다르다는 것 말고는 같은 문제이니, 정석대로 익혀놓는 것이 좋습니다. 정석대로 풀 줄 알아야 코딩으로 구현할 수가 있습니다.

트리를 순회하는 방법에는 3가지가 있으며, 아래의 3개의 노드로 이루어진 2진 트리를 기본으로 합니다.

표기법	순회순서
전위(Prefix)	root → left → right
중위(infix)	left → root → right
후위(postfix)	left → right → root
인터럽트 조건 : 순회하는 노드가 자식노드가 있을 때.

 

이처럼 순회 방법의 전, 중, 후는 순회 순서에서 root의 위치와 연관하여 기억하면 됩니다.

중요한 건 인터럽트인데, 순회하는 노드가 자식 노드가 있으면, 순회 중인 트리의 순회를 멈추고 하위 트리를 순회하면 됩니다. 그리고 항상 처음 순회하는 트리는 root를 포함하는 트리입니다.

 

말보다는 실전이죠... 문제에서 주어진 트리를 순회해보겠습니다.

문제의 조건은 Postorder, 후위 순회를 해야 됩니다. 순서는 left → right → root 순입니다.

 

 

먼저 위 그림에서 표시한 데로, 전체 트리에서 root를 가지고 있는 최상위 트리에서 순회를 시작합니다. 표시된 3개의 노드로 이루어진 트리에서 순회를 시작하면 처음은 left인 B입니다. 하지만, 노드 B는 자식을 가지고 있으므로, 인터럽트가 발생합니다. 확정을 하지 말고 순회를 멈춥시다.

인터럽트가 발생하면 하위 트리를 순회합니다. 파란색으로 표시된 하위 트리에서도 당연히 Postorder 순회입니다. 그럼 우선 left인 D를 순회합니다. 그다음 rihgt에 해당하는 노드는 없으므로 마지막 root인 B를 순회합니다.(현재까지 D,B)

그럼 파란색 동그라미로 표시한 트리의 순회는 끝이 나고, 원래의 오렌지색 트리로 돌아와서 멈췄던 순회를 계속합니다.

그럼 오랜지색 트리의 right에 해당하는 C를 순회해야 하는데, 노드 C는 자식 노드를 가지므로 인터럽트가 발생합니다.

이번에는 노란색으로 표시된 트리를 순회해야 합니다. postorder 순회(left → right → root)를 하면 E→F→C 순으로 순회를 하게 됩니다.(현재까지 D,B,E,F,C)

그럼 노란색 트리의 순회는 끝이 나고, 원래의 트리로 복귀합니다.

원래의 트리로 돌아오면, B와 C는 순회를 끝난 상황이므로, A를 순회합니다.(현재까지 D,B,E,F,C,A)

그럼 모든 순회를 마쳤습니다. 순회한 결과는 D,B,E,F,C,A 입니다.

 

 

 

https://youtube.com/playlist?list=PLboXycXmAIDt4ObBRPVj29BuD2d27oRnO

전자계산기조직응용기사 실기 필답형