/* Exercise 12.23 Solution */ #include #include #include /* TreeNode structure definition */ struct TreeNode { struct TreeNode *leftPtr; /* pointer to left subtree */ int data; /* node data */ struct TreeNode *rightPtr; /* pointer to right subtree */ }; /* end struct TreeNode */ typedef struct TreeNode TreeNode; typedef TreeNode *TreeNodePtr; /* function prototypes */ void insertNode( TreeNodePtr *treePtr, int value ); TreeNodePtr binaryTreeSearch( TreeNodePtr treePtr, const int key ); int main() { int i; /* loop counter */ int item; /* random value to insert in tree */ int searchKey; /* value to search for */ TreeNodePtr rootPtr = NULL; /* points to the tree root */ TreeNodePtr searchResultPtr; /* pointer to search result */ srand( time( NULL ) ); /* randomize */ printf( "The numbers being placed in the tree are:\n" ); /* insert random values between 1 and 20 in the tree */ for ( i = 1; i <= 10; i++ ) { item = 1 + rand() % 20; printf( "%3d", item ); insertNode( &rootPtr, item ); } /* end for */ /* prompt user and read integer search key */ printf( "\n\nEnter an integer to search for: " ); scanf( "%d", &searchKey ); searchResultPtr = binaryTreeSearch( rootPtr, searchKey ); /* if searchKey not found */ if ( searchResultPtr == NULL ) { printf( "\n%d was not found in the tree.\n\n", searchKey ); } /* end if */ else { /* if key found */ printf( "\n%d was found in the tree.\n\n", searchResultPtr->data ); } /* end else */ return 0; /* indicate successful termination */ } /* end main */ /* insert a node into the tree */ void insertNode( TreeNodePtr *treePtr, int value ) { /* if treePtr is NULL */ if ( *treePtr == NULL ) { /* dynamically allocate memory */ *treePtr = malloc( sizeof( TreeNode ) ); /* if memory was allocated, insert node */ if ( *treePtr != NULL ) { ( *treePtr )->data = value; ( *treePtr )->leftPtr = NULL; ( *treePtr )->rightPtr = NULL; } /* end if */ else { printf( "%d not inserted. No memory available.\n", value ); } /* end else */ } /* end if */ else { /* recursively call insertNode */ /* insert node in left subtree */ if ( value < ( *treePtr )->data ) { insertNode( &( ( *treePtr )->leftPtr ), value ); } /* end if */ else { /* insert node in right subtree */ if ( value > ( *treePtr )->data ) { insertNode( &( ( *treePtr )->rightPtr ), value ); } /* end if */ else { /* duplicate value */ printf( "dup" ); } /* end else */ } /* end else */ } /* end else */ } /* end function insertNode */ /* search for key in tree */ TreeNodePtr binaryTreeSearch( TreeNodePtr treePtr, const int key ) { /* traverse the tree inOrder */ if ( treePtr == NULL ) { return NULL; /* key not found */ } /* end if */ else if ( treePtr->data == key ) { return treePtr; /* key found */ } /* end else if */ else if ( key < treePtr->data ) { binaryTreeSearch( treePtr->leftPtr, key ); /* search left */ } /* end else if */ else if ( key > treePtr->data ) { binaryTreeSearch( treePtr->rightPtr, key ); /* search right */ } /* end else if */ } /* end function binaryTreeSearch */