초기 빈 상태의 트리에 다섯 개의 키 <1, 5, 3, 2, 6&… | [7급 국가직 자료구조론] 21년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 21년 1회차
초기 빈 상태의 트리에 다섯 개의 키 <1, 5, 3, 2, 6>를 차례대로 입력받아 디지털 탐색 트리를 만든 후, 전위 순회한 결과로 옳은 것은? (단, 각 키는 3비트 이진수로 표현한다)
1
1, 3, 2, 5, 6
2
1, 3, 5, 2, 6
3
1, 5, 2, 6, 3
4
1, 5, 3, 2, 6
해설
전위 순회 결과는 1, 3, 2, 5, 6이다. 디지털 탐색 트리는 키를 노드에 저장하며, 내려갈 때마다 키의 비트를 최상위 비트부터 하나씩 보아 0이면 왼쪽, 1이면 오른쪽으로 간다.
1(001): 루트
5(101): 첫 비트 1 → 1의 오른쪽
3(011): 첫 비트 0 → 1의 왼쪽
2(010): 첫 비트 0으로 3에 도달, 둘째 비트 1 → 3의 오른쪽
6(110): 첫 비트 1로 5에 도달, 둘째 비트 1 → 5의 오른쪽루트 → 왼쪽 서브트리(3, 2) → 오른쪽 서브트리(5, 6) 순으로 방문하면 1, 3, 2, 5, 6이다.
- 1, 3, 5, 2, 6은 같은 트리를 레벨 순으로 방문한 결과이다.
- 1, 5, 3, 2, 6은 키의 입력 순서 그대로이다.
오류나 개정된 내용이 보이면 알려주세요