training

Code I wrote during training
git clone git://git.bitsmanent.org/training
Log | Files | Refs | README

fig12_19_mod3.c (5962B)


      1 /* Exercise 12.22 */
      2 
      3 /* Fig. 12.19: fig12_19.c
      4    Create a binary tree and traverse it 
      5    preorder, inorder, and postorder */
      6 #include <stdio.h>
      7 #include <stdlib.h>
      8 #include <time.h>
      9 
     10 /* self-referential structure */
     11 struct treeNode { 
     12    struct treeNode *leftPtr;  /* pointer to left subtree */
     13    int data; /* node value */
     14    struct treeNode *rightPtr; /* pointer to right subtree */
     15 }; /* end structure treeNode */
     16 
     17 typedef struct treeNode TreeNode; /* synonym for struct treeNode */
     18 typedef TreeNode *TreeNodePtr; /* synonym for TreeNode* */
     19 
     20 /* prototypes */
     21 void insertNode( TreeNodePtr *treePtr, int value );
     22 void inOrder( TreeNodePtr treePtr );
     23 void preOrder( TreeNodePtr treePtr );
     24 void postOrder( TreeNodePtr treePtr );
     25 int deleteNode( TreeNodePtr *treePtr, int value );
     26 
     27 /*
     28  * NOTE: this function returns the daddy of
     29  *       the node, not the node in itself.
     30 */
     31 TreeNodePtr searchTree( TreeNodePtr treePtr, int value );
     32 
     33 /* function main begins program execution */
     34 int main(void)
     35 { 
     36    int i; /* counter to loop from 1-10 */
     37    int item; /* variable to hold random values */
     38    TreeNodePtr rootPtr = NULL; /* tree initially empty */
     39 
     40    srand( time( NULL ) ); 
     41    printf( "The numbers being placed in the tree are:\n" );
     42 
     43    /* insert random values between 1 and 15 in the tree */
     44    for ( i = 1; i <= 10; i++ ) { 
     45       item = rand() % 15;
     46       printf( "%3d", item );
     47       insertNode( &rootPtr, item );
     48    } /* end for */
     49 
     50    printf("\n\nInsert the value to remove: ");
     51    scanf("%d", &item);
     52 
     53    if( deleteNode( &rootPtr, item ) ) {
     54       printf("Value not found or value is root: %d\n", item);
     55       return -1;
     56    }
     57 
     58    /* traverse the tree preOrder */
     59    printf( "\nThe preOrder traversal is:\n" );
     60    preOrder( rootPtr );
     61 
     62    /* traverse the tree inOrder */
     63    printf( "\n\nThe inOrder traversal is:\n" );
     64    inOrder( rootPtr );
     65 
     66    /* traverse the tree postOrder */
     67    printf( "\n\nThe postOrder traversal is:\n" );
     68    postOrder( rootPtr );
     69 
     70    putchar('\n');
     71 
     72    return 0; /* indicates successful termination */
     73 
     74 } /* end main */
     75 
     76 /* insert node into tree */
     77 void insertNode( TreeNodePtr *treePtr, int value )
     78 { 
     79    
     80    /* if tree is empty */
     81    if ( *treePtr == NULL ) {   
     82       *treePtr = malloc( sizeof( TreeNode ) );
     83 
     84       /* if memory was allocated then assign data */
     85       if ( *treePtr != NULL ) { 
     86          ( *treePtr )->data = value;
     87          ( *treePtr )->leftPtr = NULL;
     88          ( *treePtr )->rightPtr = NULL;
     89       } /* end if */
     90       else {
     91          printf( "%d not inserted. No memory available.\n", value );
     92       } /* end else */
     93 
     94    } /* end if */
     95    else { /* tree is not empty */
     96 
     97       /* data to insert is less than data in current node */
     98       if ( value <= ( *treePtr )->data ) {
     99          insertNode( &( ( *treePtr )->leftPtr ), value );
    100       } /* end if */
    101 
    102       /* data to insert is greater than data in current node */
    103       else if ( value > ( *treePtr )->data ) {
    104          insertNode( &( ( *treePtr )->rightPtr ), value );
    105       } /* end else if */
    106 
    107    } /* end else */
    108 
    109 } /* end function insertNode */
    110 
    111 /* begin inorder traversal of tree */
    112 void inOrder( TreeNodePtr treePtr )
    113 { 
    114 
    115    /* if tree is not empty then traverse */
    116    if ( treePtr != NULL ) { 
    117       inOrder( treePtr->leftPtr );
    118       printf( "%3d", treePtr->data );
    119       inOrder( treePtr->rightPtr );
    120    } /* end if */
    121 
    122 } /* end function inOrder */
    123 
    124 /* begin preorder traversal of tree */
    125 void preOrder( TreeNodePtr treePtr )
    126 { 
    127 
    128    /* if tree is not empty then traverse */
    129    if ( treePtr != NULL ) { 
    130       printf( "%3d", treePtr->data );
    131       preOrder( treePtr->leftPtr );
    132       preOrder( treePtr->rightPtr );
    133    } /* end if */
    134 
    135 } /* end function preOrder */
    136 
    137 /* begin postorder traversal of tree */
    138 void postOrder( TreeNodePtr treePtr )
    139 { 
    140 
    141    /* if tree is not empty then traverse */
    142    if ( treePtr != NULL ) { 
    143       postOrder( treePtr->leftPtr );
    144       postOrder( treePtr->rightPtr );
    145       printf( "%3d", treePtr->data );
    146    } /* end if */
    147 
    148 } /* end function postOrder */
    149 
    150 /* 
    151  * Delete a node from the tree
    152 */
    153 int deleteNode( TreeNodePtr *treePtr, int value )
    154 {
    155    TreeNodePtr rm_parentp = searchTree( *treePtr, value );
    156    TreeNodePtr *rm_childp;
    157    TreeNodePtr currentPtr;
    158 
    159    /* a simple check */
    160    if( rm_parentp == NULL || *treePtr == NULL )
    161       return 1;
    162 
    163    /* set the "parent" pointer */
    164    if( rm_parentp->leftPtr != NULL && rm_parentp->leftPtr->data == value )
    165       rm_childp = &rm_parentp->leftPtr;
    166    else
    167       rm_childp = &rm_parentp->rightPtr;
    168 
    169    /* remove a leaf node */
    170    if( ( *rm_childp )->leftPtr == NULL && ( *rm_childp )->rightPtr == NULL ) {
    171 
    172       *rm_childp = NULL;
    173       free( *rm_childp );
    174    }
    175    /* remove a one-child node: is this code unreadable? :| */ 
    176    else if(((*rm_childp)->leftPtr != NULL) ^ ((*rm_childp)->rightPtr != NULL)) {
    177 
    178       rm_parentp = *rm_childp;
    179 
    180       if( ( *rm_childp )->leftPtr != NULL )
    181          *rm_childp = ( *rm_childp )->leftPtr;
    182       else
    183          *rm_childp = ( *rm_childp )->rightPtr;
    184 
    185       free( rm_parentp );
    186    }
    187    /* remove a two-children node */
    188    else {
    189       currentPtr = ( *rm_childp )->leftPtr;
    190       while( currentPtr->rightPtr != NULL ) {
    191 	 currentPtr = currentPtr->rightPtr;
    192       }
    193 
    194       rm_parentp = *rm_childp; /* will be freed */
    195 
    196       currentPtr->rightPtr = ( *rm_childp )->rightPtr;
    197       ( *rm_childp )->rightPtr = NULL;
    198       *rm_childp = ( *rm_childp )->leftPtr;
    199 
    200       free( rm_parentp );
    201    }
    202 
    203    return 0;
    204 } /* eof deleteNode()*/
    205 
    206 /*
    207  * Find a node and returns its daddy 
    208 */
    209 TreeNodePtr searchTree( TreeNodePtr treePtr, int value )
    210 {  
    211    TreeNodePtr retp = treePtr;
    212 
    213    if( retp != NULL ) {
    214       if( (retp->leftPtr != NULL && retp->leftPtr->data == value) ||
    215 	  (retp->rightPtr != NULL && retp->rightPtr->data == value)
    216       ) return retp;
    217 
    218       if( retp->data > value )
    219 	 return searchTree( retp->leftPtr, value );
    220       else
    221 	 return searchTree( retp->rightPtr, value );
    222    }
    223  
    224    return NULL;
    225 
    226 } /* eof searchTree() */
    227