Binary Search Trees

I l @ ve RuBoard

Binary Search Trees

The binary search tree is a linked structure that incorporates the binary search strategy. Each node in the tree contains an item and two pointers to other nodes, called child nodes . Figure 17.12 shows how the nodes in a binary search tree are linked. The idea is that each node has two child nodes, a left node and a right node. The ordering comes from the fact that the item in a left node precedes the item in the parent node, and the item in the right node follows the item in the parent node. This relationship holds for every node with children. Furthermore, all items that can trace their ancestry back to a left node of a parent contain items that precede the parent item in order, and every item descended from the right node contains items that follow the parent item in order. The tree in Figure 17.12 stores words in this fashion. The top of the tree, in an interesting inversion of botany, is called the root. A tree is a hierarchical organization, meaning that the data are organized in ranks, or levels, with each rank, in general, having ranks above and below it. If a binary search tree is fully populated , each level has twice as many nodes as the level above it.

Figure 17.12. A binary search tree storing words.

Each node in the binary search tree is itself the root of the nodes descending from it, making the node and its descendants a subtree . In Figure 17.12, for example, the nodes containing the words fate , carpet , and llama form the left subtree of the whole tree, and the word voyage is the right subtree of the style-plenum-voyage subtree.

Suppose you want to find an item ”call it the goal ”in such a tree. If the item precedes the root item, you need search only the left half of the tree, and if the goal follows the root item, you need search only the right subtree of the root node. Therefore, one comparison eliminates half the tree. Suppose you search the left half. That means comparing the goal with the item in the left child. If the goal precedes the left-child item, you need search only the left half of its descendants, and so on. As with the binary search, each comparison cuts the number of potential matches in half.

Let's apply this method to see if the word puppy is in the tree shown in Figure 17.12. Comparing puppy to melon (the root node item), you see that puppy , if present, must be in the right half of the tree. Therefore, you go to the right child and compare puppy to style . In this case, puppy precedes the node item, so you must follow the link to the left node. There you find plenum , which precedes puppy . You now have to follow the right branch, but it is empty, so three comparisons show you that puppy is not in the tree.

A binary search tree, then, combines a linked structure with binary search efficiency. The programming price is that putting a tree together is more involved than creating a linked list. Let's make a binary tree the next , and final, ADT project.

A Binary Tree ADT

As usual, we'll start by defining a binary tree in general terms. This particular definition assumes the tree contains no duplicate items. Many of the operations are the same as list operations. The difference is in the hierarchical arrangement of data. Here is an informal summary of this ADT:

Type Name :	Binary Search Tree
Type Properties:	A binary tree is either an empty set of nodes (an empty tree) or a set of nodes with one node designated as the root. Each node has exactly two trees, called the left subtree and the right subtree , descending from it. Each subtree is itself a binary tree, which includes the possibility of being an empty tree. A binary search tree is an ordered binary tree in which each node contains an item, in which all items in the left subtree precede the root item, and in which the root item precedes all items in the right subtree.
Type Operations:	Initializing tree to empty. Determining whether tree is empty. Determining whether tree if full. Determining the number of items in the tree. Adding an item to the tree. Removing an item from the tree. Searching the tree for an item. Visiting each item in the tree.

The Binary Search Tree Interface

In principle, you can implement a binary search tree in a variety of ways. You can even implement one as an array by manipulating array indices. But the most direct way to implement a binary search tree is by using dynamically allocated nodes linked together by using pointers, so we'll start with definitions like these:

 typedef SOMETHING Item; typedef struct node {     Item item;     struct node * left;     struct node * right; } Node; typedef struct tree {     Node * root;     int size; } Tree; 

Each node contains an item, a pointer to the left child node, and a pointer to the right child node. You could define a Tree to be type pointer-to- Node , for you only need know the location of the root node to access the entire tree. Using a structure with a size member, however, makes it simpler to keep track of the size of the tree.

The example we'll be developing is maintaining the roster of the Nerfville Pet Club, with each item consisting of a pet name and a pet kind. With that in mind, we can set up the interface shown in Listing 17.10. We've limited the tree size to 10. The small size makes it easier to test whether the program behaves correctly when the tree fills. You can always set MAXITEMS to a larger value, if necessary.

