add: levelorder-iteration für Trees

1 files changed, 102 insertions, 0 deletions

diff --git a/tree.c b/tree.c
index 6238348..95702a2 100644
--- a/tree.c
+++ b/tree.c
@@ -325,6 +325,79 @@ stack_free(struct stack *stack)
         }
 }
 
+/* ===== */
+
+struct queue_item {
+        struct queue_item *next;
+        struct tree_node * data;
+};
+
+struct queue {
+        struct queue_item *head, *tail;
+};
+
+void
+queue_init(struct queue *queue)
+{
+        queue->head = NULL;
+}
+
+void
+queue_put(struct queue *queue, struct tree_node *data)
+{
+        struct queue_item *new_item;
+
+        if ( (new_item = malloc(sizeof(*new_item))) != NULL ) {
+                struct queue_item *tmp = queue->tail;
+                new_item->data         = data;
+                new_item->next         = NULL;
+                queue->tail            = new_item;
+                if ( queue->head == NULL )
+                        queue->head = queue->tail;
+                else
+                        tmp->next = queue->tail;
+        }
+        else
+                ERROR("out of memory");
+}
+
+bool
+queue_get(struct queue *queue, struct tree_node **data)
+{
+        if ( queue->head != NULL ) {
+                struct queue_item *next;
+
+                next  = queue->head->next;
+                *data = queue->head->data;
+
+                free(queue->head);
+                queue->head = next;
+
+                return true;
+        }
+        else
+                return false;
+}
+
+bool
+queue_empty(struct queue *queue)
+{
+        return queue->head == NULL;
+}
+
+void
+queue_free(struct queue *queue)
+{
+        struct queue_item *item, *next;
+
+        for ( item = queue->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)
 {
@@ -410,6 +483,29 @@ tree_apply_postorder_it(struct tree_node *tree, void (*visit)(T key, void *cl),
         }
 }
 
+void
+tree_apply_levelorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
+{
+        if ( tree != NULL ) {
+                struct queue queue;
+
+                queue_init(&queue);
+
+                queue_put(&queue, tree);
+
+                while ( queue_get(&queue, &tree) ) {
+                        visit(tree->key, cl);
+
+                        if ( tree->left != NULL )
+                                queue_put(&queue, tree->left);
+                        if ( tree->right != NULL )
+                                queue_put(&queue, tree->right);
+                }
+
+                queue_free(&queue);
+        }
+}
+
 /* ======================== */
 
 struct tree_iterator {
@@ -541,11 +637,17 @@ main(void)
         tree = tree_insert_it(tree, 15);
         tree = tree_insert_it(tree, 18);
 
+#if 0
         tree_apply_preorder(tree, print, NULL);
         puts("postorder:");
         tree_apply_postorder(tree, print, NULL);
         puts("postorder_it:");
         tree_apply_postorder_it(tree, print, NULL);
+#endif
+        show_tree(tree, 0, 0);
+
+        puts("levelorder_it:");
+        tree_apply_levelorder_it(tree, print, NULL);
 
         show_tree(tree, 0, 0);