From 4e3ae6fb8703853b21997e4cf60ecc6b141b048d Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Thu, 6 Aug 2020 09:10:55 +0200
Subject: add: levelorder-iteration für Trees
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 tree.c | 102 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 102 insertions(+)

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);
 
-- 
cgit v1.3