Listing 17.10 The tree.h interface header file.

 /* tree.h -- binary search tree                          */ /*           no duplicate items are allowed in this tree */ #ifndef _TREE_H_ #define _TREE_H_ /* redefine Item as appropriate */ typedef struct item {     char petname[20];     char petkind[20]; } Item; #define MAXITEMS 10 typedef enum boolean {False, True} BOOLEAN; typedef struct node {     Item item;     struct node * left;    /* pointer to right branch  */     struct node * right;   /* pointer to left branch   */ } Node; typedef struct tree {     Node * root;           /* pointer to root of tree  */     int size;              /* number of items in tree  */ } Tree; /* function prototypes */ /* operation:      initialize a tree to empty          */ /* preconditions:  ptree points to a tree              */ /* postconditions: the tree is initialized to empty    */ void InitializeTree(Tree * ptree); /* operation:      determine if tree is empty          */ /* preconditions:  ptree points to a tree              */ /* postconditions: function returns True if tree is    */ /*                 empty and returns False otherwise   */ BOOLEAN EmptyTree(const Tree * ptree); /* operation:      determine if tree is full           */ /* preconditions:  ptree points to a tree              */ /* postconditions: function returns True if tree is    */ /*                 full and returns False otherwise    */ BOOLEAN FullTree(const Tree * ptree); /* operation:      determine number of items in tree   */ /* preconditions:  ptree points to a tree              */ /* postconditions: function returns number of items in */ /*                 tree                                */ int TreeItems(const Tree * ptree); /* operation:      add an item to a tree               */ /* preconditions:  pi is address of item to be added   */ /*                 ptree points to an initialized tree */ /* postconditions: if possible, function adds item to  */ /*                 tree and returns True; otherwise,    */ /*                 the function returns False          */ BOOLEAN AddItem(const Item * pi, Tree * ptree); /* operation:      find an item in a tree              */ /* preconditions:  pi points to an item                */ /*                 ptree points to an initialized tree */ /* postconditions: function returns True if item is in */ /*                 tree and returns False otherwise    */ BOOLEAN InTree(const Item * pi, const Tree * ptree); /* operation:      delete an item from a tree          */ /* preconditions:  pi is address of item to be deleted */ /*                 ptree points to an initialized tree */ /* postconditions: if possible, function deletes item  */ /*                 from tree and returns True;         */ /*                 otherwise, the function returns False*/ BOOLEAN DeleteItem(const Item * pi, Tree * ptree); /* operation:      apply a function to each item in    */ /*                 the tree                            */ /* preconditions:  ptree points to a tree              */ /*                 pfun points to a function that takes*/ /*                 an Item argument and has no return  */ /*                 value                               */ /* postcondition:  the function pointed to by pfun is  */ /*                 executed once for each item in tree */ void Traverse (const Tree * ptree, void (* pfun)(Item item)); #endif 

The Binary Tree Implementation

Next, proceed to the task of implementing the splendid functions outlined in tree.h . The InitializeTree() , EmptyTree() , FullTree() , and TreeItems() functions are pretty simple, working like their counterparts for the list and queue ADTs, so we'll concentrate on the remaining ones.

Adding an Item

When adding an item to the tree, you should first check whether the tree has room for a new node. Then, because the binary search tree is defined so that it has no duplicate items, you should check that the item is not already in the tree. If the new item clears these first two hurdles, you create a new node, copy the item to the node, and set the node's left and right pointers to NULL . This indicates that the node has no children. Then you should update the size member of the Tree structure to mark the adding of a new item. Next, you have to find where the node should be located in the tree. If the tree is empty, you should set the root pointer to point to the new node. Otherwise, look through the tree for a place to add the node. The AddItem() function follows this recipe, offloading some of the work to functions not yet defined: SeekItem() , MakeNode() , and AddNode() .

 BOOLEAN AddItem(const Item * pi, Tree * ptree) {     Node * new;     if (FullTree(ptree))     {         fprintf(stderr,"Tree is full\n");         return False;             /* early return           */     }     if (SeekItem(pi, ptree).child != NULL)     {         fprintf(stderr, "Attempted to add duplicate item\n");         return False;             /* early return           */     }     new = MakeNode(pi);           /* new points to new node */     if (new == NULL)     {         fprintf(stderr, "Couldn't create node\n");         return False;             /* early return           */     }     /* succeeded in creating a new node */     ptree->size++;     if (ptree->root == NULL)      /* case 1: tree is empty  */         ptree->root = new;        /* new node is tree root  */     else                          /* case 2: not empty      */         AddNode(new,ptree->root); /* add new node to tree   */     return True; } 

The SeekItem() , MakeNode() , and AddNode() functions are not part of the public interface for the Tree type. Instead, they are static functions hidden in the tree.c file. They deal with implementation details, such as nodes, pointers, and structures, that don't belong in the public interface .

