## 12.6. ImplementationThe example that follows is an implementation of the principal functions for a binary search tree, and uses dynamic memory management. This tree is intended to be usable for data of any kind. For this reason, the structure type of the nodes includes a flexible member to store the data, and a member indicating the size of the data: typedef struct Node { struct Node *left, // Pointers to the left and *right; // right child nodes. size_t size; // Size of the data payload. char data[ ]; // The data itself. } Node_t; The pointers As the user of our implementation, you must provide two auxiliary functions. The first of these is a function to obtain a key that corresponds to the data value passed to it, and the second compares two keys. The first function has the following type: typedef const void *GetKeyFunc_t( const void *dData ); The second function has a type like that of the comparison function used by the standard function typedef int CmpFunc_t( const void *pKey1, const void *pKey2 ); The arguments passed on calling the comparison function are pointers to the two keys that you want to compare. The function's return value is less than zero, if the first key is less than the second; or equal to zero, if the two keys are equal; or greater than zero, if the first key is greater than the second. The key may be the same as the data itself. In this case, you need to provide only a comparison function. Next, we define a structure type to represent a tree. This structure has three members: a pointer to the root of the tree; a pointer to the function to calculate a key, with the type typedef struct { struct Node *pRoot; // Pointer to the root. CmpFunc_t *cmp; // Compares two keys. GetKeyFunc_t *getKey; // Converts data into a key value. } BST_t; The pointer The elementary operations for a binary search tree are performed by functions that insert, find, and delete nodes, and functions to traverse the tree in various ways, performing a programmer-specified operation on each element if desired. The prototypes of these functions, and the typedef declarations of The function prototypes in BST_t *newBST( CmpFunc_t *cmp, GetKeyFunc_t *getKey ); This function dynamically generates a new object with the type `BST_t`, and returns a pointer to it._Bool BST_insert( BST_t *pBST, const void *pData, size_t size ); `BST_insert( )`dynamically generates a new node, copies the data referenced by`pData`to the node, and inserts the node in the specified tree.const void *BST_search( BST_t *pBST, const void *pKey ); The `BST_search( )`function searches the tree and returns a pointer to the data item that matches the key referenced by the`pKey`argument._Bool BST_erase( BST_t *pBST, const void *pKey ); This function deletes the first node whose data contents match the key referenced by `pKey`.void BST_clear( BST_t *pBST ); `BST_clear( )`deletes all nodes in the tree, leaving the tree empty.int BST_inorder( BST_t *pBST, _Bool (*action)( void *pData )); int BST_rev_inorder( BST_t *pBST, _Bool (*action)( void *pData )); int BST_preorder( BST_t *pBST, _Bool (*action)( void *pData )); int BST_postorder( BST_t *pBST, _Bool (*action)( void *pData )); Each of these functions traverses the tree in a certain order, and calls the function referenced by `action`to manipulate the data contents of each node. If the action modifies the node's data, then at least the key value must remain unchanged to preserve the tree's sorting order.
The function definitions, along with some recursive helper functions, are placed in the source file ## 12.6.1. Generating an Empty TreeWhen you create a new binary search tree, you specify how a comparison between two data items is performed. For this purpose, the ```
const void *defaultGetKey( const void *pData ) { return pData; }
BST_t *newBST( CmpFunc_t *cmp, GetKeyFunc_t *getKey )
{
BST_t *pBST = NULL;
if ( cmp != NULL )
pBST = malloc( sizeof(BST_t) );
if ( pBST != NULL )
{
pBST->pRoot = NULL;
pBST->cmp = cmp;
pBST->getKey = (getKey != NULL) ? getKey : defaultGetKey;
}
return pBST;
}
``` The pointer to ## 12.6.2. Inserting New DataTo copy a data item to a new leaf node in the tree, pass the data to the The static _Bool insert( BST_t *pBST, Node_t **ppNode, const void *pData, size_t size ); _Bool BST_insert( BST_t *pBST, const void *pData, size_t size ) { if ( pBST == NULL || pData == NULL || size == 0 ) return false; return insert( pBST, &(pBST->pRoot), pData, size ); } static _Bool insert( BST_t *pBST, Node_t **ppNode, const void *pData, size_t size ) { Node_t *pNode = *ppNode; // Pointer to the root node of the subtree // to insert the new node in. if ( pNode == NULL ) { // There's a place for a new leaf here. pNode = malloc( sizeof(Node_t) + size ); if ( pNode != NULL ) { pNode->left = pNode->right = NULL; // Initialize the new node's // members. memcpy( pNode->data, pData, size ); *ppNode = pNode; // Insert the new node. return true; } else return false; } else // Continue looking for a place ... { const void *key1 = pBST->getKey( pData ), *key2 = pBST->getKey( pNode->data ); if ( pBST->cmp( key1, key2 ) < 0 ) // ... in the left subtree, return insert( pBST, &(pNode->left), pData, size ); else // or in the right subtree. return insert( pBST, &(pNode->right), pData, size ); } } ## 12.6.3. Finding Data in the TreeThe function The search operation uses the recursive helper function static const void *search( BST_t *pBST, const Node_t *pNode, const void *pKey ); const void *BST_search( BST_t *pBST, const void *pKey ) { if ( pBST == NULL || pKey == NULL ) return NULL; return search( pBST, pBST->pRoot, pKey ); // Start at the root of the // tree. } static const void *search( BST_t *pBST, const Node_t *pNode, const void *pKey ) { if ( pNode == NULL ) return NULL; // No subtree to search; // no match found. else { // Compare data: int cmp_res = pBST->cmp( pKey, pBST->getKey(pNode->data) ); if ( cmp_res == 0 ) // Found a match. return pNode->data; else if ( cmp_res < 0 ) // Continue the search return search( pBST, pNode->left, pKey ); // in the left subtree, else return search( pBST, pNode->right, pKey ); // or in the right // subtree. } } ## 12.6.4. Removing Data from the TreeThe The actual searching and deleting is performed by means of the recursive helper function The recursive helper function ```
static Node_t *detachMin( Node_t **ppNode )
{
Node_t *pNode = *ppNode; // A pointer to the current node.
if ( pNode == NULL )
return NULL; // pNode is an empty subtree.
else if ( pNode->left != NULL )
return detachMin( &(pNode->left) ); // The minimum is in the left
// subtree.
else
{ // pNode points to the minimum node.
*ppNode = pNode->right; // Attach the right child to the parent.
return pNode;
}
}
``` Now we can use this function in the definition of static _Bool erase( BST_t *pBST, Node_t **ppNode, const void *pKey ); _Bool BST_erase( BST_t *pBST, const void *pKey ) { if ( pBST == NULL || pKey == NULL ) return false; return erase( pBST, &(pBST->pRoot), pKey ); // Start at the root of // the tree. } static _Bool erase( BST_t *pBST, Node_t **ppNode, const void *pKey ) { Node_t *pNode = *ppNode; // Pointer to the current node. if ( pNode == NULL ) return false; // No match found. // Compare data: int cmp_res = pBST->cmp( pKey, pBST->getKey(pNode->data) ); if ( cmp_res < 0 ) // Continue the search return erase( pBST, &(pNode->left), pKey ); // in the left subtree, else if ( cmp_res > 0 ) return erase( pBST, &(pNode->right), pKey ); // or in the right // subtree. else { // Found the node to be deleted. if ( pNode->left == NULL ) // If no more than one child, *ppNode = pNode->right; // attach the child to the parent. else if ( pNode->right == NULL ) *ppNode = pNode->left; else // Two children: replace the node with { // the minimum from the right subtree. Node_t *pMin = detachMin( &(pNode->right) ); *ppNode = pMin; // Graft it onto the deleted node's parent. pMin->left = pNode->left; // Graft the deleted node's children. pMin->right = pNode->right; } free( pNode ); // Release the deleted node's storage. return true; } } A function in Example 12-2, ## Example 12-2. The BST_clear( ) and clear( ) functionsstatic void clear( Node_t *pNode ); void BST_clear( BST_t *pBST ) { if ( pBST != NULL) { clear( pBST->pRoot ); pBST->pRoot = NULL; } } static void clear( Node_t *pNode ) { if ( pNode != NULL ) { clear( pNode->left ); clear( pNode->right ); free( pNode ); } } ## 12.6.5. Traversing a TreeThere are several recursive schemes for traversing a binary tree . They are often designated by abbreviations in which L stands for a given node's left subtree, R for its right subtree, and N for the node itself: *In-order or LNR traversal*First traverse the node's left subtree, then visit the node itself, then traverse the right subtree. *Pre-order or NLR traversal*First visit the node itself, then traverse its left subtree, then its right subtree. *Post-order or LRN traversal*First traverse the node's left subtree, then the right subtree, then visit the node itself.
An It's not always advantageous to process the data items in their sorting order, though. For example, if you want to store the data items in a file and later insert them in a new tree as you read them from the file, you might prefer to traverse the tree in Each of the traversal functions takes as its second argument a pointer to an "action" function that it calls for each node visited. The action function takes as its argument a pointer to the current node's data, and returns The following example contains the definition of the static int inorder( Node_t *pNode, _Bool (*action)(void *pData) ); int BST_inorder( BST_t *pBST, _Bool (*action)(void *pData) ) { if ( pBST == NULL || action == NULL ) return 0; else return inorder( pBST->pRoot, action ); } static int inorder( Node_t *pNode, _Bool (*action)(void *pData) ) { int count = 0; if ( pNode == NULL ) return 0; count = inorder( pNode->left, action ); // L: Traverse the left // subtree. if ( action( pNode->data )) // N: Visit the current node ++count; // itself. count += inorder( pNode-> right, action ); // R: Traverse the right // subtree. return count; } ## 12.6.6. A Sample ApplicationTo illustrate one use of a binary search tree, the filter program in Example 12-3, sortlines < demo.txt This command prints the contents of the file ## Example 12-3. The sortlines program// This program reads each line of text into a node of a binary tree, // then prints the text in sorted order. #include <stdio.h> #include <string.h> #include <stdlib.h> #include "BSTree.h" // Prototypes of the BST functions. #define LEN_MAX 1000 // Maximum length of a line. char buffer[LEN_MAX]; // Action to perform for each line: _Bool printStr( void *str ) { return printf( "%s", str ) >= 0; } int main( ) { BST_t *pStrTree = newBST( (CmpFunc_t*)strcmp, NULL ); int n; while ( fgets( buffer, LEN_MAX, stdin ) != NULL ) // Read each line. { size_t len = strlen( buffer ); // Length incl. newline // character. if ( !BST_insert( pStrTree, buffer, len+1 )) // Insert the line in the break; // tree. } if ( !feof(stdin) ) { // If unable to read the // entire text: fprintf( stderr, "sortlines: " "Error reading or storing text input.\n" ); exit( EXIT_FAILURE ); } n = BST_inorder( pStrTree, printStr ); // Print each line, in // sorted order. fprintf( stderr, "\nsortlines: Printed %d lines.\n", n ); BST_clear( pStrTree ); // Discard all nodes. return 0; } The loop that reads input lines breaks prematurely if a read error occurs, or if there is insufficient memory to insert a new node in the tree. In such cases, the program exits with an error message. An in-order traversal visits every node of the tree in sorted order. The return value of The The binary search tree presented in this chapter can be used for any kind of data. Most applications require the |