From 7221289477ba80bfbb9c2c37e43a9d6b1d0e6d17 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Sun, 10 Apr 2022 09:01:17 +0200
Subject: feat: rename files

---
 src/tree.c | 806 -------------------------------------------------------------
 1 file changed, 806 deletions(-)
 delete mode 100644 src/tree.c

(limited to 'src/tree.c')

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 @@
-// Binary Search Tree
-#include <limits.h>
-#include <stdbool.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <time.h>
-
-#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