The MakeNode() function is pretty simple. It handles the dynamic memory allocation and the initialization of the node. The function argument is a pointer to the new item, and the function's return value is a pointer to the new node. Recall that malloc() returns the null pointer if it can't make the requested allocation. The MakeNode() function initializes the new node only if memory allocation succeeds.

 static Node * MakeNode(const Item * pi) {     Node * new;     new = (Node *) malloc(sizeof(Node));     if (new != NULL)     {         new->item = *pi;         new->left = NULL;         new->right = NULL;     }     return new; } 

The AddNode() function is the second most difficult function in the binary search tree package. It has to determine where the new node goes, and then it has to add it. In particular, it needs to compare the new item with the root item to see whether the new item goes into the left subtree or the right subtree. If the item were a number, you could use < and > to make comparisons. If the item were a string, you could use strcmp() to make comparisons. But the item is a structure containing two strings, so you'll have to define your own functions for making comparisons. The ToLeft() function, to be defined later, returns True if the new item should be in the left subtree, and the ToRight() function returns True if the new item should be in the right subtree. These two functions are analogous to < and > , respectively. Suppose the new item goes to the left subtree. It could be that the left subtree is empty. In that case, the function just makes the left child pointer point to the new node. What if the left subtree isn't empty? Then the function should compare the new item to the item in the left child node, deciding whether the new item should go in the left subtree or right subtree of the child node. This process should continue until the function arrives at an empty subtree, at which point the new node can be added. One way to implement this search is to use recursion, that is, apply the AddNode() function to a child node instead of to the root node. The recursive series of function calls ends when a left or right subtree is empty, that is, when root->left or root->right is NULL . Keep in mind that root is a pointer to the top of the current subtree, so it points to a new, and lower-level, subtree each recursive call. (You might want to review the discussion of recursion in Chapter 9.)

 static void AddNode (Node * new, Node * root) {     if (ToLeft(&new->item, &root->item))     {         if (root->left == NULL)      /* empty subtree       */             root->left = new;        /* so add node here    */         else             AddNode(new, root->left);/* else process subtree*/     }     else if (ToRight(&new->item, &root->item))     {         if (root->right == NULL)             root->right = new;         else             AddNode(new, root->right);     }     else                         /* should be no duplicates */     {         fprintf(stderr,"location error in AddNode()\n");         exit(1);     } } 

The ToLeft() and ToRight() functions depend on the nature of the Item type. The members of the Nerfville Pet Club will be ordered alphabetically by name. If two pets have the same name, order them by kind. If they are also the same kind, then the two items are duplicates, which aren't allowed in the basic search tree. Recall that the standard C library function strcmp() returns a negative number if the string represented by the first argument precedes the second string, returns zero if the two strings are the same, and returns a positive number if the first string follows the second. The ToRight() function has similar code. Using these two functions instead of making comparisons directly in AddNode() makes the code easier to adapt to new requirements. Instead of rewriting AddNode() when a different form of comparison is needed, you rewrite ToLeft() and ToRight() .

 static BOOLEAN ToLeft(const Item * i1, const Item * i2) {     int comp1;     if ((comp1 = strcmp(i1->petname, i2->petname)) < 0)         return True;     else if (comp1 == 0 &&                 strcmp(i1->petkind, i2->petkind) < 0 )         return True;     else         return False; } 

Finding an Item

Three of the interface functions involve searching the tree for a particular item: AddItem() , InTree() , and DeleteItem() . This implementation uses a SeekItem() function to provide that service. The DeleteItem() function has an additional requirement: It needs to know the parent node of the deleted item so that the parent's child pointer can be updated when the child is deleted. Therefore, we designed SeekItem() to return a structure containing two pointers: one pointing to the node containing the item ( NULL if the item isn't found) and one pointing to the parent node ( NULL if the node is the root and has no parent). The structure type is defined as follows:

 typedef struct pair {     Node * parent;     Node * child; } Pair; 

The SeekItem() function can be implemented recursively. However, to expose you to a variety of programming techniques, we'll use a while loop to handle descending through the tree. Like AddNode() , SeekItem() uses ToLeft() and ToRight() to navigate through the tree. SeekItem() initially sets the look.child pointer to point to the root of the tree, and then resets look.child to successive subtrees as it traces the path to where the item should be found. Meanwhile, look.parent is set to point to successive parent nodes. If no matching item is found, look.child will be NULL . If the matching item is in the root node, then look.parent is NULL , for the root node has no parent.

 static Pair SeekItem(const Item * pi, const Tree * ptree) {     Pair look;     look.parent = NULL;     look.child = ptree->root;     if (look.child == NULL)         return look;                /* early return         */     while (look.child != NULL)     {         if (ToLeft(pi, &(look.child->item)))         {             look.parent = look.child;             look.child = look.child->left;         }         else if (ToRight(pi, &(look.child->item)))         {             look.parent = look.child;             look.child = look.child->right;         }         else      /* must be same if not to left or right   */             break;/* look.child is address of node with item*/     }     return look; } 

