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;
+}

diff --git a/tree.c b/tree.c new file mode 100644 index 0000000..7b0bc61 --- /dev/null +++ b/tree.c
@@ -0,0 +1,466 @@
	1	// Binary Search Tree
	2	#include <stdio.h>
	3	#include <stdlib.h>
	4	#include <stdbool.h>
	5	#include <time.h>
	6	#include <limits.h>
	7
	8	#include "util.h"
	9
	10	typedef int T;
	11
	12	struct tree_node {
	13	struct tree_node left, right;
	14	T key;
	15	int count; /* collision counter */
	16	/* ggf. weitere Felder... */
	17	};
	18
	19	static bool tree_isBstUntil(struct tree_node *tree, int min, int max);
	20
	21	bool
	22	tree_isBst(struct tree_node *tree)
	23	{
	24	return tree_isBstUntil(tree, INT_MIN, INT_MAX);
	25	}
	26
	27	bool
	28	tree_isBstUntil(struct tree_node *tree, int min, int max)
	29	{
	30	if ( tree == NULL )
	31	return true;
	32
	33	if ( tree->key < min \|\| tree->key > max )
	34	return false;
	35
	36	return tree_isBstUntil(tree->left, min, tree->key - 1) &&
	37	tree_isBstUntil(tree->right, tree->key + 1, max);
	38	}
	39
	40	struct tree_node *
	41	tree_insert(struct tree_node *tree, T key)
	42	{
	43	if ( tree == NULL ) {
	44	tree = malloc(sizeof *tree);
	45	if ( tree != NULL ) {
	46	tree->key = key;
	47	tree->count = 1;
	48	tree->left = tree->right = NULL;
	49	}
	50	else
	51	ERROR("out of memory");
	52	}
	53	else if ( key < tree->key )
	54	tree->left = tree_insert(tree->left, key);
	55	else if ( key > tree->key )
	56	tree->right = tree_insert(tree->right, key);
	57	else /* key == tree->key */
	58	tree->count++; /* handle collision */
	59
	60	return tree;
	61	}
	62
	63	static struct tree_node *
	64	tree_detach_min(struct tree_node **ptree)
	65	{
	66	struct tree_node tree = ptree;
	67
	68	if ( tree == NULL )
	69	return NULL;
	70	else if ( tree->left != NULL )
	71	return tree_detach_min(&tree->left);
	72	else {
	73	*ptree = tree->right;
	74	return tree;
	75	}
	76	}
	77
	78	struct tree_node *
	79	tree_remove(struct tree_node *tree, T key)
	80	{
	81	if ( tree == NULL )
	82	return NULL;
	83
	84	if ( key < tree->key )
	85	tree->left = tree_remove(tree->left, key);
	86	else if ( key > tree->key )
	87	tree->right = tree_remove(tree->right, key);
	88	else { /* key == tree->key */
	89	/* TODO: Handle Collision */
	90
	91	struct tree_node *temp = tree;
	92
	93	if ( tree->left == NULL ) {
	94	tree = tree->right;
	95	}
	96	else if ( tree->right == NULL ) {
	97	tree = tree->left;
	98	}
	99	else {
	100	struct tree_node *min = tree_detach_min(&tree->right);
	101
	102	min->left = tree->left;
	103	min->right = tree->right;
	104
	105	tree = min;
	106	}
	107
	108	free(temp);
	109	}
	110	return tree;
	111	}
	112
	113	void
	114	tree_clear(struct tree_node *tree)
	115	{
	116	if ( tree ) {
	117	tree_clear(tree->left);
	118	tree_clear(tree->right);
	119	free(tree);
	120	}
	121	}
	122
	123	struct tree_node *
	124	tree_lookup(struct tree_node *tree, T key)
	125	{
	126	while ( tree )
	127	if ( key < tree->key )
	128	tree = tree->left;
	129	else if ( key > tree->key )
	130	tree = tree->right;
	131	else /* key == tree->key */
	132	return tree;
	133
	134	return NULL;
	135	}
	136
	137	struct tree_node *
	138	tree_minimum(struct tree_node *tree)
	139	{
	140	if ( tree )
	141	while ( tree->left )
	142	tree = tree->left;
	143
	144	return tree;
	145	}
	146
	147	struct tree_node *
	148	tree_maximum(struct tree_node *tree)
	149	{
	150	if ( tree )
	151	while ( tree->right )
	152	tree = tree->right;
	153
	154	return tree;
	155	}
	156
	157	size_t
	158	tree_height(struct tree_node *tree)
	159	{
	160	if ( tree ) {
	161	size_t hl = tree_height(tree->left);
	162	size_t hr = tree_height(tree->right);
	163
	164	return (( hl > hr ) ? hl : hr) + 1;
	165	}
	166
	167	return 0;
	168	}
	169
	170	size_t
	171	tree_count(struct tree_node *tree)
	172	{
	173	if ( tree )
	174	return tree_count(tree->left) + tree_count(tree->right) + 1;
	175
	176	return 0;
	177	}
	178
	179	void
	180	tree_apply_preorder(struct tree_node tree, void (visit)(T key, void cl), void cl)
	181	{
	182	if ( tree ) {
	183	visit(tree->key, cl);
	184	tree_apply_preorder(tree->left, visit, cl);
	185	tree_apply_preorder(tree->right, visit, cl);
	186	}
	187	}
	188
	189	void
	190	tree_apply_inorder(struct tree_node tree, void (visit)(T key, void cl), void cl)
	191	{
	192	if ( tree ) {
	193	tree_apply_inorder(tree->left, visit, cl);
	194	visit(tree->key, cl);
	195	tree_apply_inorder(tree->right, visit, cl);
	196	}
	197	}
	198
	199	void
	200	tree_apply_postorder(struct tree_node tree, void (visit)(T key, void cl), void cl)
	201	{
	202	if ( tree ) {
	203	tree_apply_postorder(tree->left, visit, cl);
	204	tree_apply_postorder(tree->right, visit, cl);
	205	visit(tree->key, cl);
	206	}
	207	}
	208
	209	/* ===== */
	210
	211	struct stack_item {
	212	struct stack_item *next;
	213	struct tree_node *data;
	214	};
	215
	216	struct stack {
	217	struct stack_item *head;
	218	};
	219
	220	static void
	221	stack_init(struct stack *stack)
	222	{
	223	stack->head = NULL;
	224	}
	225
	226	static void
	227	stack_push(struct stack stack, struct tree_node data)
	228	{
	229	struct stack_item *new_item;
	230
	231	if ( (new_item = malloc(sizeof(*new_item))) != NULL ) {
	232	new_item->data = data;
	233	new_item->next = stack->head;
	234	stack->head = new_item;
	235	}
	236	else
	237	ERROR("out of memory");
	238	}
	239
	240	static bool
	241	stack_pop(struct stack stack, struct tree_node *data)
	242	{
	243	if ( stack->head != NULL ) {
	244	struct stack_item *next = stack->head->next;
	245	*data = stack->head->data;
	246	free(stack->head);
	247	stack->head = next;
	248
	249	return true;
	250	}
	251	else
	252	return false;
	253	}
	254
	255	static bool
	256	stack_empty(struct stack *stack)
	257	{
	258	return stack->head == NULL;
	259	}
	260
	261	void
	262	stack_free(struct stack *stack)
	263	{
	264	struct stack_item item, next;
	265
	266	for ( item = stack->head; item; item = next ) {
	267	next = item->next;
	268	free(item);
	269	}
	270	}
	271
	272	void
	273	tree_apply_preorder_it(struct tree_node tree, void (visit)(T key, void cl), void cl)
	274	{
	275	if ( tree != NULL ) {
	276	struct stack stack;
	277
	278	stack_init(&stack);
	279
	280	stack_push(&stack, tree);
	281
	282	while ( stack_pop(&stack, &tree) ) {
	283	visit(tree->key, cl);
	284
	285	if ( tree->right != NULL ) stack_push(&stack, tree->right);
	286	if ( tree->left != NULL ) stack_push(&stack, tree->left );
	287	}
	288
	289	stack_free(&stack);
	290	}
	291	}
	292
	293	void
	294	tree_apply_inorder_it(struct tree_node tree, void (visit)(T key, void cl), void cl)
	295	{
	296	if ( tree != NULL ) {
	297	struct stack stack;
	298
	299	stack_init(&stack);
	300
	301	while ( !stack_empty(&stack) \|\| tree != NULL ) {
	302	if ( tree != NULL ) {
	303	stack_push(&stack, tree);
	304	tree = tree->left;
	305	}
	306	else {
	307	stack_pop(&stack, &tree);
	308	visit(tree->key, cl);
	309	tree = tree->right;
	310	}
	311	}
	312
	313	stack_free(&stack);
	314	}
	315	}
	316
	317	/* ======================== */
	318
	319	struct tree_iterator {
	320	struct stack stack;
	321	};
	322
	323	static void
	324	tree_iterator_push_leftmost(struct stack stack, struct tree_node node)
	325	{
	326	for ( ; node; node = node->left ) {
	327	stack_push(stack, node);
	328	}
	329	}
	330
	331	struct tree_node *
	332	tree_iterator_next(struct tree_iterator *it)
	333	{
	334	struct tree_node *node = NULL;
	335
	336	if ( stack_pop(&it->stack, &node) ) {
	337	tree_iterator_push_leftmost(&it->stack, node->right);
	338	}
	339
	340	return node;
	341	}
	342
	343	struct tree_node *
	344	tree_iterator_first(struct tree_iterator it, struct tree_node tree)
	345	{
	346	stack_init(&it->stack);
	347
	348	tree_iterator_push_leftmost(&it->stack, tree);
	349
	350	return tree_iterator_next(it);
	351	}
	352
	353	void
	354	tree_iterator_free(struct tree_iterator *it)
	355	{
	356	stack_free(&it->stack);
	357	}
	358
	359	/* ===== */
	360
	361
	362	void
	363	print(T data, void *cl)
	364	{
	365	(void) cl;
	366	printf("%d\n", data);
	367	}
	368
	369	#include "treeutil.h"
	370
	371	int
	372	main_(void)
	373	{
	374	// Teste den Fall von mycodeschool
	375
	376	struct tree_node *tree = NULL;
	377
	378	tree = tree_insert(tree, 12);
	379	tree = tree_insert(tree, 5);
	380	tree = tree_insert(tree, 15);
	381	tree = tree_insert(tree, 3);
	382	tree = tree_insert(tree, 7);
	383	tree = tree_insert(tree, 13);
	384	tree = tree_insert(tree, 17);
	385	tree = tree_insert(tree, 1);
	386	tree = tree_insert(tree, 9);
	387	tree = tree_insert(tree, 14);
	388	tree = tree_insert(tree, 20);
	389	tree = tree_insert(tree, 8);
	390	tree = tree_insert(tree, 11);
	391	tree = tree_insert(tree, 18);
	392
	393	tree = tree_remove(tree, 15);
	394
	395	if ( !tree_isBst(tree) ) {
	396	fprintf(stderr, "Tree ist kein BST!!\n");
	397	return EXIT_FAILURE;
	398	}
	399
	400	show_tree(tree, 0, 0);
	401
	402	tree_clear(tree);
	403
	404	return EXIT_SUCCESS;
	405	}
	406
	407	int
	408	main__(void)
	409	{
	410	struct tree_node *tree = NULL;
	411
	412	tree = tree_insert(tree, 5);
	413	tree = tree_insert(tree, 3);
	414	tree = tree_insert(tree, 7);
	415	tree = tree_insert(tree, 2);
	416	tree = tree_insert(tree, 4);
	417	tree = tree_insert(tree, 6);
	418	tree = tree_insert(tree, 8);
	419
	420	tree = tree_remove(tree, 2);
	421	tree = tree_remove(tree, 3);
	422	tree = tree_remove(tree, 5);
	423
	424	if ( !tree_isBst(tree) ) {
	425	fprintf(stderr, "Tree ist kein BST!!\n");
	426	return EXIT_FAILURE;
	427	}
	428
	429	show_tree(tree, 0, 0);
	430
	431	tree_clear(tree);
	432
	433	return EXIT_SUCCESS;
	434	}
	435
	436
	437	int
	438	main(void)
	439	{
	440	struct tree_node *tree = NULL;
	441
	442	tree = tree_insert(tree, 10);
	443	tree = tree_insert(tree, 5);
	444	tree = tree_insert(tree, 20);
	445	tree = tree_insert(tree, 1);
	446	tree = tree_insert(tree, 7);
	447	tree = tree_insert(tree, 15);
	448	tree = tree_insert(tree, 18);
	449
	450	tree_apply_preorder(tree, print, NULL);
	451
	452	show_tree(tree, 0, 0);
	453
	454	struct tree_iterator it;
	455	struct tree_node *node = tree_iterator_first(&it, tree);
	456	while ( node ) {
	457	fprintf(stdout, "%d\n", node->key);
	458
	459	node = tree_iterator_next(&it);
	460	}
	461	tree_iterator_free(&it);
	462
	463	tree_clear(tree);
	464
	465	return EXIT_SUCCESS;
	466	}