1 files changed, 48 insertions, 0 deletions

diff --git a/tree.c b/tree.c
index 3c6a65c..b2819f0 100644
--- a/tree.c
+++ b/tree.c
@@ -299,6 +299,12 @@ stack_pop(struct stack *stack, struct tree_node **data)
                 return false;
 }
 
+static struct tree_node *
+stack_peek(struct stack *stack)
+{
+        return (stack->head != NULL) ? stack->head->data : NULL;
+}
+
 static bool
 stack_empty(struct stack *stack)
 {
@@ -363,6 +369,44 @@ tree_apply_inorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), vo
         }
 }
 
+// Hier eine Version für PostOrder-Iterativ:
+// Quelle: https://stackoverflow.com/a/16092333
+
+void
+tree_apply_postorder_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_empty(&stack) ) {
+                        struct tree_node *next = stack_peek(&stack);
+
+                        bool finishedSubtrees = (next->left == tree || next->right == tree);
+                        bool isLeaf           = (next->left == NULL && next->right == NULL);
+
+                        if ( finishedSubtrees || isLeaf ) {
+                                stack_pop(&stack, &next);
+
+                                visit(next->key, cl);
+
+                                tree = next;
+                        }
+                        else {
+                                if ( next->right != NULL ) {
+                                        stack_push(&stack, next->right);
+                                }
+                                if ( next->left != NULL ) {
+                                        stack_push(&stack, next->left);
+                                }
+                        }
+                }
+                stack_free(&stack);
+        }
+}
+
 /* ======================== */
 
 struct tree_iterator {
@@ -495,6 +539,10 @@ main(void)
         tree = tree_insert_it(tree, 18);
 
         tree_apply_preorder(tree, print, NULL);
+        puts("postorder:");
+        tree_apply_postorder(tree, print, NULL);
+        puts("postorder_it:");
+        tree_apply_postorder_it(tree, print, NULL);
 
         show_tree(tree, 0, 0);