aboutsummaryrefslogtreecommitdiff
path: root/tree.c
diff options
context:
space:
mode:
Diffstat (limited to 'tree.c')
-rw-r--r--tree.c80
1 files changed, 80 insertions, 0 deletions
diff --git a/tree.c b/tree.c
index cc2ae53..f6ccc5a 100644
--- a/tree.c
+++ b/tree.c
@@ -7,6 +7,7 @@
7 7
8#include "util.h" 8#include "util.h"
9 9
10/* --8<-- tree_type */
10typedef int T; 11typedef int T;
11 12
12struct tree_node { 13struct tree_node {
@@ -15,7 +16,9 @@ struct tree_node {
15 int count; /* collision counter */ 16 int count; /* collision counter */
16 /* ggf. weitere Felder... */ 17 /* ggf. weitere Felder... */
17}; 18};
19/* -->8-- */
18 20
21/* --8<-- tree_isBst */
19static bool 22static bool
20tree_isBstUntil(struct tree_node *tree, T min, T max) 23tree_isBstUntil(struct tree_node *tree, T min, T max)
21{ 24{
@@ -34,7 +37,9 @@ tree_isBst(struct tree_node *tree)
34{ 37{
35 return tree_isBstUntil(tree, INT_MIN, INT_MAX); 38 return tree_isBstUntil(tree, INT_MIN, INT_MAX);
36} 39}
40/* -->8-- */
37 41
42/* --8<-- tree_insert */
38struct tree_node * 43struct tree_node *
39tree_insert(struct tree_node *tree, T key) 44tree_insert(struct tree_node *tree, T key)
40{ 45{
@@ -58,7 +63,9 @@ tree_insert(struct tree_node *tree, T key)
58 63
59 return tree; 64 return tree;
60} 65}
66/* -->8-- */
61 67
68/* --8<-- tree_insert_it */
62struct tree_node * 69struct tree_node *
63tree_insert_it(struct tree_node *tree, T key) 70tree_insert_it(struct tree_node *tree, T key)
64{ 71{
@@ -104,7 +111,9 @@ tree_insert_it(struct tree_node *tree, T key)
104 111
105 return tree; 112 return tree;
106} 113}
114/* -->8-- */
107 115
116/* --8<-- tree_detach_min */
108static struct tree_node * 117static struct tree_node *
109tree_detach_min(struct tree_node **ptree) 118tree_detach_min(struct tree_node **ptree)
110{ 119{
@@ -119,7 +128,9 @@ tree_detach_min(struct tree_node **ptree)
119 return tree; 128 return tree;
120 } 129 }
121} 130}
131/* -->8-- */
122 132
133/* --8<-- tree_remove */
123struct tree_node * 134struct tree_node *
124tree_remove(struct tree_node *tree, T key) 135tree_remove(struct tree_node *tree, T key)
125{ 136{
@@ -154,7 +165,9 @@ tree_remove(struct tree_node *tree, T key)
154 } 165 }
155 return tree; 166 return tree;
156} 167}
168/* -->8-- */
157 169
170/* --8<-- tree_clear */
158void 171void
159tree_clear(struct tree_node *tree) 172tree_clear(struct tree_node *tree)
160{ 173{
@@ -164,7 +177,9 @@ tree_clear(struct tree_node *tree)
164 free(tree); 177 free(tree);
165 } 178 }
166} 179}
180/* -->8-- */
167 181
182/* --8<-- tree_lookup */
168struct tree_node * 183struct tree_node *
169tree_lookup(struct tree_node *tree, T key) 184tree_lookup(struct tree_node *tree, T key)
170{ 185{
@@ -178,7 +193,9 @@ tree_lookup(struct tree_node *tree, T key)
178 193
179 return tree; 194 return tree;
180} 195}
196/* -->8-- */
181 197
198/* --8<-- tree_minimum */
182struct tree_node * 199struct tree_node *
183tree_minimum(struct tree_node *tree) 200tree_minimum(struct tree_node *tree)
184{ 201{
@@ -188,7 +205,9 @@ tree_minimum(struct tree_node *tree)
188 205
189 return tree; 206 return tree;
190} 207}
208/* -->8-- */
191 209
210/* --8<-- tree_maximum */
192struct tree_node * 211struct tree_node *
193tree_maximum(struct tree_node *tree) 212tree_maximum(struct tree_node *tree)
194{ 213{
@@ -198,7 +217,9 @@ tree_maximum(struct tree_node *tree)
198 217
199 return tree; 218 return tree;
200} 219}
220/* -->8-- */
201 221
222/* --8<-- tree_height */
202size_t 223size_t
203tree_height(struct tree_node *tree) 224tree_height(struct tree_node *tree)
204{ 225{
@@ -211,7 +232,9 @@ tree_height(struct tree_node *tree)
211 232
212 return 0; 233 return 0;
213} 234}
235/* -->8-- */
214 236
237/* --8<-- tree_count */
215size_t 238size_t
216tree_count(struct tree_node *tree) 239tree_count(struct tree_node *tree)
217{ 240{
@@ -220,13 +243,17 @@ tree_count(struct tree_node *tree)
220 243
221 return 0; 244 return 0;
222} 245}
246/* -->8-- */
223 247
248/* --8<-- tree_isleaf */
224bool 249bool
225tree_isleaf(struct tree_node *tree) 250tree_isleaf(struct tree_node *tree)
226{ 251{
227 return tree->left == NULL && tree->right == NULL; 252 return tree->left == NULL && tree->right == NULL;
228} 253}
254/* -->8-- */
229 255
256/* --8<-- tree_apply_preorder */
230void 257void
231tree_apply_preorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) 258tree_apply_preorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
232{ 259{
@@ -236,7 +263,9 @@ tree_apply_preorder(struct tree_node *tree, void (*visit)(T key, void *cl), void
236 tree_apply_preorder(tree->right, visit, cl); 263 tree_apply_preorder(tree->right, visit, cl);
237 } 264 }
238} 265}
266/* -->8-- */
239 267
268/* --8<-- tree_apply_inorder */
240void 269void
241tree_apply_inorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) 270tree_apply_inorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
242{ 271{
@@ -246,7 +275,9 @@ tree_apply_inorder(struct tree_node *tree, void (*visit)(T key, void *cl), void
246 tree_apply_inorder(tree->right, visit, cl); 275 tree_apply_inorder(tree->right, visit, cl);
247 } 276 }
248} 277}
278/* -->8-- */
249 279
280/* --8<-- tree_apply_postorder */
250void 281void
251tree_apply_postorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) 282tree_apply_postorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
252{ 283{
@@ -256,9 +287,11 @@ tree_apply_postorder(struct tree_node *tree, void (*visit)(T key, void *cl), voi
256 visit(tree->key, cl); 287 visit(tree->key, cl);
257 } 288 }
258} 289}
290/* -->8-- */
259 291
260/* ===== */ 292/* ===== */
261 293
294/* --8<-- tree_stack_type */
262struct stack_item { 295struct stack_item {
263 struct stack_item *next; 296 struct stack_item *next;
264 struct tree_node * data; 297 struct tree_node * data;
@@ -267,13 +300,17 @@ struct stack_item {
267struct stack { 300struct stack {
268 struct stack_item *head; 301 struct stack_item *head;
269}; 302};
303/* -->8-- */
270 304
305/* --8<-- tree_stack_init */
271static void 306static void
272stack_init(struct stack *stack) 307stack_init(struct stack *stack)
273{ 308{
274 stack->head = NULL; 309 stack->head = NULL;
275} 310}
311/* -->8-- */
276 312
313/* --8<-- tree_stack_push */
277static void 314static void
278stack_push(struct stack *stack, struct tree_node *data) 315stack_push(struct stack *stack, struct tree_node *data)
279{ 316{
@@ -287,7 +324,9 @@ stack_push(struct stack *stack, struct tree_node *data)
287 else 324 else
288 ERROR("out of memory"); 325 ERROR("out of memory");
289} 326}
327/* -->8-- */
290 328
329/* --8<-- tree_stack_pop */
291static bool 330static bool
292stack_pop(struct stack *stack, struct tree_node **data) 331stack_pop(struct stack *stack, struct tree_node **data)
293{ 332{
@@ -305,19 +344,25 @@ stack_pop(struct stack *stack, struct tree_node **data)
305 else 344 else
306 return false; 345 return false;
307} 346}
347/* -->8-- */
308 348
349/* --8<-- tree_stack_peek */
309static struct tree_node * 350static struct tree_node *
310stack_peek(struct stack *stack) 351stack_peek(struct stack *stack)
311{ 352{
312 return (stack->head != NULL) ? stack->head->data : NULL; 353 return (stack->head != NULL) ? stack->head->data : NULL;
313} 354}
355/* -->8-- */
314 356
357/* --8<-- tree_stack_empty */
315static bool 358static bool
316stack_empty(struct stack *stack) 359stack_empty(struct stack *stack)
317{ 360{
318 return stack->head == NULL; 361 return stack->head == NULL;
319} 362}
363/* -->8-- */
320 364
365/* --8<-- tree_stack_free */
321void 366void
322stack_free(struct stack *stack) 367stack_free(struct stack *stack)
323{ 368{
@@ -328,9 +373,11 @@ stack_free(struct stack *stack)
328 free(item); 373 free(item);
329 } 374 }
330} 375}
376/* -->8-- */
331 377
332/* ===== */ 378/* ===== */
333 379
380/* --8<-- tree_queue_type */
334struct queue_item { 381struct queue_item {
335 struct queue_item *next; 382 struct queue_item *next;
336 struct tree_node * data; 383 struct tree_node * data;
@@ -339,13 +386,17 @@ struct queue_item {
339struct queue { 386struct queue {
340 struct queue_item *head, *tail; 387 struct queue_item *head, *tail;
341}; 388};
389/* -->8-- */
342 390
391/* --8<-- tree_queue_init */
343void 392void
344queue_init(struct queue *queue) 393queue_init(struct queue *queue)
345{ 394{
346 queue->head = NULL; 395 queue->head = NULL;
347} 396}
397/* -->8-- */
348 398
399/* --8<-- tree_queue_put */
349void 400void
350queue_put(struct queue *queue, struct tree_node *data) 401queue_put(struct queue *queue, struct tree_node *data)
351{ 402{
@@ -367,7 +418,9 @@ queue_put(struct queue *queue, struct tree_node *data)
367 else 418 else
368 ERROR("out of memory"); 419 ERROR("out of memory");
369} 420}
421/* -->8-- */
370 422
423/* --8<-- tree_queue_get */
371bool 424bool
372queue_get(struct queue *queue, struct tree_node **data) 425queue_get(struct queue *queue, struct tree_node **data)
373{ 426{
@@ -385,13 +438,17 @@ queue_get(struct queue *queue, struct tree_node **data)
385 else 438 else
386 return false; 439 return false;
387} 440}
441/* -->8-- */
388 442
443/* --8<-- tree_queue_empty */
389bool 444bool
390queue_empty(struct queue *queue) 445queue_empty(struct queue *queue)
391{ 446{
392 return queue->head == NULL; 447 return queue->head == NULL;
393} 448}
449/* -->8-- */
394 450
451/* --8<-- tree_queue_free */
395void 452void
396queue_free(struct queue *queue) 453queue_free(struct queue *queue)
397{ 454{
@@ -402,9 +459,11 @@ queue_free(struct queue *queue)
402 free(item); 459 free(item);
403 } 460 }
404} 461}
462/* -->8-- */
405 463
406/* ===== */ 464/* ===== */
407 465
466/* --8<-- tree_apply_preorder_it */
408void 467void
409tree_apply_preorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) 468tree_apply_preorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
410{ 469{
@@ -427,7 +486,9 @@ tree_apply_preorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), v
427 stack_free(&stack); 486 stack_free(&stack);
428 } 487 }
429} 488}
489/* -->8-- */
430 490
491/* --8<-- tree_apply_inorder_it */
431void 492void
432tree_apply_inorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) 493tree_apply_inorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
433{ 494{
@@ -451,10 +512,12 @@ tree_apply_inorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), vo
451 stack_free(&stack); 512 stack_free(&stack);
452 } 513 }
453} 514}
515/* -->8-- */
454 516
455// Hier eine Version für PostOrder-Iterativ: 517// Hier eine Version für PostOrder-Iterativ:
456// Quelle: https://stackoverflow.com/a/16092333 518// Quelle: https://stackoverflow.com/a/16092333
457 519
520/* --8<-- tree_apply_postorder_it */
458void 521void
459tree_apply_postorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) 522tree_apply_postorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
460{ 523{
@@ -488,7 +551,9 @@ tree_apply_postorder_it(struct tree_node *tree, void (*visit)(T key, void *cl),
488 stack_free(&stack); 551 stack_free(&stack);
489 } 552 }
490} 553}
554/* -->8-- */
491 555
556/* --8<-- tree_apply_levelorder_it */
492void 557void
493tree_apply_levelorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) 558tree_apply_levelorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
494{ 559{
@@ -511,13 +576,17 @@ tree_apply_levelorder_it(struct tree_node *tree, void (*visit)(T key, void *cl),
511 queue_free(&queue); 576 queue_free(&queue);
512 } 577 }
513} 578}
579/* -->8-- */
514 580
515/* ======================== */ 581/* ======================== */
516 582
583/* --8<-- tree_iterator_type */
517struct tree_iterator { 584struct tree_iterator {
518 struct stack stack; 585 struct stack stack;
519}; 586};
587/* -->8-- */
520 588
589/* --8<-- tree_iterator_push_leftmost */
521static void 590static void
522tree_iterator_push_leftmost(struct stack *stack, struct tree_node *node) 591tree_iterator_push_leftmost(struct stack *stack, struct tree_node *node)
523{ 592{
@@ -525,7 +594,9 @@ tree_iterator_push_leftmost(struct stack *stack, struct tree_node *node)
525 stack_push(stack, node); 594 stack_push(stack, node);
526 } 595 }
527} 596}
597/* -->8-- */
528 598
599/* --8<-- tree_iterator_next */
529struct tree_node * 600struct tree_node *
530tree_iterator_next(struct tree_iterator *it) 601tree_iterator_next(struct tree_iterator *it)
531{ 602{
@@ -537,7 +608,9 @@ tree_iterator_next(struct tree_iterator *it)
537 608
538 return node; 609 return node;
539} 610}
611/* -->8-- */
540 612
613/* --8<-- tree_iterator_first */
541struct tree_node * 614struct tree_node *
542tree_iterator_first(struct tree_iterator *it, struct tree_node *tree) 615tree_iterator_first(struct tree_iterator *it, struct tree_node *tree)
543{ 616{
@@ -547,13 +620,17 @@ tree_iterator_first(struct tree_iterator *it, struct tree_node *tree)
547 620
548 return tree_iterator_next(it); 621 return tree_iterator_next(it);
549} 622}
623/* -->8-- */
550 624
625/* --8<-- tree_iterator_free */
551void 626void
552tree_iterator_free(struct tree_iterator *it) 627tree_iterator_free(struct tree_iterator *it)
553{ 628{
554 stack_free(&it->stack); 629 stack_free(&it->stack);
555} 630}
631/* -->8-- */
556 632
633/* --8<-- tree_preorder_iterator_next */
557struct tree_node * 634struct tree_node *
558tree_preorder_iterator_next(struct tree_iterator *it) 635tree_preorder_iterator_next(struct tree_iterator *it)
559{ 636{
@@ -570,7 +647,9 @@ tree_preorder_iterator_next(struct tree_iterator *it)
570 647
571 return node; 648 return node;
572} 649}
650/* -->8-- */
573 651
652/* --8<-- tree_preorder_iterator_first */
574struct tree_node * 653struct tree_node *
575tree_preorder_iterator_first(struct tree_iterator *it, struct tree_node *tree) 654tree_preorder_iterator_first(struct tree_iterator *it, struct tree_node *tree)
576{ 655{
@@ -585,6 +664,7 @@ tree_preorder_iterator_first(struct tree_iterator *it, struct tree_node *tree)
585 return NULL; 664 return NULL;
586 } 665 }
587} 666}
667/* -->8-- */
588 668
589/* ===== */ 669/* ===== */
590 670