다음 이진 트리에 대하여 전위순회(preorder traversal),… | [7급 국가직 자료구조론] 16년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 16년 1회차
다음 이진 트리에 대하여 전위순회(preorder traversal), 중위순회(inorder traversal), 후위순회(postorder traversal)를 수행하였다. 3가지 순회 방법 중 2가지 이상에서 방문 순서가 동일한 노드 수는? (예를 들어, 3개의 노드 A, B, C를 갖는 이진 트리에서 전위순회 : B-A-C, 중위순회 : A-B-C, 후위순회 : A-C-B의 결과를 얻었다면, 중위순회 및 후위순회에서 노드 A에 대한 방문 순서가 동일하고 전위순회 및 중위순회에서 노드 C에 대한 방문 순서가 동일하므로, 2가지 이상에서 방문 순서가 동일한 노드 수는 2개이다)
1
2
2
3
3
4
4
5
해설
2가지 이상의 순회에서 방문 순서가 같은 노드는 B, D, E, G, I의 5개이다.
세 순회 결과는 전위 A, B, D, E, H, C, F, G, I / 중위 D, B, H, E, A, F, C, G, I / 후위 D, H, E, B, F, I, G, C, A이다. 각 노드의 방문 위치를 비교하면 다음과 같다.
| 노드 | 전위 | 중위 | 후위 |
|---|---|---|---|
| A | 1 | 5 | 9 |
| B | 2 | 2 | 4 |
| C | 6 | 7 | 8 |
| D | 3 | 1 | 1 |
| E | 4 | 4 | 3 |
| F | 7 | 6 | 5 |
| G | 8 | 8 | 7 |
| H | 5 | 3 | 2 |
| I | 9 | 9 | 6 |
B·E·G·I는 전위와 중위에서, D는 중위와 후위에서 위치가 같다. A, C, F, H는 세 순회의 위치가 모두 다르다.
- 2개: 일치하는 노드 5개 중 일부만 센 값이다.
- 3개: 전위·중위가 같은 노드만 일부 세고 D를 빠뜨린 값이다.
- 4개: 전위·중위가 같은 B, E, G, I만 세고 중위·후위가 같은 D를 빠뜨린 값이다.
오류나 개정된 내용이 보이면 알려주세요
