다음은 이진트리를 전위 순회하여 얻어진 전위표기식이다. 이 트리에 대한… | [7급 국가직 자료구조론] 21년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 21년 1회차
다음은 이진트리를 전위 순회하여 얻어진 전위표기식이다. 이 트리에 대한 설명으로 옳지 않은 것은?＋ / * 6 2 － 3 1 * ＋ 5 8 － 7 4
1
연산식의 최종 결과는 45이다.
2
트리로 재구성하면 루트 노드는 ＋이다.
3
트리로 재구성하여 중위 순회하면 6*2/3－1＋5＋8*7－4이다.
4
트리로 재구성하여 후위 순회하면 62*31/－58＋74－*＋이다.
해설
후위 순회 결과를 62*31/-58+74-*+로 적은 설명이 옳지 않다. 올바른 후위 순회는 6 2 * 3 1 - / 5 8 + 7 4 - * +로, 3 1 다음에 -가 먼저 와야 한다.
전위식을 재구성하면 루트 +의 왼쪽 서브트리는 (6*2)/(3-1), 오른쪽 서브트리는 (5+8)*(7-4)이다.
- 12/2=6, 13×3=39이므로 연산식의 최종 결과 45는 옳다.
- 전위식의 첫 기호가 루트이므로 루트 노드가 +라는 설명은 옳다.
- 중위 순회는 괄호 없이 왼쪽·루트·오른쪽 순으로 나열하므로 6*2/3-1+5+8*7-4가 되어 옳다.
오류나 개정된 내용이 보이면 알려주세요