aboutsummaryrefslogtreecommitdiff
path: root/src/tree.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/tree.c')
-rw-r--r--src/tree.c806
1 files changed, 0 insertions, 806 deletions
diff --git a/src/tree.c b/src/tree.c
deleted file mode 100644
index 93690e2..0000000
--- a/src/tree.c
+++ /dev/null
@@ -1,806 +0,0 @@
1// Binary Search Tree
2#include <limits.h>
3#include <stdbool.h>
4#include <stdio.h>
5#include <stdlib.h>
6#include <time.h>
7
8#include "util.h"
9
10/* --8<-- tree_type */
11typedef int T;
12
13struct tree_node {
14 struct tree_node *left, *right;
15 T key;
16 int count; /* collision counter */
17 /* ggf. weitere Felder... */
18};
19/* -->8-- */
20
21/* --8<-- tree_isBst */
22static bool
23tree_isBstUntil(struct tree_node *tree, T min, T max)
24{
25 if ( tree == NULL )
26 return true;
27
28 if ( tree->key < min || tree->key > max )
29 return false;
30
31 return tree_isBstUntil(tree->left, min, tree->key - 1) &&
32 tree_isBstUntil(tree->right, tree->key + 1, max);
33}
34
35bool
36tree_isBst(struct tree_node *tree)
37{
38 return tree_isBstUntil(tree, INT_MIN, INT_MAX);
39}
40/* -->8-- */
41
42/* --8<-- tree_insert */
43struct tree_node *
44tree_insert(struct tree_node *tree, T key)
45{
46 if ( tree == NULL ) {
47 tree = malloc(sizeof *tree);
48 if ( tree ) {
49 tree->key = key;
50 tree->count = 1;
51 tree->left = NULL;
52 tree->right = NULL;
53 }
54 else
55 ERROR("out of memory");
56 }
57 else if ( key < tree->key )
58 tree->left = tree_insert(tree->left, key);
59 else if ( key > tree->key )
60 tree->right = tree_insert(tree->right, key);
61 else /* key == tree->key */
62 tree->count++; /* handle collision */
63
64 return tree;
65}
66/* -->8-- */
67
68/* --8<-- tree_insert_it */
69struct tree_node *
70tree_insert_it(struct tree_node *tree, T key)
71{
72 struct tree_node *parent = NULL;
73
74 for ( struct tree_node *curr = tree; curr; ) {
75 parent = curr;
76
77 if ( key < curr->key ) {
78 curr = curr->left;
79 }
80 else if ( key > curr->key ) {
81 curr = curr->right;
82 }
83 else { /* key == current->key */
84 curr->count++;
85 return tree;
86 }
87 }
88
89 struct tree_node *new_node;
90
91 new_node = malloc(sizeof *new_node);
92 if ( new_node ) {
93 new_node->key = key;
94 new_node->count = 1;
95 new_node->left = NULL;
96 new_node->right = NULL;
97
98 if ( parent == NULL ) {
99 tree = new_node;
100 }
101 else if ( key < parent->key ) {
102 parent->left = new_node;
103 }
104 else {
105 parent->right = new_node;
106 }
107 }
108 else {
109 ERROR("out of memory");
110 }
111
112 return tree;
113}
114/* -->8-- */
115
116/* --8<-- tree_detach_min */
117static struct tree_node *
118tree_detach_min(struct tree_node **ptree)
119{
120 struct tree_node *tree = *ptree;
121
122 if ( tree == NULL )
123 return NULL;
124 else if ( tree->left )
125 return tree_detach_min(&tree->left);
126 else {
127 *ptree = tree->right;
128 return tree;
129 }
130}
131/* -->8-- */
132
133/* --8<-- tree_remove */
134struct tree_node *
135tree_remove(struct tree_node *tree, T key)
136{
137 if ( tree == NULL )
138 return NULL;
139
140 if ( key < tree->key )
141 tree->left = tree_remove(tree->left, key);
142 else if ( key > tree->key )
143 tree->right = tree_remove(tree->right, key);
144 else { /* key == tree->key */
145 if ( --tree->count == 0 ) { /* Handle Collision */
146 struct tree_node *temp = tree;
147
148 if ( tree->left == NULL ) {
149 tree = tree->right;
150 }
151 else if ( tree->right == NULL ) {
152 tree = tree->left;
153 }
154 else {
155 struct tree_node *min = tree_detach_min(&tree->right);
156
157 min->left = tree->left;
158 min->right = tree->right;
159
160 tree = min;
161 }
162
163 free(temp);
164 }
165 }
166 return tree;
167}
168/* -->8-- */
169
170/* --8<-- tree_clear */
171void
172tree_clear(struct tree_node *tree)
173{
174 if ( tree ) {
175 tree_clear(tree->left);
176 tree_clear(tree->right);
177 free(tree);
178 }
179}
180/* -->8-- */
181
182/* --8<-- tree_lookup */
183struct tree_node *
184tree_lookup(struct tree_node *tree, T key)
185{
186 while ( tree )
187 if ( key < tree->key )
188 tree = tree->left;
189 else if ( key > tree->key )
190 tree = tree->right;
191 else /* key == tree->key */
192 break;
193
194 return tree;
195}
196/* -->8-- */
197
198/* --8<-- tree_minimum */
199struct tree_node *
200tree_minimum(struct tree_node *tree)
201{
202 if ( tree )
203 while ( tree->left )
204 tree = tree->left;
205
206 return tree;
207}
208/* -->8-- */
209
210/* --8<-- tree_maximum */
211struct tree_node *
212tree_maximum(struct tree_node *tree)
213{
214 if ( tree )
215 while ( tree->right )
216 tree = tree->right;
217
218 return tree;
219}
220/* -->8-- */
221
222/* --8<-- tree_height */
223size_t
224tree_height(struct tree_node *tree)
225{
226 if ( tree ) {
227 size_t hl = tree_height(tree->left);
228 size_t hr = tree_height(tree->right);
229
230 return ((hl > hr) ? hl : hr) + 1;
231 }
232
233 return 0;
234}
235/* -->8-- */
236
237/* --8<-- tree_count */
238size_t
239tree_count(struct tree_node *tree)
240{
241 if ( tree )
242 return tree_count(tree->left) + tree_count(tree->right) + 1;
243
244 return 0;
245}
246/* -->8-- */
247
248/* --8<-- tree_copy */
249struct tree_node *
250tree_copy(struct tree_node *tree)
251{
252 if ( tree ) {
253 struct tree_node *new_node;
254
255 new_node = malloc(sizeof *new_node);
256 if ( new_node ) {
257 new_node->key = tree->key;
258 new_node->count = tree->count;
259 new_node->left = tree_copy(tree->left);
260 new_node->right = tree_copy(tree->right);
261 }
262 else {
263 ERROR("out of memory");
264 }
265
266 return new_node;
267 }
268 return NULL;
269}
270/* -->8-- */
271
272/* --8<-- tree_isleaf */
273bool
274tree_isleaf(struct tree_node *tree)
275{
276 return tree->left == NULL && tree->right == NULL;
277}
278/* -->8-- */
279
280/* --8<-- tree_apply_preorder */
281void
282tree_apply_preorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
283{
284 if ( tree ) {
285 visit(tree->key, cl);
286 tree_apply_preorder(tree->left, visit, cl);
287 tree_apply_preorder(tree->right, visit, cl);
288 }
289}
290/* -->8-- */
291
292/* --8<-- tree_apply_inorder */
293void
294tree_apply_inorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
295{
296 if ( tree ) {
297 tree_apply_inorder(tree->left, visit, cl);
298 visit(tree->key, cl);
299 tree_apply_inorder(tree->right, visit, cl);
300 }
301}
302/* -->8-- */
303
304/* --8<-- tree_apply_postorder */
305void
306tree_apply_postorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
307{
308 if ( tree ) {
309 tree_apply_postorder(tree->left, visit, cl);
310 tree_apply_postorder(tree->right, visit, cl);
311 visit(tree->key, cl);
312 }
313}
314/* -->8-- */
315
316/* ===== */
317
318/* --8<-- tree_stack_type */
319struct stack_item {
320 struct stack_item *next;
321 struct tree_node * data;
322};
323
324struct stack {
325 struct stack_item *head;
326};
327/* -->8-- */
328
329/* --8<-- tree_stack_init */
330static void
331stack_init(struct stack *stack)
332{
333 stack->head = NULL;
334}
335/* -->8-- */
336
337/* --8<-- tree_stack_push */
338static void
339stack_push(struct stack *stack, struct tree_node *data)
340{
341 struct stack_item *new_item;
342
343 if ( (new_item = malloc(sizeof *new_item)) ) {
344 new_item->data = data;
345 new_item->next = stack->head;
346 stack->head = new_item;
347 }
348 else
349 ERROR("out of memory");
350}
351/* -->8-- */
352
353/* --8<-- tree_stack_pop */
354static bool
355stack_pop(struct stack *stack, struct tree_node **data)
356{
357 if ( stack->head ) {
358 struct stack_item *next;
359
360 next = stack->head->next;
361 *data = stack->head->data;
362
363 free(stack->head);
364 stack->head = next;
365
366 return true;
367 }
368 else
369 return false;
370}
371/* -->8-- */
372
373/* --8<-- tree_stack_peek */
374static struct tree_node *
375stack_peek(struct stack *stack)
376{
377 return (stack->head) ? stack->head->data : NULL;
378}
379/* -->8-- */
380
381/* --8<-- tree_stack_empty */
382static bool
383stack_empty(struct stack *stack)
384{
385 return stack->head == NULL;
386}
387/* -->8-- */
388
389/* --8<-- tree_stack_free */
390void
391stack_free(struct stack *stack)
392{
393 struct stack_item *item, *next;
394
395 for ( item = stack->head; item; item = next ) {
396 next = item->next;
397 free(item);
398 }
399}
400/* -->8-- */
401
402/* ===== */
403
404/* --8<-- tree_queue_type */
405struct queue_item {
406 struct queue_item *next;
407 struct tree_node * data;
408};
409
410struct queue {
411 struct queue_item *head, *tail;
412};
413/* -->8-- */
414
415/* --8<-- tree_queue_init */
416void
417queue_init(struct queue *queue)
418{
419 queue->head = NULL;
420}
421/* -->8-- */
422
423/* --8<-- tree_queue_put */
424void
425queue_put(struct queue *queue, struct tree_node *data)
426{
427 struct queue_item *new_item;
428
429 if ( (new_item = malloc(sizeof *new_item)) ) {
430 struct queue_item *tail;
431
432 tail = queue->tail;
433 new_item->data = data;
434 new_item->next = NULL;
435 queue->tail = new_item;
436
437 if ( queue->head == NULL )
438 queue->head = queue->tail;
439 else
440 tail->next = queue->tail;
441 }
442 else
443 ERROR("out of memory");
444}
445/* -->8-- */
446
447/* --8<-- tree_queue_get */
448bool
449queue_get(struct queue *queue, struct tree_node **data)
450{
451 if ( queue->head ) {
452 struct queue_item *next;
453
454 next = queue->head->next;
455 *data = queue->head->data;
456
457 free(queue->head);
458 queue->head = next;
459
460 return true;
461 }
462 else
463 return false;
464}
465/* -->8-- */
466
467/* --8<-- tree_queue_empty */
468bool
469queue_empty(struct queue *queue)
470{
471 return queue->head == NULL;
472}
473/* -->8-- */
474
475/* --8<-- tree_queue_free */
476void
477queue_free(struct queue *queue)
478{
479 struct queue_item *item, *next;
480
481 for ( item = queue->head; item; item = next ) {
482 next = item->next;
483 free(item);
484 }
485}
486/* -->8-- */
487
488/* ===== */
489
490/* --8<-- tree_apply_preorder_it */
491void
492tree_apply_preorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
493{
494 if ( tree ) {
495 struct stack stack;
496
497 stack_init(&stack);
498
499 stack_push(&stack, tree);
500
501 while ( stack_pop(&stack, &tree) ) {
502 visit(tree->key, cl);
503
504 if ( tree->right )
505 stack_push(&stack, tree->right);
506 if ( tree->left )
507 stack_push(&stack, tree->left);
508 }
509
510 stack_free(&stack);
511 }
512}
513/* -->8-- */
514
515/* --8<-- tree_apply_inorder_it */
516void
517tree_apply_inorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
518{
519 if ( tree ) {
520 struct stack stack;
521
522 stack_init(&stack);
523
524 while ( !stack_empty(&stack) || tree ) {
525 if ( tree ) {
526 stack_push(&stack, tree);
527 tree = tree->left;
528 }
529 else {
530 stack_pop(&stack, &tree);
531 visit(tree->key, cl);
532 tree = tree->right;
533 }
534 }
535
536 stack_free(&stack);
537 }
538}
539/* -->8-- */
540
541// Hier eine Version für PostOrder-Iterativ:
542// Quelle: https://stackoverflow.com/a/16092333
543
544/* --8<-- tree_apply_postorder_it */
545void
546tree_apply_postorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
547{
548 if ( tree ) {
549 struct stack stack;
550
551 stack_init(&stack);
552 stack_push(&stack, tree);
553
554 while ( !stack_empty(&stack) ) {
555 struct tree_node *next = stack_peek(&stack);
556
557 bool finishedSubtrees = (next->left == tree || next->right == tree);
558
559 if ( finishedSubtrees || tree_isleaf(next) ) {
560 stack_pop(&stack, &next);
561
562 visit(next->key, cl);
563
564 tree = next;
565 }
566 else {
567 if ( next->right ) {
568 stack_push(&stack, next->right);
569 }
570 if ( next->left ) {
571 stack_push(&stack, next->left);
572 }
573 }
574 }
575 stack_free(&stack);
576 }
577}
578/* -->8-- */
579
580/* --8<-- tree_apply_levelorder_it */
581void
582tree_apply_levelorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
583{
584 if ( tree ) {
585 struct queue queue;
586
587 queue_init(&queue);
588
589 queue_put(&queue, tree);
590
591 while ( queue_get(&queue, &tree) ) {
592 visit(tree->key, cl);
593
594 if ( tree->left )
595 queue_put(&queue, tree->left);
596 if ( tree->right )
597 queue_put(&queue, tree->right);
598 }
599
600 queue_free(&queue);
601 }
602}
603/* -->8-- */
604
605/* ======================== */
606
607/* --8<-- tree_iterator_type */
608struct tree_iterator {
609 struct stack stack;
610};
611/* -->8-- */
612
613/* --8<-- tree_iterator_push_leftmost */
614static void
615tree_iterator_push_leftmost(struct stack *stack, struct tree_node *node)
616{
617 for ( ; node; node = node->left ) {
618 stack_push(stack, node);
619 }
620}
621/* -->8-- */
622
623/* --8<-- tree_iterator_next */
624struct tree_node *
625tree_iterator_next(struct tree_iterator *it)
626{
627 struct tree_node *node = NULL;
628
629 if ( stack_pop(&it->stack, &node) ) {
630 tree_iterator_push_leftmost(&it->stack, node->right);
631 }
632
633 return node;
634}
635/* -->8-- */
636
637/* --8<-- tree_iterator_first */
638struct tree_node *
639tree_iterator_first(struct tree_iterator *it, struct tree_node *tree)
640{
641 stack_init(&it->stack);
642
643 tree_iterator_push_leftmost(&it->stack, tree);
644
645 return tree_iterator_next(it);
646}
647/* -->8-- */
648
649/* --8<-- tree_iterator_free */
650void
651tree_iterator_free(struct tree_iterator *it)
652{
653 stack_free(&it->stack);
654}
655/* -->8-- */
656
657/* --8<-- tree_preorder_iterator_next */
658struct tree_node *
659tree_preorder_iterator_next(struct tree_iterator *it)
660{
661 struct tree_node *node = NULL;
662
663 if ( stack_pop(&it->stack, &node) ) {
664 if ( node->right ) {
665 stack_push(&it->stack, node->right);
666 }
667 if ( node->left ) {
668 stack_push(&it->stack, node->left);
669 }
670 }
671
672 return node;
673}
674/* -->8-- */
675
676/* --8<-- tree_preorder_iterator_first */
677struct tree_node *
678tree_preorder_iterator_first(struct tree_iterator *it, struct tree_node *tree)
679{
680 stack_init(&it->stack);
681
682 if ( tree ) {
683 stack_push(&it->stack, tree);
684
685 return tree_preorder_iterator_next(it);
686 }
687 else {
688 return NULL;
689 }
690}
691/* -->8-- */
692
693/* ===== */
694
695void
696print(T data, void *cl)
697{
698 (void) cl;
699 printf("%d\n", data);
700}
701
702#include "treeutil.h"
703
704int
705main_(void)
706{
707 // Teste den Fall von mycodeschool
708
709 struct tree_node *tree = NULL;
710
711 tree = tree_insert(tree, 12);
712 tree = tree_insert(tree, 5);
713 tree = tree_insert(tree, 15);
714 tree = tree_insert(tree, 3);
715 tree = tree_insert(tree, 7);
716 tree = tree_insert(tree, 13);
717 tree = tree_insert(tree, 17);
718 tree = tree_insert(tree, 1);
719 tree = tree_insert(tree, 9);
720 tree = tree_insert(tree, 14);
721 tree = tree_insert(tree, 20);
722 tree = tree_insert(tree, 8);
723 tree = tree_insert(tree, 11);
724 tree = tree_insert(tree, 18);
725
726 tree = tree_remove(tree, 15);
727
728 if ( !tree_isBst(tree) ) {
729 fprintf(stderr, "Tree ist kein BST!!\n");
730 return EXIT_FAILURE;
731 }
732
733 show_tree(tree, 0, 0);
734
735 tree_clear(tree);
736
737 return EXIT_SUCCESS;
738}
739
740int
741main__(void)
742{
743 struct tree_node *tree = NULL;
744
745 tree = tree_insert(tree, 5);
746 tree = tree_insert(tree, 3);
747 tree = tree_insert(tree, 7);
748 tree = tree_insert(tree, 2);
749 tree = tree_insert(tree, 4);
750 tree = tree_insert(tree, 6);
751 tree = tree_insert(tree, 8);
752
753 tree = tree_remove(tree, 2);
754 tree = tree_remove(tree, 3);
755 tree = tree_remove(tree, 5);
756
757 if ( !tree_isBst(tree) ) {
758 fprintf(stderr, "Tree ist kein BST!!\n");
759 return EXIT_FAILURE;
760 }
761
762 show_tree(tree, 0, 0);
763
764 tree_clear(tree);
765
766 return EXIT_SUCCESS;
767}
768
769int
770main(void)
771{
772 struct tree_node *tree = NULL;
773
774 tree = tree_insert_it(tree, 10);
775 tree = tree_insert_it(tree, 5);
776 tree = tree_insert_it(tree, 20);
777 tree = tree_insert_it(tree, 1);
778 tree = tree_insert_it(tree, 7);
779 tree = tree_insert_it(tree, 15);
780 tree = tree_insert_it(tree, 18);
781
782 tree_apply_preorder(tree, print, NULL);
783 puts("postorder:");
784 tree_apply_postorder(tree, print, NULL);
785 puts("postorder_it:");
786 tree_apply_postorder_it(tree, print, NULL);
787 show_tree(tree, 0, 0);
788
789 puts("levelorder_it:");
790 tree_apply_levelorder_it(tree, print, NULL);
791
792 show_tree(tree, 0, 0);
793
794 struct tree_iterator it;
795 struct tree_node * node = tree_preorder_iterator_first(&it, tree);
796 while ( node ) {
797 fprintf(stdout, "%d\n", node->key);
798
799 node = tree_preorder_iterator_next(&it);
800 }
801 tree_iterator_free(&it);
802
803 tree_clear(tree);
804
805 return EXIT_SUCCESS;
806}