Note that because the SeekItem() function returns a structure, it can be used with the structure membership operator. For example, the AddItem() function used the following code:

 if (SeekItem(pi, ptree).child != NULL) 

After you have SeekItem() , it's simple to code the InTree() public interface function:

 BOOLEAN InTree(const Item * pi, const Tree * ptree) {     return (SeekItem(pi, ptree).child == NULL) ? False : True; } 

Deleting an Item

Removing an item is the most difficult of the tasks because you have to reconnect the remaining subtrees to form a valid tree. Before attempting to program this task, it's a good idea to develop a visual picture of what has to be done.

Figure 17.13 illustrates the simplest case. Here the node to be deleted has no children. Such a node is called a leaf . All that has to be done in this case is to reset a pointer in the parent node to NULL and to use the free() function to reclaim the memory used by the deleted node.

Figure 17.13. Deleting a leaf.

Next in complexity is deleting a node with one child. Deleting the node leaves the child subtree separate from the rest of the tree. To fix this, the address of the child subtree needs to be stored in the parent node at the location formerly occupied by the address of the deleted node (see Figure 17.14).

Figure 17.14. Deleting a one-child node.

Finally, you have deleting a node with two subtrees. One subtree, say the left, can be attached to where the deleted node was formerly attached. But where should the remaining subtree go? Keep in mind the basic design of a tree. Every item in a left subtree precedes the item in the parent node, and every item in a right subtree follows the item in the parent node. This means that every item in the right subtree comes after every item in the left subtree. Also, because the right subtree once was part of the subtree headed by the deleted node, every item in the right subtree comes before the parent node of the deleted node. Imagine coming down the tree looking for where to place the head of the right subtree. It comes before the parent node, so you have to go down the left subtree from there. However, it comes after every item in the left subtree, so you have to take the right branch of the left subtree and see whether it has an opening for a new node. If not, you must go down the right side of the left subtree until you do find an opening. Figure 17.15 illustrates the approach.

Figure 17.15. Deleting a two-child node.

Deleting a Node

Now you can begin to plan the necessary functions, separating the job into two tasks. One is associating a particular item with the node to be deleted, and the second is actually deleting the node. One point to note is that all the cases involve modifying a pointer in the parent node, which has two important consequences:

• The program has to identify the parent node of the node to be deleted.

• To modify the pointer, the code must pass the address of that pointer to the deleting function.

We'll come back to the first point later. Meanwhile, the pointer to be modified is itself of type Node * , or pointer-to- Node . Because the function argument is the address of that pointer, the argument will be of type Node ** , or pointer-to-pointer-to- Node . Assuming you have the proper address available, you can write the deletion function as the following:

 static void DeleteNode(Node **ptr) /* ptr is address of parent member pointing to target node  */ {     Node * temp;     if ( (*ptr)->left == NULL)     {         temp = *ptr;         *ptr = (*ptr)->right;         free(temp);     }     else if ( (*ptr)->right == NULL)     {         temp = *ptr;         *ptr = (*ptr)->left;         free(temp);     }     else    /* deleted node has two children */     {         /* find where to reattach right subtree */         for (temp = (*ptr)->left; temp->right != NULL;                 temp = temp->right)             continue;         temp->right = (*ptr)->right;         temp = *ptr;         *ptr =(*ptr)->left;         free(temp);     } } 

This function explicitly handles three cases: a node with no left child, a node with no right child, and a node with two children. A node with no children can be considered a special case of a node with no left child. If the node has no left child, the code assigns the address of the right child to the parent pointer. But if the node also has no right child, that pointer is NULL , which is the proper value for the no-child case.

Notice that the code uses a temporary pointer to keep track of the address of the deleted node. After the parent pointer ( *ptr ) is reset, the program would lose track of where the deleted node is, but you need that information for the free() function. So the program stores the original value of *ptr in temp , and then uses temp to free the memory used for the deleted node.

The code for the two-child case first uses the temp pointer in a for loop to search down the right side of the left subtree for an empty spot. When it finds an empty spot, it attaches the right subtree there. Then it reuses temp to keep track of where the deleted node is. Next, it attaches the left subtree to the parent, and then frees the node pointed to by temp .

