다음과 같은 이진트리(binary tree)에서 전위순회(preorde… | [7급 국가직 자료구조론] 09년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 09년 1회차
다음과 같은 이진트리(binary tree)에서 전위순회(preorder traversal)와 중위순회(inorder traversal)를 했을 때, 두 순회 결과에서 노드 값의 방문 순서가 일치하는 횟수는? (전위순회의 k번째 노드값과 중위순회의 k번째 노드값이 같을 때, 일치하는 횟수를 1회로 한다)
1
3 회
2
4 회
3
5 회
4
6 회
해설
두 순회 결과를 나란히 비교하면 같은 자리에서 일치하는 노드는 B, E, I, G로 4회이다.
전위순회(루트→왼쪽→오른쪽)는 A, B, D, E, H, C, F, I, J, G 순이고, 중위순회(왼쪽→루트→오른쪽)는 D, B, H, E, A, F, J, I, C, G 순이다.
2번째 B, 4번째 E, 8번째 I, 10번째 G가 같고 나머지 자리는 모두 다르다.
- 3회: 네 자리 중 하나(예: 마지막 G)를 빠뜨렸을 때 나오는 값이다.
- 5회: 실제 일치 수보다 많아, 순회 순서를 잘못 구했을 때 나오는 값이다.
- 6회: H를 E의 오른쪽 자식으로 보는 등 트리 구조를 잘못 읽었을 때 나올 수 있는 값으로, 실제 일치는 4회뿐이다.
오류나 개정된 내용이 보이면 알려주세요
