From ac55496d881e0a17b3eff85f1faae5aafbc53b50 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Wed, 22 Jul 2020 17:30:45 +0200
Subject: erster Commit

---
 tree.c | 466 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 466 insertions(+)
 create mode 100644 tree.c

(limited to 'tree.c')

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;
+}
-- 
cgit v1.3