diff options
Diffstat (limited to 'tree.c')
| -rw-r--r-- | tree.c | 14 |
1 files changed, 9 insertions, 5 deletions
| @@ -45,7 +45,8 @@ tree_insert(struct tree_node *tree, T key) | |||
| 45 | if ( tree != NULL ) { | 45 | if ( tree != NULL ) { |
| 46 | tree->key = key; | 46 | tree->key = key; |
| 47 | tree->count = 1; | 47 | tree->count = 1; |
| 48 | tree->left = tree->right = NULL; | 48 | tree->left = NULL; |
| 49 | tree->right = NULL; | ||
| 49 | } | 50 | } |
| 50 | else | 51 | else |
| 51 | ERROR("out of memory"); | 52 | ERROR("out of memory"); |
| @@ -223,6 +224,12 @@ tree_count(struct tree_node *tree) | |||
| 223 | return 0; | 224 | return 0; |
| 224 | } | 225 | } |
| 225 | 226 | ||
| 227 | bool | ||
| 228 | tree_isleaf(struct tree_node *tree) | ||
| 229 | { | ||
| 230 | return tree->left == NULL && tree->right == NULL; | ||
| 231 | } | ||
| 232 | |||
| 226 | void | 233 | void |
| 227 | tree_apply_preorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) | 234 | tree_apply_preorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl) |
| 228 | { | 235 | { |
| @@ -461,9 +468,8 @@ tree_apply_postorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), | |||
| 461 | struct tree_node *next = stack_peek(&stack); | 468 | struct tree_node *next = stack_peek(&stack); |
| 462 | 469 | ||
| 463 | bool finishedSubtrees = (next->left == tree || next->right == tree); | 470 | bool finishedSubtrees = (next->left == tree || next->right == tree); |
| 464 | bool isLeaf = (next->left == NULL && next->right == NULL); | ||
| 465 | 471 | ||
| 466 | if ( finishedSubtrees || isLeaf ) { | 472 | if ( finishedSubtrees || tree_isleaf(next) ) { |
| 467 | stack_pop(&stack, &next); | 473 | stack_pop(&stack, &next); |
| 468 | 474 | ||
| 469 | visit(next->key, cl); | 475 | visit(next->key, cl); |
| @@ -637,13 +643,11 @@ main(void) | |||
| 637 | tree = tree_insert_it(tree, 15); | 643 | tree = tree_insert_it(tree, 15); |
| 638 | tree = tree_insert_it(tree, 18); | 644 | tree = tree_insert_it(tree, 18); |
| 639 | 645 | ||
| 640 | #if 0 | ||
| 641 | tree_apply_preorder(tree, print, NULL); | 646 | tree_apply_preorder(tree, print, NULL); |
| 642 | puts("postorder:"); | 647 | puts("postorder:"); |
| 643 | tree_apply_postorder(tree, print, NULL); | 648 | tree_apply_postorder(tree, print, NULL); |
| 644 | puts("postorder_it:"); | 649 | puts("postorder_it:"); |
| 645 | tree_apply_postorder_it(tree, print, NULL); | 650 | tree_apply_postorder_it(tree, print, NULL); |
| 646 | #endif | ||
| 647 | show_tree(tree, 0, 0); | 651 | show_tree(tree, 0, 0); |
| 648 | 652 | ||
| 649 | puts("levelorder_it:"); | 653 | puts("levelorder_it:"); |
