[Exercises 1]
/*
For the binary tree of Figure 5.15, list the leaf nodes, the nonleaf nodes, and the level of each node
5.15에서 제시하는 이진트리에서 단말노드, 단말노드가 아닌 노드들, 그리고 각 노드의 높이를 명시한다
*/
leaf nodes(단말노드) :D, E
non-leaf nodes(그 외 노드들): A, B, C
A(level 1)
B(level 2)
C(level 3)
D(level 3)
E(level 4)
[Figure 5.15]
[Exercises 2]
/*
What is the maximum number of nodes in a k-ary tree of height h?
h 높이의 k진 트리의 최대 노드의 수는?
*/
1 + k + k ^ 2 + ... + k ^ (h - 1) + k ^ h = (k ^ (h + 1) - 1) / (k - 1)
[Exercises 3]
/*
Draw the internal memory representation of the binary tree of Figure 5.15 using (a) sequential and (b) linked representations
5.15에서 제시한 이진트리에 대해 배열 메모리 구조와 링크드리스트 메모리 구조를 그려본다
*/
[배열]
[링크드 리스트]
[Exercises 4]
/*
Extend the array representation of a complete binary tree to the case of complete trees whose degree is d, d>1
배열로 표현된 완벽 이진트리을 완벽 d진트리로 확장한다.
Develop formulas for the parent and children node stored in position i of the array.
배열의 i번째 위치에 있는 노드의 부모노드와 자식노드를 구하는 공식을 구한다
*/
parent node(부모 노드):(-2*d+i)/d
children node(자식 노드들): d*i-d+2, d*i-d+3, d*i-d+4, ..., d*i, d*i+1
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.