erster Commit

1 files changed, 466 insertions, 0 deletions

diff --git a/tree.c b/tree.c
new file mode 100644
index 0000000..7b0bc61
--- /dev/null
+++ b/tree.c
@@ -0,0 +1,466 @@
+// Binary Search Tree
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <time.h>
+#include <limits.h>
+
+#include "util.h"
+
+typedef int T;
+
+struct tree_node {
+        struct tree_node *left, *right;
+        T key;
+        int count;      /* collision counter */
+        /* ggf. weitere Felder... */
+};
+
+static bool tree_isBstUntil(struct tree_node *tree, int min, int max);
+
+bool
+tree_isBst(struct tree_node *tree)
+{
+        return tree_isBstUntil(tree, INT_MIN, INT_MAX);
+}
+
+bool
+tree_isBstUntil(struct tree_node *tree, int min, int 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);
+}
+
+struct tree_node *
+tree_insert(struct tree_node *tree, T key)
+{
+        if ( tree == NULL ) {
+                tree = malloc(sizeof *tree);
+                if ( tree != NULL ) {
+                        tree->key = key;
+                        tree->count = 1;
+                        tree->left = 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;
+}
+
+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 != NULL )
+                return tree_detach_min(&tree->left);
+        else {
+                *ptree = tree->right;
+                return tree;
+        }
+}
+
+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 */
+                /* TODO: 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;
+}
+
+void
+tree_clear(struct tree_node *tree)
+{
+        if ( tree ) {
+                tree_clear(tree->left);
+                tree_clear(tree->right);
+                free(tree);
+        }
+}
+
+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 */
+                        return tree;
+
+        return NULL;
+}
+
+struct tree_node *
+tree_minimum(struct tree_node *tree)
+{
+        if ( tree )
+                while ( tree->left )
+                        tree = tree->left;
+
+        return tree;
+}
+
+struct tree_node *
+tree_maximum(struct tree_node *tree)
+{
+        if ( tree )
+                while ( tree->right )
+                        tree = tree->right;
+
+        return tree;
+}
+
+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;
+}
+
+size_t
+tree_count(struct tree_node *tree)
+{
+        if ( tree )
+                return tree_count(tree->left) + tree_count(tree->right) + 1;
+
+        return 0;
+}
+
+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);
+        }
+}
+
+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);
+        }
+}
+
+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);
+        }
+}
+
+/* ===== */
+
+struct stack_item {
+        struct stack_item *next;
+        struct tree_node *data;
+};
+
+struct stack {
+        struct stack_item *head;
+};
+
+static void
+stack_init(struct stack *stack)
+{
+        stack->head = NULL;
+}
+
+static void
+stack_push(struct stack *stack, struct tree_node *data)
+{
+        struct stack_item *new_item;
+
+        if ( (new_item = malloc(sizeof(*new_item))) != NULL ) {
+                new_item->data = data;
+                new_item->next = stack->head;
+                stack->head = new_item;
+        }
+        else
+                ERROR("out of memory");
+}
+
+static bool
+stack_pop(struct stack *stack, struct tree_node **data)
+{
+        if ( stack->head != NULL ) {
+                struct stack_item *next = stack->head->next;
+                *data = stack->head->data;
+                free(stack->head);
+                stack->head = next;
+
+                return true;
+        }
+        else
+                return false;
+}
+
+static bool
+stack_empty(struct stack *stack)
+{
+        return stack->head == NULL;
+}
+
+void
+stack_free(struct stack *stack)
+{
+        struct stack_item *item, *next;
+
+        for ( item = stack->head; item; item = next ) {
+                next = item->next;
+                free(item);
+        }
+}
+
+void
+tree_apply_preorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
+{
+        if ( tree != NULL ) {
+                struct stack stack;
+
+                stack_init(&stack);
+
+                stack_push(&stack, tree);
+
+                while ( stack_pop(&stack, &tree) ) {
+                        visit(tree->key, cl);
+
+                        if ( tree->right != NULL ) stack_push(&stack, tree->right);
+                        if ( tree->left  != NULL ) stack_push(&stack, tree->left );
+                }
+
+                stack_free(&stack);
+        }
+}
+
+void
+tree_apply_inorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
+{
+        if ( tree != NULL ) {
+                struct stack stack;
+
+                stack_init(&stack);
+
+                while ( !stack_empty(&stack) || tree != NULL ) {
+                        if ( tree != NULL ) {
+                                stack_push(&stack, tree);
+                                tree = tree->left;
+                        }
+                        else {
+                                stack_pop(&stack, &tree);
+                                visit(tree->key, cl);
+                                tree = tree->right;
+                        }
+                }
+
+                stack_free(&stack);
+        }
+}
+
+/* ======================== */
+
+struct tree_iterator {
+        struct stack stack;
+};
+
+static void
+tree_iterator_push_leftmost(struct stack *stack, struct tree_node *node)
+{
+        for ( ; node; node = node->left ) {
+                stack_push(stack, node);
+        }
+}
+
+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;
+}
+
+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);
+}
+
+void
+tree_iterator_free(struct tree_iterator *it)
+{
+        stack_free(&it->stack);
+}
+
+/* ===== */
+
+
+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(tree, 10);
+        tree = tree_insert(tree, 5);
+        tree = tree_insert(tree, 20);
+        tree = tree_insert(tree, 1);
+        tree = tree_insert(tree, 7);
+        tree = tree_insert(tree, 15);
+        tree = tree_insert(tree, 18);
+
+        tree_apply_preorder(tree, print, NULL);
+
+        show_tree(tree, 0, 0);
+
+        struct tree_iterator it;
+        struct tree_node *node = tree_iterator_first(&it, tree);
+        while ( node ) {
+                fprintf(stdout, "%d\n", node->key);
+
+                node = tree_iterator_next(&it);
+        }
+        tree_iterator_free(&it);
+
+        tree_clear(tree);
+
+        return EXIT_SUCCESS;
+}