2009년03월01일 66번

[전자계산기 일반 및 무선설비기준]
다음 그림과 같은 트리를 후위 순회(postorder -traversal)한 결과는?

① +**/ABCDE
② AB/C*D*E+
③ A*B+C*D/E
④ A*B+CD*/E

(정답률: 84%)

문제 해설

트리의 후위 순회는 왼쪽 자식 노드, 오른쪽 자식 노드, 그리고 부모 노드 순으로 방문하는 것입니다. 따라서 위의 트리를 후위 순회하면 "AC/BD*E*+"이 됩니다.

보기에서 "AB/C*D*E+"가 정답인 이유는 다음과 같습니다.

- "AB/C*D*E+" : A와 B를 먼저 스택에 넣고, C를 만나면 스택에서 B와 A를 꺼내서 B/C를 계산하고 다시 스택에 넣습니다. D를 만나면 스택에서 C와 B를 꺼내서 C*D를 계산하고 다시 스택에 넣습니다. E를 만나면 스택에서 D와 C를 꺼내서 D*E를 계산하고 다시 스택에 넣습니다. 마지막으로 스택에서 E와 C*D를 꺼내서 C*D+E를 계산하고 결과를 반환합니다.
- "+**/ABCDE" : 이 경우에는 연산자 우선순위를 고려하지 않고 순서대로 계산하면 "A*B+C*D/E"와 같은 결과가 나옵니다.
- "A*B+C*D/E" : 이 경우에는 트리의 구조와 순서가 다르기 때문에 후위 순회 결과가 "AB*CD*E/+"가 됩니다.
- "A*B+CD*/E" : 이 경우에도 트리의 구조와 순서가 다르기 때문에 후위 순회 결과가 "AB*CD/E*+"가 됩니다.

이전 문제 다음 문제