+ Add: Iterative Version von tree_insert().

+ Fix: Codelayout

1 files 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 <limits.h>
+#include <stdbool.h>
 #include <stdio.h>
 #include <stdlib.h>
-#include <stdbool.h>
 #include <time.h>
-#include <limits.h>
 
 #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);