From c42cc885f355ef986843cf74c474bfb793e3f0d8 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Wed, 5 Aug 2020 13:10:24 +0200 Subject: + Add: Iterative Version von tree_insert(). + Fix: Codelayout --- tree.c | 103 +++++++++++++++++++++++++++++++++++++++++++++++------------------ 1 file changed, 75 insertions(+), 28 deletions(-) diff --git a/tree.c b/tree.c index 7b0bc61..50f9548 100644 --- a/tree.c +++ b/tree.c @@ -1,9 +1,9 @@ // Binary Search Tree +#include +#include #include #include -#include #include -#include #include "util.h" @@ -11,9 +11,9 @@ typedef int T; struct tree_node { struct tree_node *left, *right; - T key; - int count; /* collision counter */ - /* ggf. weitere Felder... */ + T key; + int count; /* collision counter */ + /* ggf. weitere Felder... */ }; static bool tree_isBstUntil(struct tree_node *tree, int min, int max); @@ -34,7 +34,7 @@ tree_isBstUntil(struct tree_node *tree, int min, int max) return false; return tree_isBstUntil(tree->left, min, tree->key - 1) && - tree_isBstUntil(tree->right, tree->key + 1, max); + tree_isBstUntil(tree->right, tree->key + 1, max); } struct tree_node * @@ -43,7 +43,7 @@ tree_insert(struct tree_node *tree, T key) if ( tree == NULL ) { tree = malloc(sizeof *tree); if ( tree != NULL ) { - tree->key = key; + tree->key = key; tree->count = 1; tree->left = tree->right = NULL; } @@ -54,12 +54,59 @@ tree_insert(struct tree_node *tree, T 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 */ + else /* key == tree->key */ + tree->count++; /* handle collision */ return tree; } +struct tree_node * +tree_insert_it(struct tree_node *root, T key) +{ + struct tree_node *parent = NULL, + *curr = root; + + while ( curr != NULL ) { + parent = curr; + + if ( key < curr->key ) { + curr = curr->left; + } + else if ( key > curr->key ) { + curr = curr->right; + } + else { /* key == current->key */ + curr->count++; + return root; + } + } + + struct tree_node *new_node; + + new_node = malloc(sizeof *new_node); + if ( new_node != NULL ) { + new_node->key = key; + new_node->count = 1; + new_node->left = NULL; + new_node->right = NULL; + + if ( parent == NULL ) { + root = new_node; + } + else if ( key < parent->key ) { + parent->left = new_node; + } + else { + parent->right = new_node; + } + } + else { + ERROR("out of memory"); + } + + return root; +} + static struct tree_node * tree_detach_min(struct tree_node **ptree) { @@ -99,7 +146,7 @@ tree_remove(struct tree_node *tree, T key) else { struct tree_node *min = tree_detach_min(&tree->right); - min->left = tree->left; + min->left = tree->left; min->right = tree->right; tree = min; @@ -161,7 +208,7 @@ tree_height(struct tree_node *tree) size_t hl = tree_height(tree->left); size_t hr = tree_height(tree->right); - return (( hl > hr ) ? hl : hr) + 1; + return ((hl > hr) ? hl : hr) + 1; } return 0; @@ -210,7 +257,7 @@ tree_apply_postorder(struct tree_node *tree, void (*visit)(T key, void *cl), voi struct stack_item { struct stack_item *next; - struct tree_node *data; + struct tree_node * data; }; struct stack { @@ -231,7 +278,7 @@ stack_push(struct stack *stack, struct tree_node *data) if ( (new_item = malloc(sizeof(*new_item))) != NULL ) { new_item->data = data; new_item->next = stack->head; - stack->head = new_item; + stack->head = new_item; } else ERROR("out of memory"); @@ -242,7 +289,7 @@ stack_pop(struct stack *stack, struct tree_node **data) { if ( stack->head != NULL ) { struct stack_item *next = stack->head->next; - *data = stack->head->data; + *data = stack->head->data; free(stack->head); stack->head = next; @@ -282,8 +329,10 @@ tree_apply_preorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), v 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 ); + if ( tree->right != NULL ) + stack_push(&stack, tree->right); + if ( tree->left != NULL ) + stack_push(&stack, tree->left); } stack_free(&stack); @@ -358,7 +407,6 @@ tree_iterator_free(struct tree_iterator *it) /* ===== */ - void print(T data, void *cl) { @@ -372,7 +420,7 @@ int main_(void) { // Teste den Fall von mycodeschool - + struct tree_node *tree = NULL; tree = tree_insert(tree, 12); @@ -400,7 +448,7 @@ main_(void) show_tree(tree, 0, 0); tree_clear(tree); - + return EXIT_SUCCESS; } @@ -433,26 +481,25 @@ main__(void) 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 = 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); show_tree(tree, 0, 0); struct tree_iterator it; - struct tree_node *node = tree_iterator_first(&it, tree); + struct tree_node * node = tree_iterator_first(&it, tree); while ( node ) { fprintf(stdout, "%d\n", node->key); -- cgit v1.3