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