09_tree_bst.c

Download
c 398 lines 10.8 KB 
  1/*
  2 * ํŠธ๋ฆฌ์™€ ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ (Tree and BST)
  3 * Tree Traversal, BST Operations, Tree Properties
  4 *
  5 * ํŠธ๋ฆฌ ์ž๋ฃŒ๊ตฌ์กฐ์˜ ๊ธฐ๋ณธ ์—ฐ์‚ฐ๋“ค์ž…๋‹ˆ๋‹ค.
  6 */
  7
  8#include <stdio.h>
  9#include <stdlib.h>
 10#include <stdbool.h>
 11
 12/* =============================================================================
 13 * 1. ์ด์ง„ ํŠธ๋ฆฌ ๋…ธ๋“œ
 14 * ============================================================================= */
 15
 16typedef struct TreeNode {
 17    int val;
 18    struct TreeNode* left;
 19    struct TreeNode* right;
 20} TreeNode;
 21
 22TreeNode* create_node(int val) {
 23    TreeNode* node = malloc(sizeof(TreeNode));
 24    node->val = val;
 25    node->left = NULL;
 26    node->right = NULL;
 27    return node;
 28}
 29
 30void free_tree(TreeNode* root) {
 31    if (root == NULL) return;
 32    free_tree(root->left);
 33    free_tree(root->right);
 34    free(root);
 35}
 36
 37/* =============================================================================
 38 * 2. ํŠธ๋ฆฌ ์ˆœํšŒ
 39 * ============================================================================= */
 40
 41void preorder(TreeNode* root) {
 42    if (root == NULL) return;
 43    printf("%d ", root->val);
 44    preorder(root->left);
 45    preorder(root->right);
 46}
 47
 48void inorder(TreeNode* root) {
 49    if (root == NULL) return;
 50    inorder(root->left);
 51    printf("%d ", root->val);
 52    inorder(root->right);
 53}
 54
 55void postorder(TreeNode* root) {
 56    if (root == NULL) return;
 57    postorder(root->left);
 58    postorder(root->right);
 59    printf("%d ", root->val);
 60}
 61
 62/* ๋ ˆ๋ฒจ ์ˆœํšŒ (BFS) */
 63void level_order(TreeNode* root) {
 64    if (root == NULL) return;
 65
 66    TreeNode** queue = malloc(1000 * sizeof(TreeNode*));
 67    int front = 0, rear = 0;
 68    queue[rear++] = root;
 69
 70    while (front < rear) {
 71        TreeNode* node = queue[front++];
 72        printf("%d ", node->val);
 73
 74        if (node->left) queue[rear++] = node->left;
 75        if (node->right) queue[rear++] = node->right;
 76    }
 77
 78    free(queue);
 79}
 80
 81/* =============================================================================
 82 * 3. BST ์—ฐ์‚ฐ
 83 * ============================================================================= */
 84
 85TreeNode* bst_insert(TreeNode* root, int val) {
 86    if (root == NULL) return create_node(val);
 87
 88    if (val < root->val)
 89        root->left = bst_insert(root->left, val);
 90    else if (val > root->val)
 91        root->right = bst_insert(root->right, val);
 92
 93    return root;
 94}
 95
 96TreeNode* bst_search(TreeNode* root, int val) {
 97    if (root == NULL || root->val == val)
 98        return root;
 99
100    if (val < root->val)
101        return bst_search(root->left, val);
102    return bst_search(root->right, val);
103}
104
105TreeNode* find_min(TreeNode* root) {
106    while (root && root->left)
107        root = root->left;
108    return root;
109}
110
111TreeNode* find_max(TreeNode* root) {
112    while (root && root->right)
113        root = root->right;
114    return root;
115}
116
117TreeNode* bst_delete(TreeNode* root, int val) {
118    if (root == NULL) return NULL;
119
120    if (val < root->val) {
121        root->left = bst_delete(root->left, val);
122    } else if (val > root->val) {
123        root->right = bst_delete(root->right, val);
124    } else {
125        /* ๋…ธ๋“œ ์ฐพ์Œ */
126        if (root->left == NULL) {
127            TreeNode* temp = root->right;
128            free(root);
129            return temp;
130        } else if (root->right == NULL) {
131            TreeNode* temp = root->left;
132            free(root);
133            return temp;
134        }
135
136        /* ๋‘ ์ž์‹ ์žˆ์Œ: ์˜ค๋ฅธ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ์˜ ์ตœ์†Ÿ๊ฐ’์œผ๋กœ ๋Œ€์ฒด */
137        TreeNode* successor = find_min(root->right);
138        root->val = successor->val;
139        root->right = bst_delete(root->right, successor->val);
140    }
141
142    return root;
143}
144
145/* =============================================================================
146 * 4. ํŠธ๋ฆฌ ์†์„ฑ
147 * ============================================================================= */
148
149int tree_height(TreeNode* root) {
150    if (root == NULL) return 0;
151
152    int left_h = tree_height(root->left);
153    int right_h = tree_height(root->right);
154
155    return 1 + (left_h > right_h ? left_h : right_h);
156}
157
158int count_nodes(TreeNode* root) {
159    if (root == NULL) return 0;
160    return 1 + count_nodes(root->left) + count_nodes(root->right);
161}
162
163int count_leaves(TreeNode* root) {
164    if (root == NULL) return 0;
165    if (root->left == NULL && root->right == NULL) return 1;
166    return count_leaves(root->left) + count_leaves(root->right);
167}
168
169bool is_balanced(TreeNode* root) {
170    if (root == NULL) return true;
171
172    int left_h = tree_height(root->left);
173    int right_h = tree_height(root->right);
174
175    if (abs(left_h - right_h) > 1) return false;
176
177    return is_balanced(root->left) && is_balanced(root->right);
178}
179
180/* BST ๊ฒ€์ฆ */
181bool is_bst_util(TreeNode* root, TreeNode* min_node, TreeNode* max_node) {
182    if (root == NULL) return true;
183
184    if (min_node && root->val <= min_node->val) return false;
185    if (max_node && root->val >= max_node->val) return false;
186
187    return is_bst_util(root->left, min_node, root) &&
188           is_bst_util(root->right, root, max_node);
189}
190
191bool is_bst(TreeNode* root) {
192    return is_bst_util(root, NULL, NULL);
193}
194
195/* =============================================================================
196 * 5. ๊ฒฝ๋กœ ๋ฌธ์ œ
197 * ============================================================================= */
198
199/* ๋ฃจํŠธ์—์„œ ๋ฆฌํ”„๊นŒ์ง€์˜ ๊ฒฝ๋กœ ํ•ฉ */
200bool has_path_sum(TreeNode* root, int target_sum) {
201    if (root == NULL) return false;
202
203    if (root->left == NULL && root->right == NULL)
204        return target_sum == root->val;
205
206    return has_path_sum(root->left, target_sum - root->val) ||
207           has_path_sum(root->right, target_sum - root->val);
208}
209
210/* ์ตœ๋Œ€ ๊ฒฝ๋กœ ํ•ฉ */
211int max_path_sum_util(TreeNode* root, int* max_sum) {
212    if (root == NULL) return 0;
213
214    int left = max_path_sum_util(root->left, max_sum);
215    int right = max_path_sum_util(root->right, max_sum);
216
217    left = left > 0 ? left : 0;
218    right = right > 0 ? right : 0;
219
220    int path_sum = root->val + left + right;
221    if (path_sum > *max_sum) *max_sum = path_sum;
222
223    return root->val + (left > right ? left : right);
224}
225
226int max_path_sum(TreeNode* root) {
227    int max_sum = root ? root->val : 0;
228    max_path_sum_util(root, &max_sum);
229    return max_sum;
230}
231
232/* =============================================================================
233 * 6. LCA (Lowest Common Ancestor)
234 * ============================================================================= */
235
236/* ์ผ๋ฐ˜ ํŠธ๋ฆฌ LCA */
237TreeNode* lca(TreeNode* root, int p, int q) {
238    if (root == NULL) return NULL;
239    if (root->val == p || root->val == q) return root;
240
241    TreeNode* left = lca(root->left, p, q);
242    TreeNode* right = lca(root->right, p, q);
243
244    if (left && right) return root;
245    return left ? left : right;
246}
247
248/* BST LCA */
249TreeNode* lca_bst(TreeNode* root, int p, int q) {
250    if (root == NULL) return NULL;
251
252    if (p < root->val && q < root->val)
253        return lca_bst(root->left, p, q);
254    if (p > root->val && q > root->val)
255        return lca_bst(root->right, p, q);
256
257    return root;
258}
259
260/* =============================================================================
261 * 7. ํŠธ๋ฆฌ ๋ณ€ํ™˜
262 * ============================================================================= */
263
264/* ์ขŒ์šฐ ๋ฐ˜์ „ */
265TreeNode* invert_tree(TreeNode* root) {
266    if (root == NULL) return NULL;
267
268    TreeNode* temp = root->left;
269    root->left = invert_tree(root->right);
270    root->right = invert_tree(temp);
271
272    return root;
273}
274
275/* ํŠธ๋ฆฌ ์ง๋ ฌํ™” (์ „์œ„ ์ˆœํšŒ) */
276void serialize(TreeNode* root, int* arr, int* idx) {
277    if (root == NULL) {
278        arr[(*idx)++] = -1;  /* NULL ํ‘œ์‹œ */
279        return;
280    }
281    arr[(*idx)++] = root->val;
282    serialize(root->left, arr, idx);
283    serialize(root->right, arr, idx);
284}
285
286TreeNode* deserialize(int* arr, int* idx, int n) {
287    if (*idx >= n || arr[*idx] == -1) {
288        (*idx)++;
289        return NULL;
290    }
291
292    TreeNode* node = create_node(arr[(*idx)++]);
293    node->left = deserialize(arr, idx, n);
294    node->right = deserialize(arr, idx, n);
295    return node;
296}
297
298/* =============================================================================
299 * ํ…Œ์ŠคํŠธ
300 * ============================================================================= */
301
302int main(void) {
303    printf("============================================================\n");
304    printf("ํŠธ๋ฆฌ์™€ BST (Tree and BST) ์˜ˆ์ œ\n");
305    printf("============================================================\n");
306
307    /* BST ์ƒ์„ฑ */
308    /*
309     *        50
310     *       /  \
311     *      30   70
312     *     / \   / \
313     *    20 40 60 80
314     */
315    TreeNode* root = NULL;
316    int values[] = {50, 30, 70, 20, 40, 60, 80};
317    for (int i = 0; i < 7; i++) {
318        root = bst_insert(root, values[i]);
319    }
320
321    /* 1. ์ˆœํšŒ */
322    printf("\n[1] ํŠธ๋ฆฌ ์ˆœํšŒ\n");
323    printf("    ์ „์œ„: ");
324    preorder(root);
325    printf("\n");
326    printf("    ์ค‘์œ„: ");
327    inorder(root);
328    printf("\n");
329    printf("    ํ›„์œ„: ");
330    postorder(root);
331    printf("\n");
332    printf("    ๋ ˆ๋ฒจ: ");
333    level_order(root);
334    printf("\n");
335
336    /* 2. BST ์—ฐ์‚ฐ */
337    printf("\n[2] BST ์—ฐ์‚ฐ\n");
338    printf("    ๊ฒ€์ƒ‰ 40: %s\n", bst_search(root, 40) ? "found" : "not found");
339    printf("    ๊ฒ€์ƒ‰ 45: %s\n", bst_search(root, 45) ? "found" : "not found");
340    printf("    ์ตœ์†Ÿ๊ฐ’: %d\n", find_min(root)->val);
341    printf("    ์ตœ๋Œ“๊ฐ’: %d\n", find_max(root)->val);
342
343    /* 3. ํŠธ๋ฆฌ ์†์„ฑ */
344    printf("\n[3] ํŠธ๋ฆฌ ์†์„ฑ\n");
345    printf("    ๋†’์ด: %d\n", tree_height(root));
346    printf("    ๋…ธ๋“œ ์ˆ˜: %d\n", count_nodes(root));
347    printf("    ๋ฆฌํ”„ ์ˆ˜: %d\n", count_leaves(root));
348    printf("    ๊ท ํ˜•: %s\n", is_balanced(root) ? "yes" : "no");
349    printf("    BST: %s\n", is_bst(root) ? "yes" : "no");
350
351    /* 4. ๊ฒฝ๋กœ */
352    printf("\n[4] ๊ฒฝ๋กœ ๋ฌธ์ œ\n");
353    printf("    ๊ฒฝ๋กœ ํ•ฉ 100 ์กด์žฌ: %s\n", has_path_sum(root, 100) ? "yes" : "no");
354    printf("    ์ตœ๋Œ€ ๊ฒฝ๋กœ ํ•ฉ: %d\n", max_path_sum(root));
355
356    /* 5. LCA */
357    printf("\n[5] LCA (์ตœ์†Œ ๊ณตํ†ต ์กฐ์ƒ)\n");
358    TreeNode* ancestor = lca_bst(root, 20, 40);
359    printf("    LCA(20, 40): %d\n", ancestor ? ancestor->val : -1);
360    ancestor = lca_bst(root, 20, 80);
361    printf("    LCA(20, 80): %d\n", ancestor ? ancestor->val : -1);
362
363    /* 6. ์‚ญ์ œ */
364    printf("\n[6] BST ์‚ญ์ œ\n");
365    printf("    ์‚ญ์ œ ์ „ ์ค‘์œ„: ");
366    inorder(root);
367    printf("\n");
368    root = bst_delete(root, 30);
369    printf("    30 ์‚ญ์ œ ํ›„ ์ค‘์œ„: ");
370    inorder(root);
371    printf("\n");
372
373    /* 7. ์ง๋ ฌํ™” */
374    printf("\n[7] ํŠธ๋ฆฌ ์ง๋ ฌํ™”/์—ญ์ง๋ ฌํ™”\n");
375    int serialized[100];
376    int idx = 0;
377    serialize(root, serialized, &idx);
378    printf("    ์ง๋ ฌํ™”: ");
379    for (int i = 0; i < idx; i++) {
380        printf("%d ", serialized[i]);
381    }
382    printf("\n");
383
384    int deserialize_idx = 0;
385    TreeNode* restored = deserialize(serialized, &deserialize_idx, idx);
386    printf("    ๋ณต์› ํ›„ ์ค‘์œ„: ");
387    inorder(restored);
388    printf("\n");
389
390    /* ์ •๋ฆฌ */
391    free_tree(root);
392    free_tree(restored);
393
394    printf("\n============================================================\n");
395
396    return 0;
397}