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

10.4 Linked List Structures 305

We first describe the tree using the algorithm to generate its graph. The first letter
in the string is put at the root of the tree (see Figure 10.8), while the second letter is
pu.t at the left or right successor node of the root, depending on whether it is
alphabetically before or after the letter at the root. Successive letters begin at the root
node, going left or right to successor nodes in the same way as the second letter until an
empty node is found. The new letter is placed at this empty node. We recommend that
you work through the characters in the string (12) above, and build up the tree shown in
Figure 10.8 using the foregoing rule.
As you have just seen, it is fairly easy to generate the graph of the tree. We now
describe how to store the tree in memory using a linked list structure. After each letter
in the string, append two integers where the first is the string index of the letter for the
left successor and the second is the string index of the letter for the right successor,
(String indexes, as usual, begin at 0, so that 0 is the string index for t, 1 is the string
index for c, and so on.) The symbol NS, which is $FF, indicates no successor of that
type. (See Figure 10.9 for the linked list representation of the tree. The symbolic
contents of each byte is shown rather than the usual hexadecimal contents.) This linked
list structure contains identically structured lists, such as the first three bytes, t,!,2. The
list index of each list is identical to the string index of the letter in the list so that the
list t,l ,2 is the Oth list in the linked list. Each list has three elements, a letter and two
links. Although the elements of each list are the same precision in this example (each is
one byte), the precisions are generally different, from one bit to hundreds of bits per
element. The links in this example are equal to the indexes of the lists that contain the
left and right successors. For the top, which is the Oth element and represents the root of
the tree, the left successor of the root is the letter c, and the element that contains the
letter c has index 1, so that the first link out of the Oth element is 1. The root's right
successor is the letter x, and the element that contains x has index 2, so the second link
of the Oth element is 2. You should verify that the other elements, which are identical in
form to the Oth element, have the same relationship to the tree that the Oth element has.

Figure 10.9. Linked List Representation of the Tree Shown in Figure 10.8