Note that because ptr is type Node ** , *ptr is of type Node * , making it the same type as temp .

Deleting an Item

The remaining part of the problem is associating a node with a particular item. You can use the SeekNode() function to do so. Recall that it returns a structure containing a pointer to the parent node and a pointer to the node containing the item. Then you can use the parent node pointer to get the proper address to pass to the DeleteNode() function. The DeleteItem() function, shown here, follows this plan:

 BOOLEAN DeleteItem(const Item * pi, Tree * ptree) {     Pair look;     look = SeekItem(pi, ptree);     if (look.child == NULL)         return False;     if (look.parent == NULL)      /* delete root item       */         DeleteNode(&ptree->root);     else if (look.parent->left == look.child)         DeleteNode(&look.parent->left);     else         DeleteNode(&look.parent->right);     ptree->size--;     return True; } 

First, the return value of the SeekItem() function is assigned to the look structure variable. If look.child is NULL , the search failed to find the time, and the DeleteItem() function quits, returning False . If the Item is found, the function handles three cases. First, a NULL value for look.parent means the item was found in the root node. In this case, there is no parent node to update. Instead, the program has to update the root pointer in the Tree structure. Therefore, the function passes the address of that pointer to the DeleteNode() function. Otherwise, the program determines whether the node to be deleted is the left child or the right child of the parent, and then it passes the address of the appropriate pointer.

Note that the public interface function ( DeleteItem() ) speaks in terms of end- user concerns (items and trees), and the hidden DeleteNode() function handles the nitty-gritty of pointer shuffling.

Traversing the Tree

Traversing a tree is more involved than traversing a linked list because each node has two branches to follow. This branching nature makes divide-and-conquer recursion (Chapter 9) a natural choice for handling the problem. At each node, the function should do the following:

• Process the item in the node.

• Process the left subtree (a recursive call).

• Process the right subtree (a recursive call).

You can break this process down into two functions: Traverse() and InOrder() . Note that the InOrder() function processes the left subtree, then processes the item, and then processes the right subtree. This order results in traversing the tree in alphabetical order. If you have the time, you might want to see what happens if you use different orders, such as item-left-right and left-right-item.

 void Traverse (const Tree * ptree, void (* pfun)(Item item)) {     if (ptree != NULL)         InOrder(ptree->root, pfun); } static void InOrder(const Node * root, void (* pfun)(Item item)) {     if (root != NULL)     {         InOrder(root->left, pfun);         (*pfun)(root->item);         InOrder(root->right, pfun);     } } 

Listing 17.11 shows the entire tree.c code. Together, tree.h and tree.c constitute a tree programming package.

