다음 이진 트리에 대하여 전위순회(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이다. 각 노드의 방문 위치를 비교하면 다음과 같다.

노드전위중위후위
A159
B224
C678
D311
E443
F765
G887
H532
I996

B·E·G·I는 전위와 중위에서, D는 중위와 후위에서 위치가 같다. A, C, F, H는 세 순회의 위치가 모두 다르다.

  • 2개: 일치하는 노드 5개 중 일부만 센 값이다.
  • 3개: 전위·중위가 같은 노드만 일부 세고 D를 빠뜨린 값이다.
  • 4개: 전위·중위가 같은 B, E, G, I만 세고 중위·후위가 같은 D를 빠뜨린 값이다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 16년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기