From 154874afda4a8df885e51c01f7681f04fb0b8e61 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sat, 9 Apr 2022 09:43:53 +0200 Subject: neue Verzeichnisstruktur --- src/tree.c | 806 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 806 insertions(+) create mode 100644 src/tree.c (limited to 'src/tree.c') diff --git a/src/tree.c b/src/tree.c new file mode 100644 index 0000000..93690e2 --- /dev/null +++ b/src/tree.c @@ -0,0 +1,806 @@ +// Binary Search Tree +#include +#include +#include +#include +#include + +#include "util.h" + +/* --8<-- tree_type */ +typedef int T; + +struct tree_node { + struct tree_node *left, *right; + T key; + int count; /* collision counter */ + /* ggf. weitere Felder... */ +}; +/* -->8-- */ + +/* --8<-- tree_isBst */ +static bool +tree_isBstUntil(struct tree_node *tree, T min, T max) +{ + if ( tree == NULL ) + return true; + + if ( tree->key < min || tree->key > max ) + return false; + + return tree_isBstUntil(tree->left, min, tree->key - 1) && + tree_isBstUntil(tree->right, tree->key + 1, max); +} + +bool +tree_isBst(struct tree_node *tree) +{ + return tree_isBstUntil(tree, INT_MIN, INT_MAX); +} +/* -->8-- */ + +/* --8<-- tree_insert */ +struct tree_node * +tree_insert(struct tree_node *tree, T key) +{ + if ( tree == NULL ) { + tree = malloc(sizeof *tree); + if ( tree ) { + tree->key = key; + tree->count = 1; + tree->left = NULL; + tree->right = NULL; + } + else + ERROR("out of memory"); + } + else if ( key < tree->key ) + tree->left = tree_insert(tree->left, key); + else if ( key > tree->key ) + tree->right = tree_insert(tree->right, key); + else /* key == tree->key */ + tree->count++; /* handle collision */ + + return tree; +} +/* -->8-- */ + +/* --8<-- tree_insert_it */ +struct tree_node * +tree_insert_it(struct tree_node *tree, T key) +{ + struct tree_node *parent = NULL; + + for ( struct tree_node *curr = tree; curr; ) { + parent = curr; + + if ( key < curr->key ) { + curr = curr->left; + } + else if ( key > curr->key ) { + curr = curr->right; + } + else { /* key == current->key */ + curr->count++; + return tree; + } + } + + struct tree_node *new_node; + + new_node = malloc(sizeof *new_node); + if ( new_node ) { + new_node->key = key; + new_node->count = 1; + new_node->left = NULL; + new_node->right = NULL; + + if ( parent == NULL ) { + tree = new_node; + } + else if ( key < parent->key ) { + parent->left = new_node; + } + else { + parent->right = new_node; + } + } + else { + ERROR("out of memory"); + } + + return tree; +} +/* -->8-- */ + +/* --8<-- tree_detach_min */ +static struct tree_node * +tree_detach_min(struct tree_node **ptree) +{ + struct tree_node *tree = *ptree; + + if ( tree == NULL ) + return NULL; + else if ( tree->left ) + return tree_detach_min(&tree->left); + else { + *ptree = tree->right; + return tree; + } +} +/* -->8-- */ + +/* --8<-- tree_remove */ +struct tree_node * +tree_remove(struct tree_node *tree, T key) +{ + if ( tree == NULL ) + return NULL; + + if ( key < tree->key ) + tree->left = tree_remove(tree->left, key); + else if ( key > tree->key ) + tree->right = tree_remove(tree->right, key); + else { /* key == tree->key */ + if ( --tree->count == 0 ) { /* Handle Collision */ + struct tree_node *temp = tree; + + if ( tree->left == NULL ) { + tree = tree->right; + } + else if ( tree->right == NULL ) { + tree = tree->left; + } + else { + struct tree_node *min = tree_detach_min(&tree->right); + + min->left = tree->left; + min->right = tree->right; + + tree = min; + } + + free(temp); + } + } + return tree; +} +/* -->8-- */ + +/* --8<-- tree_clear */ +void +tree_clear(struct tree_node *tree) +{ + if ( tree ) { + tree_clear(tree->left); + tree_clear(tree->right); + free(tree); + } +} +/* -->8-- */ + +/* --8<-- tree_lookup */ +struct tree_node * +tree_lookup(struct tree_node *tree, T key) +{ + while ( tree ) + if ( key < tree->key ) + tree = tree->left; + else if ( key > tree->key ) + tree = tree->right; + else /* key == tree->key */ + break; + + return tree; +} +/* -->8-- */ + +/* --8<-- tree_minimum */ +struct tree_node * +tree_minimum(struct tree_node *tree) +{ + if ( tree ) + while ( tree->left ) + tree = tree->left; + + return tree; +} +/* -->8-- */ + +/* --8<-- tree_maximum */ +struct tree_node * +tree_maximum(struct tree_node *tree) +{ + if ( tree ) + while ( tree->right ) + tree = tree->right; + + return tree; +} +/* -->8-- */ + +/* --8<-- tree_height */ +size_t +tree_height(struct tree_node *tree) +{ + if ( tree ) { + size_t hl = tree_height(tree->left); + size_t hr = tree_height(tree->right); + + return ((hl > hr) ? hl : hr) + 1; + } + + return 0; +} +/* -->8-- */ + +/* --8<-- tree_count */ +size_t +tree_count(struct tree_node *tree) +{ + if ( tree ) + return tree_count(tree->left) + tree_count(tree->right) + 1; + + return 0; +} +/* -->8-- */ + +/* --8<-- tree_copy */ +struct tree_node * +tree_copy(struct tree_node *tree) +{ + if ( tree ) { + struct tree_node *new_node; + + new_node = malloc(sizeof *new_node); + if ( new_node ) { + new_node->key = tree->key; + new_node->count = tree->count; + new_node->left = tree_copy(tree->left); + new_node->right = tree_copy(tree->right); + } + else { + ERROR("out of memory"); + } + + return new_node; + } + return NULL; +} +/* -->8-- */ + +/* --8<-- tree_isleaf */ +bool +tree_isleaf(struct tree_node *tree) +{ + return tree->left == NULL && tree->right == NULL; +} +/* -->8-- */ + +/* --8<-- tree_apply_preorder */ +void +tree_apply_preorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) +{ + if ( tree ) { + visit(tree->key, cl); + tree_apply_preorder(tree->left, visit, cl); + tree_apply_preorder(tree->right, visit, cl); + } +} +/* -->8-- */ + +/* --8<-- tree_apply_inorder */ +void +tree_apply_inorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) +{ + if ( tree ) { + tree_apply_inorder(tree->left, visit, cl); + visit(tree->key, cl); + tree_apply_inorder(tree->right, visit, cl); + } +} +/* -->8-- */ + +/* --8<-- tree_apply_postorder */ +void +tree_apply_postorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) +{ + if ( tree ) { + tree_apply_postorder(tree->left, visit, cl); + tree_apply_postorder(tree->right, visit, cl); + visit(tree->key, cl); + } +} +/* -->8-- */ + +/* ===== */ + +/* --8<-- tree_stack_type */ +struct stack_item { + struct stack_item *next; + struct tree_node * data; +}; + +struct stack { + struct stack_item *head; +}; +/* -->8-- */ + +/* --8<-- tree_stack_init */ +static void +stack_init(struct stack *stack) +{ + stack->head = NULL; +} +/* -->8-- */ + +/* --8<-- tree_stack_push */ +static void +stack_push(struct stack *stack, struct tree_node *data) +{ + struct stack_item *new_item; + + if ( (new_item = malloc(sizeof *new_item)) ) { + new_item->data = data; + new_item->next = stack->head; + stack->head = new_item; + } + else + ERROR("out of memory"); +} +/* -->8-- */ + +/* --8<-- tree_stack_pop */ +static bool +stack_pop(struct stack *stack, struct tree_node **data) +{ + if ( stack->head ) { + struct stack_item *next; + + next = stack->head->next; + *data = stack->head->data; + + free(stack->head); + stack->head = next; + + return true; + } + else + return false; +} +/* -->8-- */ + +/* --8<-- tree_stack_peek */ +static struct tree_node * +stack_peek(struct stack *stack) +{ + return (stack->head) ? stack->head->data : NULL; +} +/* -->8-- */ + +/* --8<-- tree_stack_empty */ +static bool +stack_empty(struct stack *stack) +{ + return stack->head == NULL; +} +/* -->8-- */ + +/* --8<-- tree_stack_free */ +void +stack_free(struct stack *stack) +{ + struct stack_item *item, *next; + + for ( item = stack->head; item; item = next ) { + next = item->next; + free(item); + } +} +/* -->8-- */ + +/* ===== */ + +/* --8<-- tree_queue_type */ +struct queue_item { + struct queue_item *next; + struct tree_node * data; +}; + +struct queue { + struct queue_item *head, *tail; +}; +/* -->8-- */ + +/* --8<-- tree_queue_init */ +void +queue_init(struct queue *queue) +{ + queue->head = NULL; +} +/* -->8-- */ + +/* --8<-- tree_queue_put */ +void +queue_put(struct queue *queue, struct tree_node *data) +{ + struct queue_item *new_item; + + if ( (new_item = malloc(sizeof *new_item)) ) { + struct queue_item *tail; + + tail = queue->tail; + new_item->data = data; + new_item->next = NULL; + queue->tail = new_item; + + if ( queue->head == NULL ) + queue->head = queue->tail; + else + tail->next = queue->tail; + } + else + ERROR("out of memory"); +} +/* -->8-- */ + +/* --8<-- tree_queue_get */ +bool +queue_get(struct queue *queue, struct tree_node **data) +{ + if ( queue->head ) { + struct queue_item *next; + + next = queue->head->next; + *data = queue->head->data; + + free(queue->head); + queue->head = next; + + return true; + } + else + return false; +} +/* -->8-- */ + +/* --8<-- tree_queue_empty */ +bool +queue_empty(struct queue *queue) +{ + return queue->head == NULL; +} +/* -->8-- */ + +/* --8<-- tree_queue_free */ +void +queue_free(struct queue *queue) +{ + struct queue_item *item, *next; + + for ( item = queue->head; item; item = next ) { + next = item->next; + free(item); + } +} +/* -->8-- */ + +/* ===== */ + +/* --8<-- tree_apply_preorder_it */ +void +tree_apply_preorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) +{ + if ( tree ) { + struct stack stack; + + stack_init(&stack); + + stack_push(&stack, tree); + + while ( stack_pop(&stack, &tree) ) { + visit(tree->key, cl); + + if ( tree->right ) + stack_push(&stack, tree->right); + if ( tree->left ) + stack_push(&stack, tree->left); + } + + stack_free(&stack); + } +} +/* -->8-- */ + +/* --8<-- tree_apply_inorder_it */ +void +tree_apply_inorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) +{ + if ( tree ) { + struct stack stack; + + stack_init(&stack); + + while ( !stack_empty(&stack) || tree ) { + if ( tree ) { + stack_push(&stack, tree); + tree = tree->left; + } + else { + stack_pop(&stack, &tree); + visit(tree->key, cl); + tree = tree->right; + } + } + + stack_free(&stack); + } +} +/* -->8-- */ + +// Hier eine Version für PostOrder-Iterativ: +// Quelle: https://stackoverflow.com/a/16092333 + +/* --8<-- tree_apply_postorder_it */ +void +tree_apply_postorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) +{ + if ( tree ) { + struct stack stack; + + stack_init(&stack); + stack_push(&stack, tree); + + while ( !stack_empty(&stack) ) { + struct tree_node *next = stack_peek(&stack); + + bool finishedSubtrees = (next->left == tree || next->right == tree); + + if ( finishedSubtrees || tree_isleaf(next) ) { + stack_pop(&stack, &next); + + visit(next->key, cl); + + tree = next; + } + else { + if ( next->right ) { + stack_push(&stack, next->right); + } + if ( next->left ) { + stack_push(&stack, next->left); + } + } + } + stack_free(&stack); + } +} +/* -->8-- */ + +/* --8<-- tree_apply_levelorder_it */ +void +tree_apply_levelorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) +{ + if ( tree ) { + struct queue queue; + + queue_init(&queue); + + queue_put(&queue, tree); + + while ( queue_get(&queue, &tree) ) { + visit(tree->key, cl); + + if ( tree->left ) + queue_put(&queue, tree->left); + if ( tree->right ) + queue_put(&queue, tree->right); + } + + queue_free(&queue); + } +} +/* -->8-- */ + +/* ======================== */ + +/* --8<-- tree_iterator_type */ +struct tree_iterator { + struct stack stack; +}; +/* -->8-- */ + +/* --8<-- tree_iterator_push_leftmost */ +static void +tree_iterator_push_leftmost(struct stack *stack, struct tree_node *node) +{ + for ( ; node; node = node->left ) { + stack_push(stack, node); + } +} +/* -->8-- */ + +/* --8<-- tree_iterator_next */ +struct tree_node * +tree_iterator_next(struct tree_iterator *it) +{ + struct tree_node *node = NULL; + + if ( stack_pop(&it->stack, &node) ) { + tree_iterator_push_leftmost(&it->stack, node->right); + } + + return node; +} +/* -->8-- */ + +/* --8<-- tree_iterator_first */ +struct tree_node * +tree_iterator_first(struct tree_iterator *it, struct tree_node *tree) +{ + stack_init(&it->stack); + + tree_iterator_push_leftmost(&it->stack, tree); + + return tree_iterator_next(it); +} +/* -->8-- */ + +/* --8<-- tree_iterator_free */ +void +tree_iterator_free(struct tree_iterator *it) +{ + stack_free(&it->stack); +} +/* -->8-- */ + +/* --8<-- tree_preorder_iterator_next */ +struct tree_node * +tree_preorder_iterator_next(struct tree_iterator *it) +{ + struct tree_node *node = NULL; + + if ( stack_pop(&it->stack, &node) ) { + if ( node->right ) { + stack_push(&it->stack, node->right); + } + if ( node->left ) { + stack_push(&it->stack, node->left); + } + } + + return node; +} +/* -->8-- */ + +/* --8<-- tree_preorder_iterator_first */ +struct tree_node * +tree_preorder_iterator_first(struct tree_iterator *it, struct tree_node *tree) +{ + stack_init(&it->stack); + + if ( tree ) { + stack_push(&it->stack, tree); + + return tree_preorder_iterator_next(it); + } + else { + return NULL; + } +} +/* -->8-- */ + +/* ===== */ + +void +print(T data, void *cl) +{ + (void) cl; + printf("%d\n", data); +} + +#include "treeutil.h" + +int +main_(void) +{ + // Teste den Fall von mycodeschool + + struct tree_node *tree = NULL; + + tree = tree_insert(tree, 12); + tree = tree_insert(tree, 5); + tree = tree_insert(tree, 15); + tree = tree_insert(tree, 3); + tree = tree_insert(tree, 7); + tree = tree_insert(tree, 13); + tree = tree_insert(tree, 17); + tree = tree_insert(tree, 1); + tree = tree_insert(tree, 9); + tree = tree_insert(tree, 14); + tree = tree_insert(tree, 20); + tree = tree_insert(tree, 8); + tree = tree_insert(tree, 11); + tree = tree_insert(tree, 18); + + tree = tree_remove(tree, 15); + + if ( !tree_isBst(tree) ) { + fprintf(stderr, "Tree ist kein BST!!\n"); + return EXIT_FAILURE; + } + + show_tree(tree, 0, 0); + + tree_clear(tree); + + return EXIT_SUCCESS; +} + +int +main__(void) +{ + struct tree_node *tree = NULL; + + tree = tree_insert(tree, 5); + tree = tree_insert(tree, 3); + tree = tree_insert(tree, 7); + tree = tree_insert(tree, 2); + tree = tree_insert(tree, 4); + tree = tree_insert(tree, 6); + tree = tree_insert(tree, 8); + + tree = tree_remove(tree, 2); + tree = tree_remove(tree, 3); + tree = tree_remove(tree, 5); + + if ( !tree_isBst(tree) ) { + fprintf(stderr, "Tree ist kein BST!!\n"); + return EXIT_FAILURE; + } + + show_tree(tree, 0, 0); + + tree_clear(tree); + + return EXIT_SUCCESS; +} + +int +main(void) +{ + struct tree_node *tree = NULL; + + tree = tree_insert_it(tree, 10); + tree = tree_insert_it(tree, 5); + tree = tree_insert_it(tree, 20); + tree = tree_insert_it(tree, 1); + tree = tree_insert_it(tree, 7); + tree = tree_insert_it(tree, 15); + tree = tree_insert_it(tree, 18); + + tree_apply_preorder(tree, print, NULL); + puts("postorder:"); + tree_apply_postorder(tree, print, NULL); + puts("postorder_it:"); + tree_apply_postorder_it(tree, print, NULL); + show_tree(tree, 0, 0); + + puts("levelorder_it:"); + tree_apply_levelorder_it(tree, print, NULL); + + show_tree(tree, 0, 0); + + struct tree_iterator it; + struct tree_node * node = tree_preorder_iterator_first(&it, tree); + while ( node ) { + fprintf(stdout, "%d\n", node->key); + + node = tree_preorder_iterator_next(&it); + } + tree_iterator_free(&it); + + tree_clear(tree); + + return EXIT_SUCCESS; +} -- cgit v1.3