Listing 17.11 The tree.c implementation file.

 /* tree.c -- tree support functions */ #include <string.h> #include <stdio.h> #include <stdlib.h> #include "tree.h" /* local data type */ typedef struct pair {     Node * parent;     Node * child; } Pair; /* protototypes for local functions */ static Node * MakeNode(const Item * pi); static BOOLEAN ToLeft(const Item * i1, const Item * i2); static BOOLEAN ToRight(const Item * i1, const Item * i2); static void AddNode (Node * new, Node * root); static void InOrder(const Node * root, void (* pfun)(Item item)); static Pair SeekItem(const Item * pi, const Tree * ptree); static void DeleteNode(Node **ptr); /* function definitions */ void InitializeTree(Tree * ptree) {     ptree->root = NULL;     ptree->size = 0; } BOOLEAN EmptyTree(const Tree * ptree) {     if (ptree->root == NULL)         return True;     else         return False; } BOOLEAN FullTree(const Tree * ptree) {     if (ptree->size == MAXITEMS)         return True;     else         return False; } int TreeItems(const Tree * ptree) {     return ptree->size; } BOOLEAN AddItem(const Item * pi, Tree * ptree) {     Node * new;     if (FullTree(ptree))     {         fprintf(stderr,"Tree is full\n");         return False;             /* early return           */     }     if (SeekItem(pi, ptree).child != NULL)     {         fprintf(stderr, "Attempted to add duplicate item\n");         return False;             /* early return           */     }     new = MakeNode(pi);           /* new points to new node */     if (new == NULL)     {         fprintf(stderr, "Couldn't create node\n");         return False;             /* early return           */     }     /* succeeded in creating a new node */     ptree->size++;     if (ptree->root == NULL)      /* case 1: tree is empty  */         ptree->root = new;        /* new node is tree root  */     else                          /* case 2: not empty      */         AddNode(new,ptree->root); /* add new node to tree   */     return True; } BOOLEAN InTree(const Item * pi, const Tree * ptree) {     return (SeekItem(pi, ptree).child == NULL) ? False : True; } BOOLEAN DeleteItem(const Item * pi, Tree * ptree) {     Pair look;     look = SeekItem(pi, ptree);     if (look.child == NULL)         return False;     if (look.parent == NULL)      /* delete root item       */         DeleteNode(&ptree->root);     else if (look.parent->left == look.child)         DeleteNode(&look.parent->left);     else         DeleteNode(&look.parent->right);     ptree->size--;     return True; } void Traverse (const Tree * ptree, void (* pfun)(Item item)) {     if (ptree != NULL)         InOrder(ptree->root, pfun); } /* local functions */ static void InOrder(const Node * root, void (* pfun)(Item item)) {     if (root != NULL)     {         InOrder(root->left, pfun);         (*pfun)(root->item);         InOrder(root->right, pfun);     } } static void AddNode (Node * new, Node * root) {     if (ToLeft(&new->item, &root->item))     {         if (root->left == NULL)      /* empty subtree       */             root->left = new;        /* so add node here    */         else             AddNode(new, root->left);/* else process subtree*/     }     else if (ToRight(&new->item, &root->item))     {         if (root->right == NULL)             root->right = new;         else             AddNode(new, root->right);     }     else                         /* should be no duplicates */     {         fprintf(stderr,"location error in AddNode()\n");         exit(1);     } } static BOOLEAN ToLeft(const Item * i1, const Item * i2) {     int comp1;     if ((comp1 = strcmp(i1->petname, i2->petname)) < 0)         return True;     else if (comp1 == 0 &&                 strcmp(i1->petkind, i2->petkind) < 0 )         return True;     else         return False; } static BOOLEAN ToRight(const Item * i1, const Item * i2) {     int comp1;     if ((comp1 = strcmp(i1->petname, i2->petname)) > 0)         return True;     else if (comp1 == 0 &&                 strcmp(i1->petkind, i2->petkind) > 0 )         return True;     else         return False; } static Node * MakeNode(const Item * pi) {     Node * new;     new = (Node *) malloc(sizeof(Node));     if (new != NULL)     {         new->item = *pi;         new->left = NULL;         new->right = NULL;     }     return new; } static Pair SeekItem(const Item * pi, const Tree * ptree) {     Pair look;     look.parent = NULL;     look.child = ptree->root;     if (look.child == NULL)         return look;                /* early return         */     while (look.child != NULL)     {         if (ToLeft(pi, &(look.child->item)))         {             look.parent = look.child;             look.child = look.child->left;         }         else if (ToRight(pi, &(look.child->item)))         {             look.parent = look.child;             look.child = look.child->right;         }         else      /* must be same if not to left or right   */             break;/* look.child is address of node with item*/     }     return look; } static void DeleteNode(Node **ptr) /* ptr is address of parent member pointing to target node  */ {     Node * temp;     if ( (*ptr)->left == NULL)     {         temp = *ptr;         *ptr = (*ptr)->right;         free(temp);     }     else if ( (*ptr)->right == NULL)     {         temp = *ptr;         *ptr = (*ptr)->left;         free(temp);     }     else    /* deleted node has two children */     {         /* find where to reattach right subtree */         for (temp = (*ptr)->left; temp->right != NULL;                 temp = temp->right)             continue;         temp->right = (*ptr)->right;         temp = *ptr;         *ptr =(*ptr)->left;         free(temp);     } } 

Trying the Tree

Now that you have the interface and the function implementations , let's use them. The program in Listing 17.12 uses a menu to offer a choice of adding pets to the club membership roster, listing members, reporting the number of members, checking for membership, and quitting. The brief main() function concentrates on the essential program outline. Supporting functions do most of the work.

