From dc71e5faf4752f5ceaedd5beae55cea40dbb007f Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sat, 8 Aug 2020 09:52:25 +0200 Subject: Implementiere einen "preorder"-Iterator --- tree.c | 36 ++++++++++++++++++++++++++++++++++-- 1 file changed, 34 insertions(+), 2 deletions(-) diff --git a/tree.c b/tree.c index b2515ca..9dc9cb9 100644 --- a/tree.c +++ b/tree.c @@ -554,6 +554,38 @@ tree_iterator_free(struct tree_iterator *it) stack_free(&it->stack); } +struct tree_node * +tree_preorder_iterator_next(struct tree_iterator *it) +{ + struct tree_node *node = NULL; + + if ( stack_pop(&it->stack, &node) ) { + if ( node->right != NULL ) { + stack_push(&it->stack, node->right); + } + if ( node->left != NULL ) { + stack_push(&it->stack, node->left); + } + } + + return node; +} + +struct tree_node * +tree_preorder_iterator_first(struct tree_iterator *it, struct tree_node *tree) +{ + stack_init(&it->stack); + + if ( tree ) { + stack_push(&it->stack, tree); + + return tree_preorder_iterator_next(it); + } + else { + return NULL; + } +} + /* ===== */ void @@ -656,11 +688,11 @@ main(void) show_tree(tree, 0, 0); struct tree_iterator it; - struct tree_node * node = tree_iterator_first(&it, tree); + struct tree_node * node = tree_preorder_iterator_first(&it, tree); while ( node ) { fprintf(stdout, "%d\n", node->key); - node = tree_iterator_next(&it); + node = tree_preorder_iterator_next(&it); } tree_iterator_free(&it); -- cgit v1.3