Rex Jaeschke is an independent computer consultant, author and seminar leader.He participates in both ANSI and ISO C Standards meetings and is the editor of The Journal of C Language Translation, a quarterly publication aimed at implementors of C language translation tools. Readers are encouraged to submit column topics and suggestions to Rex at 2051 Swans Neck Way, Reston, VA 22091 or via UUCP at rex@aussie.com.
Last month I began listing a program that managed a dynamically allocated tree. Missing from that listing were the help and odd node options. This month's column presents these options along with the stack routines used by the print routine to traverse the tree, and the free-node list-management routines.
This month I also provide the remove node option source. This is by far the most complicated option. Removing a node that has no children or only one child is not very difficult, but removing one that has two children is non-trivial since it involves rearranging the tree structure.
The stack-management code is almost identical to that used in the stack columns some months ago. Instead of pushing and popping integers, however, now I push and pop pointers to nodes.
The free-node list-management code was also borrowed from an earlier installment; that on linked lists. In that case, I added a newly freed node to the front of a free-node linked list. I could have done likewise here, but rather than use a linked list I use a binary tree instead. The only difference is that every node in the free-node list has only a left child and that leads to the next free node. Whenever a node is freed, it is added to the free node list by making it the new root and by having its left child pointer point to the old root. As such, in a sense, it behaves just like a linked list.
Listing 1 contains the remaining code.
Consider the case where you add the following nodes to a new tree in the following order: green, blue, black, brown, red, orange, and white. After doing this, enter the commands shown in Figure 1a to see how the tree has been stored. Figure 1b contains the output produced from the print-tree option. The seven nodes are evenly distributed across the tree, which has a depth of three. The tree is perfectly balanced.
Now, consider the case where you add the nodes in alphabetical order: black, blue, brown, green, orange, red, and white. After doing this, enter the commands shown in Figure 2a to see how the tree has been stored. Of course, the tree still has seven nodes, however, the depth has increased from three to seven. Figure 2b shows how the tree looks now. As the depth of the tree is much greater, locating any given node takes longer on average since you don't eliminate any subtrees as you navigate down the list.
Not surprisingly, entering the same nodes in descending alphabetical order produces a similarly-shaped tree except the nodes are joined via the left branch. For example, the code shown in Figure 3a results in the tree shown in Figure 3b.
In the final example, you add the following nodes in the order shown: green, blue, black, brown, cherry, and red. You then proceed to remove nodes and print out the tree after each step so you can see how the tree's shape has changed. Some of the nodes deleted have two children, some only one, and some none at all. You also delete the root node. The code shown in Figure 4a results in a tree shaped as in Figure 4b.
When the blue node (which has a parent and two children) is deleted as in Figure 5a, the result is the tree shown in Figure 5b.
When the black node (which has a parent and no children) is deleted as in Figure 6a, the result is the tree shown in Figure 6b.
When the brown node (which has a parent and one child) is deleted as in Figure 7a, the result is the tree shown in Figure 7b.
And when the green node (which has no parent and two children) is deleted as in Figure 8a, the result is the tree shown in Figure 8b.