Listing 17.12 The petclub.c program.

 /* petclub.c -- use a binary search tree */ #include <stdio.h> #include <string.h> #include <ctype.h> #include "tree.h" char menu(void); void addpet(Tree * pt); void droppet(Tree * pt); void showpets(const Tree * pt); void findpet(const Tree * pt); void printitem(Item item); void uppercase(char * str); int main(void) {     Tree pets;     char choice;     InitializeTree(&pets);     while ((choice = menu()) != `q')     {         switch (choice)         {             case `a' :  addpet(&pets);                         break;             case `l' :  showpets(&pets);                         break;             case `f' :  findpet(&pets);                         break;             case `n' :  printf("%d pets in club\n",                                 TreeItems(&pets));                         break;             case `d' :  droppet(&pets);                         break;             default  :  puts("Switching error");         }     }     puts("Bye.");     return 0; } char menu(void) {     int ch;     puts("Nerfville Pet Club Membership Program");     puts("Enter the letter corresponding to your choice:");     puts("a) add a pet          l) show list of pets");     puts("n) number of pets     f) find pets");     puts("d) delete a pet       q) quit");     while ((ch = getchar()) != EOF)     {         while (getchar() != `\n')  /* discard rest of line */             continue;         ch = tolower(ch);         if (strchr("alrfndq",ch) == NULL)             puts("Please enter an a, l, f, n, d, or q:");         else             break;     }     if (ch == EOF)       /* make EOF cause program to quit */         ch = `q';     return ch; } void addpet(Tree * pt) {     Item temp;     if (FullTree(pt))         puts("No room in the club!");     else     {         puts("Please enter name of pet:");         gets(temp.petname);         puts("Please enter pet kind:");         gets(temp.petkind);         uppercase(temp.petname);         uppercase(temp.petkind);         AddItem(&temp, pt);     } } void showpets(const Tree * pt) {     if (EmptyTree(pt))         puts("No entries!");     else         Traverse(pt, printitem); } void printitem(Item item) {     printf("Pet: %-19s  Kind: %-19s\n", item.petname,             item.petkind); } void findpet(const Tree * pt) {     Item temp;     if (EmptyTree(pt))     {         puts("No entries!");         return;     /* quit function if tree is empty */     }     puts("Please enter name of pet you wish to find:");     gets(temp.petname);     puts("Please enter pet kind:");     gets(temp.petkind);     uppercase(temp.petname);     uppercase(temp.petkind);     printf("%s the %s ", temp.petname, temp.petkind);     if (InTree(&temp, pt))         printf("is a member.\n");     else         printf("is not a member.\n"); } void droppet(Tree * pt) {     Item temp;     if (EmptyTree(pt))     {         puts("No entries!");         return;     /* quit function if tree is empty */     }     puts("Please enter name of pet you wish to delete:");     gets(temp.petname);     puts("Please enter pet kind:");     gets(temp.petkind);     uppercase(temp.petname);     uppercase(temp.petkind);     printf("%s the %s ", temp.petname, temp.petkind);     if (DeleteItem(&temp, pt))         printf("is dropped from the club.\n");     else         printf("is not a member.\n"); } void uppercase(char * str) {     while (*str != ` 
 /* petclub.c -- use a binary search tree */ #include <stdio.h> #include <string.h> #include < ctype .h> #include "tree.h" char menu(void); void addpet(Tree * pt); void droppet(Tree * pt); void showpets(const Tree * pt); void findpet(const Tree * pt); void printitem(Item item); void uppercase(char * str); int main(void) { Tree pets; char choice; InitializeTree(&pets); while ((choice = menu()) != `q') { switch (choice) { case `a' : addpet(&pets); break; case `l' : showpets(&pets); break; case `f' : findpet(&pets); break; case `n' : printf("%d pets in club\n", TreeItems(&pets)); break; case `d' : droppet(&pets); break; default : puts("Switching error"); } } puts("Bye."); return 0; } char menu(void) { int ch; puts("Nerfville Pet Club Membership Program"); puts("Enter the letter corresponding to your choice:"); puts("a) add a pet l) show list of pets"); puts("n) number of pets f) find pets"); puts("d) delete a pet q) quit"); while ((ch = getchar()) != EOF) { while ( getchar () != `\n') /* discard rest of line */ continue; ch = tolower (ch); if ( strchr ("alrfndq",ch) == NULL) puts("Please enter an a, l, f, n, d, or q:"); else break; } if (ch == EOF) /* make EOF cause program to quit */ ch = `q'; return ch; } void addpet(Tree * pt) { Item temp; if (FullTree(pt)) puts("No room in the club!"); else { puts("Please enter name of pet:"); gets(temp.petname); puts("Please enter pet kind:"); gets(temp.petkind); uppercase(temp.petname); uppercase(temp.petkind); AddItem(&temp, pt); } } void showpets(const Tree * pt) { if (EmptyTree(pt)) puts("No entries!"); else Traverse(pt, printitem); } void printitem(Item item) { printf("Pet: %-19s Kind: %-19s\n", item.petname, item.petkind); } void findpet(const Tree * pt) { Item temp; if (EmptyTree(pt)) { puts("No entries!"); return; /* quit function if tree is empty */ } puts("Please enter name of pet you wish to find:"); gets(temp.petname); puts("Please enter pet kind:"); gets(temp.petkind); uppercase(temp.petname); uppercase(temp.petkind); printf("%s the %s ", temp.petname, temp.petkind); if (InTree(&temp, pt)) printf("is a member.\n"); else printf("is not a member.\n"); } void droppet(Tree * pt) { Item temp; if (EmptyTree(pt)) { puts("No entries!"); return; /* quit function if tree is empty */ } puts("Please enter name of pet you wish to delete:"); gets(temp.petname); puts("Please enter pet kind:"); gets(temp.petkind); uppercase(temp.petname); uppercase(temp.petkind); printf("%s the %s ", temp.petname, temp.petkind); if (DeleteItem(&temp, pt)) printf("is dropped from the club.\n"); else printf("is not a member.\n"); } void uppercase(char * str) { while (*str != `\0') { *str = toupper(*str); str++; } } 
 ')     {         *str = toupper(*str);         str++;     } } 

