This section develops an algorithm for creating or growing a binary search tree that stores records at its nodes. Imagine that you have already processed some records and created a binary search tree for them. Given the next input record, search the current tree for its key value. Assume no duplicates will occur in the tree, although this need not create any real problem, since a node can contain a pointer to a list, stored separately, of records with identical key values. Eventually, since the new record is not in the tree, a null subtree will be reached. However, if this null subtree is replaced by a node that stores this record, the resultant tree will still be a binary search tree. For instance, inserting 45 by this procedure in Figure 9.7(c) produces Figure 9.8. This gives an algorithm for growing a binary search tree. Start with the first input record at the root. For each additional input, search the tree. The search will reach a node whose left or right successor must be followed, but the successor is null. The record replaces that null subtree.
This can be accomplished by using pred from the search implementation, and then invoking the following.
p = malloc(sizeof(binarytreenode));
p->key = keyvalue;
p->leftptr = NULL;
p->rightptr = NULL;
if (keyvalue < pred->key)
pred->leftptr = p;
else
pred->rightptr = p;
We now have algorithms for growing, searching, and inserting records into a binary search tree.