Rex Jaeschke is an independent computer consultant, seminar leader, and author of several books, including The Dictionary of Standard C (Professional Press, Horsham, PA). 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 introduced tree structures and represented them in statically-allocated arrays of structures. Of course, this is rather limiting. In most cases the number of nodes in the tree will be unknown at compile-time. So this month, I provide for dynamic allocation and removal of nodes along the same lines as I did for linked lists earlier in this series.
The new program has several other enhancements. Each node contains a pointer to a string so the length of the string is not limited by the node size. The program can also determine the number of nodes in the tree at any time, display the contents of any given node, determine the maximum depth of the tree, and print out the nodes in alphabetical order. The only tree-traversal option provided is infix order. (The other traversal methods from last month's column could easily be adapted as well.)
By maintaining a tree in some sorted order of node value, you can locate any given node by value much easier on average than if you were using a sorted linked list. And if the tree is reasonably well balanced, each node will be approximately mid-way between each of its subtrees. That is, when the value being searched for is less than that of any node, you follow the left branch. And, when the value is greater than that of any node, you follow the right branch. Eventually, you'll find a match or a NULL pointer which indicates no such node exists. At every node that does not match you follow only the subtree to the left or right. As such, the number of levels you have to search in the worse case depends directly on the depth of the subtree you traverse. In a completely balanced tree, the depth of all possible branches is the same.
Listing 1 contains the first part of the program to manage a dynamically-allocated binary tree.
Figure 1 shows some input and corresponding output when the program was run. To trace what is happening, draw a binary tree and show what happens as each node is added. When the tree is printed, a hyphen (-) indicates a node has no child in a given (left or right) direction.