The program converts all letters to uppercase so that SNUFFY , Snuffy , and snuffy are not considered distinct names . Here is a sample run:

 Nerfville Pet Club Membership Program Enter the letter corresponding to your choice: a) add a pet          l) show list of pets n) number of pets     f) find pets q) quit  a  Please enter name of pet:  Quincy  Please enter pet kind:  pig  Nerfville Pet Club Membership Program Enter the letter corresponding to your choice: a) add a pet          l) show list of pets n) number of pets     f) find pets q) quit  a  Please enter name of pet:  Betty  Please enter pet kind:  Boa  Nerfville Pet Club Membership Program Enter the letter corresponding to your choice: a) add a pet          l) show list of pets n) number of pets     f) find pets q) quit  a  Please enter name of pet:  Hiram Jinx  Please enter pet kind:  domestic cat  Nerfville Pet Club Membership Program Enter the letter corresponding to your choice: a) add a pet          l) show list of pets n) number of pets     f) find pets q) quit  n  3 pets in club Nerfville Pet Club Membership Program Enter the letter corresponding to your choice: a) add a pet          l) show list of pets n) number of pets     f) find pets q) quit  l  Pet: BETTY                Kind: BOA Pet: HIRAM JINX           Kind: DOMESTIC CAT Pet: QUINCY               Kind: PIG Nerfville Pet Club Membership Program Enter the letter corresponding to your choice: a) add a pet          l) show list of pets n) number of pets     f) find pets q) quit  q  Bye. 

Tree Thoughts

The binary search tree has some drawbacks. For instance, the binary search tree is efficient only if it is fully populated, or balanced . Suppose you're storing words that are entered randomly . Chances are the tree will have a fairly bushy look, as in Figure 17.12. Now suppose you enter data in alphabetical order. Then each new node would be added to the right, and the tree might look like Figure 17.16. The Figure 17.12 tree is said to be balanced , and the Figure 17.16 tree is unbalanced . Searching this tree is no more effective than sequentially searching a linked list.

Figure 17.16. A badly unbalanced binary search tree.

One way to avoid stringy trees is use more care when building a tree. If a tree or subtree begins to get too unbalanced on one side or the other, rearrange the nodes to restore a better balance. Similarly, you might need to rearrange the tree after a deletion. The Russian mathematicians Adel'son-Vel'skii and Landis developed an algorithm to do this. Trees built with their method are called AVL trees. It takes longer to build a balanced tree because of the extra restructuring, but you ensure maximum, or nearly maximum, search efficiency.

You might want a binary search tree that does allow duplicate items. Suppose, for example, you wanted to analyze some text by tracking how many times each word in the text appears. One approach is to define Item as a structure that holds one word and a number. The first time a word is encountered , it's added to the tree, and the number is set to 1 . The next time the same word is encountered, the program finds the node containing the word and increments the number. It doesn't take much work to modify the basic binary search tree to behave in this fashion.

For another possible variation, consider the Nerfville Pet Club. The example ordered the tree by both name and kind, so it could hold Sam the cat in one node, Sam the dog in another node, and Sam the goat in a third node. You couldn't have two cats called Sam, however. Another approach is to order the tree just by name. Making that change alone would allow for only one Sam, regardless of kind, but you could then define Item to be a list of structures instead of being a single structure. The first time a Sally shows up, the program would create a new node, then create a new list, and then add Sally and her kind to the list. The next Sally that shows up would be directed to the same node and added to the list.

I l @ ve RuBoard