Page 111 - Programming Microcontrollers in C

96 Chapter 2 Advanced C Topics

and a new word is received. If the word is not the same and is less
than the root word, the node to the left is accessed and the compari­
son is repeated. This process is repeated until a match is found or a
node with no descendants is found. If a match is found, the count of
that node is incremented. If no match is found a new node is created
and placed at the bottom location, and the word is inserted into the
new node. This process is repeated with the smaller words always
going to the left and the larger words always going to the right.
Eventually a tree that contains all of the different words entered into
the program will have been created. The tree has several properties.
Since each node has two child nodes, the tree builds in a binary manner.
The root level has exactly one entry, the second level has two entries, the
third level has four entries, and so forth. If the tree is balanced, each level
will have a power of two entries. However, if word data are taken in
randomly, it is possible that some tree branches will terminate early and
others will extend to a depth or level that exceeds some.
Once the data are placed into the tree, it is possible to sort it or to
arrange the words in alphabetical order. If we traverse the tree from
the root node to the extreme left, we will find the word that is small­
est. Immediately above that word will be the next larger word. To the
right of the second word will be words larger than itself but smaller
than the word in the next node above. Therefore, the right path must
be traversed to the left to find the next larger words. All of this—
right and left, larger and smaller—sounds complicated. It is not.
Here is a case where a little thought and recursive code will help
things along easily. The code that follows is a complete function to
alphabetize and count the number of times that each word is used in
a document. Several new concepts will be shown in this program, so
it will be broken into short blocks and described in these small pieces
of code rather than trying to bite into the whole program at one time.
The structure tnode is listed below.

typedef struct tnode
{ /* the tree node */
char *word; /* points to text */
int count; /* occurrences */
struct tnode *left;/* pointer to left child */
struct tnode *right; /* pointer to right child*/
}Tnode;