From 9daf9039c0356e68a3a7bb12f71901fa02d86860 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Wed, 5 Aug 2020 15:04:34 +0200 Subject: Neu: iterative Version für Postorder-Tree-Traversal MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- tree.c | 48 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 48 insertions(+) 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); -- cgit v1.3