- 1 -
데이터 구조 실습 (14주차)
2021. 6. 2
1. 다음 이진 트리 T에 대해서 답하시오.
a. T를 배열로 표현하라. 이때 노드 7, 8, 9의 배열 요소 인덱스는 무엇인가?
b. a)로부터 노드의 인덱스가 i일 때, 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드의 인덱 스는 각각 무엇인가?
c. 이진 트리 T를 다음 4가지 방법으로 순회하고자 한다. 각 순회 결과는 무엇인가?
1) 전위 순회:
2) 중위 순회:
3) 후위 순회:
d. c)의 각 순회를 위한 알고리즘을 재귀적 버전으로 작성하라.
1) preorder(T, idx) // T는 트리를 표현하는 배열이고, idx는 트리 노드에 대한 인덱스이다.
2) inorder()
3) postorder()
e. 다음과 같이 main()을 작성하고, 테스트하라. (main() 수행 결과를 c)의 결과와 비교하라)
int main() {
T의 배열 선언 preorder(T, 1);
inorder(T, 1);
postorder(T, 1);
return 0;
}
- 2 -
2. 다음은 디렉토리를 보여준다. 한 디렉토리에 대한 서브디렉토리의 개수는 최대 2개이다.
다음에 답하시오.
a. 위의 디렉토리를 이진 트리로 구성하라. 트리의 노드는 (data, left, right)의 구조체로 표 현된다. 여기서 data는 디렉토리 용량을 나타내며, left, right는 서브 디렉토리를 가리키는 데 사용되는 링크(포인터)이다.
b. a)에서 구성된 디렉토리 D가 주어졌을 때, D의 전체 용량을 계산하여 반환하는 알고리즘 calc_dir()를 재귀적으로 작성하라. 루트 디렉토리(‘나의 문서’)의 용량은 0이다.
c. 다음과 같이 main()을 작성하고, 테스트하라.
트리 노드 타입 정의: TreeNode int main() {
TreeNode *T;
T = cons_dir(); // a)의 트리를 구성하여 반환 calc_dir(T);
return 0;
}
