[prev] [prev-tail] [tail] [up]

3.2.3 Traverse

To traverse a binary (search) tree, we can use the code in listing 8.


Listing 8:traverseBSTree
 
1void Tree_traverse(struct Tree *pTree, 
2  void (*pre)(struct Tree *pTree), 
3  void (*in)(struct Tree *pTree), 
4  void (*post)(struct Tree *pTree) 
5  ) 
6{ 
7  if (!Tree_isempty(pTree)) 
8  { 
9    if (pre) pre(pTree); 
10    Tree_traverse(Tree_getlefttree(pTree), pre, in, post); 
11    if (in) in(pTree); 
12    Tree_traverse(Tree_getrighttree(pTree), pre, in, post); 
13    if (post) post(pTree); 
14  } 
15}

This is a very general traversal subroutine. The parameters pre, in and post are pointers to subroutines that perform some kind of operation (such as printing) on a non-empty tree. Because Tree_traverse is already visiting all the nodes, the functions pointed to by pre, in and post typically only need to do something with the root node of the tree pointed to by pTree.

You may specify NULL for the pointers to functions if there is nothing to do before, in between or after the traversal of the subtrees of a tree.

If you want to visit the nodes in a sorted order based on the value of each node, you should define a function to process a (struct Tree) and pass it as the in parameter.

[prev] [prev-tail] [front] [up]