Page 329 - Introduction to Microcontrollers Architecture, Programming, and Interfacing of The Motorola 68HC12

306 Chapter 10 Elementary Data Structures

Once the linked list is formed, the tree can be scanned to print the letters in order by
an algorithm pictured in Figure 10.10. The idea behind the algorithm is this. Starting at
the root, wrap a cord around the outside of the tree and print each node's letter (except 0),
as you pass under its crotch. Its crotch is the part between the branches to its successors
or, if it does not have successors, the crotch is the part between where the successors
would be connected, (Try this out on Figure 10.10.) Although a human being can
visualize this easily, a computer has a hard time working with pictures. This algorithm
can be implemented in a computer using the elegantly simple rule:
1. Process the tree at the left successor node. (13)
2. Print the letter.
3. Process the tree at the right successor node.
in processing the root node, you process the tree containing nodes c, a, b, and f first,
then print the letter t, then process the tree containing x and u last. Before you print the
letter t, you have to process the tree containing the nodes c, a, b, and f first, and that
processing will result in printing some letters first. In processing the tree containing c,
a, b, and f, you process the tree containing a and b, then print the letter c, then process
the tree containing f. Again, before you print the letter c, you have to process the tree
containing a and b first, and that will result in some printing. In processing the tree
containing a and b, you process the "null" tree for the left successor node of letter a (you
do nothing), then you print the letter a, then you process the tree containing b. In
processing the tree containing b, you process the "null" tree, you print the letter b, then
you process the "null" tree. After you print the letter c, you will process the tree
containing f and then process the tree containing x and u after printing the letter t. Try
this rale out on the tree, to see that it prints out the letters in alphabetical order.
The flowchart in Figure 10.11 shows the basic idea of the rule (13). The calling
sequence sets LINK to 0 to process list 0 first. If LINK is $FF, nothing is done;
otherwise, we process the left successor, print the letter, and process the right successor.
Processing the left successor requires the subroutine to call itself, and processing the
right successor requires the subroutine to call itself again so that this subroutine is
recursive, as discussed in Chapter 5. (To read the flowchart of Figure 10.11, RETURN
means to return to the place in the flowchart after the last execution of SCAN.)

Figure 10.10. Path for Scanning the Tree