반응형
1. 4
2. 2
3. 4
4. 3
5. 1
6. A B * C D / +
7. 4
8. 3
9.
이진탐색트리는 최악의 경우 배열과 다름없이 만들어질 수 있다. 따라서, 삽입연산 최악의 시간복잡도는 O(n) 평균의 시간복잡도는 O(logn)이 된다.
12.
Tree의 모든 노드 중 가장 큰 키 값을 반환하는 코드로 '8'을 반환한다.
13.
int get_height(TreeNode* node) {
int height = 0;
if (node != NULL)
height = 1 + max(get_height(node->left), get_height(node->right);
}
bool isBalanced(TreeNode* node){
if (node == NULL)
return true;
int leftHeight = getHeight(node->getLeft());
int rightHeight = getHeight(node->getRight());
//왼쪽 서브트리와 오른쪽서브트리의 높이차가 2이상 나지 않고 둘 다 균형이 잡혀있을 경우 참
if ((leftHeight - rightHeight) <= 1 && (leftHeight - rightHeight) >= -1 && isBalanced(node->getLeft()) && isBalanced(node->getRight()))
return true;
return false;
}
14.
int get_sum(TreeNode* root) {
if (root == NULL)
return 0;
int sum = root->data;
sum = sum + get_sum(root->left) + get_sum(root->right);
return sum;
}
15.
void find_smaller_than_value(TreeNode* root, int value) {
if (root == NULL)
return;
if (root->data < value)
printf("%d보다 작은 노드 : %d\n", value, root->data);
find_smaller_than_value(root->left, value);
find_smaller_than_value(root->right, value);
}
16.
int find_leftorright(TreeNode* root) {
if (root == NULL)
return 0;
int count = 0;
if ((root->left == NULL && root->right != NULL) || (root->left != NULL && root->right == NULL))
count++;
count = count + find_leftorright(root->left) + find_leftorright(root->right);
return count;
}
17.
#define MAX 987654321
#define MIN -987654321
int max(int a, int b) {
if (a < b)
return b;
return a;
}
int min(int a, int b) {
if (a < b)
return a;
retu
int find_min(TreeNode* root) {
if (root == NULL)
return MAX;
int min_value = root->data;
min_value = min(min_value, find_min(root->left));
min_value = min(min_value, find_min(root->right));
return min_value;
}
int find_max(TreeNode *root) {
if (root == NULL)
return MIN;
int max_value = root->data;
max_value = max(max_value, find_max(root->left));
max_value = max(max_value, find_max(root->right));
return max_value;
}
18.
void binary_search_tree_inorder(TreeNode* root) {
if (root == NULL)
return;
binary_search_tree_inorder(root->left);
printf("%d ", root->data);
binary_search_tree_inorder(root->right);
}
int main(void) {
int list[11] = { 11,3,4,1,56,5,6,2,98,32,23 };
TreeNode* root = NULL;
for (int i = 0; i < 11; i++)
insert_node(&root, list[i]);
binary_search_tree_inorder(root);
}
19.
void binary_search_tree_decreasing_inorder(TreeNode* root) {
if (root == NULL)
return;
binary_search_tree_decreasing_inorder(root->right);
printf("%d ", root->data);
binary_search_tree_decreasing_inorder(root->left);
}
int main(void) {
int list[11] = { 11,3,4,1,56,5,6,2,98,32,23 };
TreeNode* root = NULL;
for (int i = 0; i < 11; i++)
insert_node(&root, list[i]);
binary_search_tree_decreasing_inorder(root);
}
20.
void search_tree_plus_one(TreeNode* root) {
if (root == NULL)
return;
fsearch_tree_plus_one(root->right);
root->data++;
search_tree_plus_one(root->left);
}
21.
트리의 루트에서 오른쪽서브트리로 계속 순회를 진행해, 트리의 가장 오른쪽 리프노드에 도달하면 그 값이 가장 큰 값이다.
관심이 있으신 분들에게 유용한 정보였길 바라며
다음은 9장 핵심정리를 가져오도록 하겠습니다.
반응형