training

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

fig12_19_mod2.c (3574B)

      1 /* Exercise 12.17 */
      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 <string.h>
      9 
     10 #define SIZE 100
     11 
     12 /* self-referential structure */
     13 struct treeNode { 
     14    struct treeNode *leftPtr;  /* pointer to left subtree */
     15    char data[SIZE]; /* node value */
     16    struct treeNode *rightPtr; /* pointer to right subtree */
     17 }; /* end structure treeNode */
     18 
     19 typedef struct treeNode TreeNode; /* synonym for struct treeNode */
     20 typedef TreeNode *TreeNodePtr; /* synonym for TreeNode* */
     21 
     22 /* prototypes */
     23 void insertNode( TreeNodePtr *treePtr, char *string );
     24 void inOrder( TreeNodePtr treePtr );
     25 void preOrder( TreeNodePtr treePtr );
     26 void postOrder( TreeNodePtr treePtr );
     27 
     28 /* function main begins program execution */
     29 int main(void)
     30 { 
     31    TreeNodePtr rootPtr = NULL; /* tree initially empty */
     32    char string[SIZE], *tokp;
     33 
     34    printf("Insert a phrase: ");
     35    fgets(string, SIZE, stdin);
     36    printf( "The current string being placed in the tree are:\n" );
     37    printf("%s\n", string);
     38 
     39    tokp = strtok(string, " ");
     40    while( tokp != NULL ) {
     41       insertNode( &rootPtr, tokp );
     42       tokp = strtok(NULL, " ");
     43    }
     44 
     45    /* traverse the tree preOrder */
     46    printf( "\nThe preOrder traversal is:\n" );
     47    preOrder( rootPtr );
     48 
     49    /* traverse the tree inOrder */
     50    printf( "\n\nThe inOrder traversal is:\n" );
     51    inOrder( rootPtr );
     52 
     53    /* traverse the tree postOrder */
     54    printf( "\n\nThe postOrder traversal is:\n" );
     55    postOrder( rootPtr );
     56 
     57    putchar('\n');
     58 
     59    return 0; /* indicates successful termination */
     60 
     61 } /* end main */
     62 
     63 /* insert node into tree */
     64 void insertNode( TreeNodePtr *treePtr, char *string )
     65 { 
     66    
     67    /* if tree is empty */
     68    if ( *treePtr == NULL ) {   
     69       *treePtr = malloc( sizeof( TreeNode ) );
     70 
     71       /* if memory was allocated then assign data */
     72       if ( *treePtr != NULL ) { 
     73 	 strncpy( ( *treePtr )->data, string, SIZE );
     74          ( *treePtr )->leftPtr = NULL;
     75          ( *treePtr )->rightPtr = NULL;
     76       } /* end if */
     77       else {
     78          printf( "%s not inserted. No memory available.\n", string );
     79       } /* end else */
     80 
     81    } /* end if */
     82    else { /* tree is not empty */
     83 
     84       /* data to insert is less than data in current node */
     85       if ( memcmp(string, ( *treePtr )->data, SIZE) <= 0 ) {
     86          insertNode( &( ( *treePtr )->leftPtr ), string );
     87       } /* end if */
     88 
     89       /* data to insert is greater than data in current node */
     90       else {
     91          insertNode( &( ( *treePtr )->rightPtr ), string );
     92       } /* end else if */
     93 
     94    } /* end else */
     95 
     96 } /* end function insertNode */
     97 
     98 /* begin inorder traversal of tree */
     99 void inOrder( TreeNodePtr treePtr )
    100 { 
    101 
    102    /* if tree is not empty then traverse */
    103    if ( treePtr != NULL ) { 
    104       inOrder( treePtr->leftPtr );
    105       printf( "%s ", treePtr->data );
    106       inOrder( treePtr->rightPtr );
    107    } /* end if */
    108 
    109 } /* end function inOrder */
    110 
    111 /* begin preorder traversal of tree */
    112 void preOrder( TreeNodePtr treePtr )
    113 { 
    114 
    115    /* if tree is not empty then traverse */
    116    if ( treePtr != NULL ) { 
    117       printf( "%s ", treePtr->data );
    118       preOrder( treePtr->leftPtr );
    119       preOrder( treePtr->rightPtr );
    120    } /* end if */
    121 
    122 } /* end function preOrder */
    123 
    124 /* begin postorder traversal of tree */
    125 void postOrder( TreeNodePtr treePtr )
    126 { 
    127 
    128    /* if tree is not empty then traverse */
    129    if ( treePtr != NULL ) { 
    130       postOrder( treePtr->leftPtr );
    131       postOrder( treePtr->rightPtr );
    132       printf( "%s ", treePtr->data );
    133    } /* end if */
    134 
    135 } /* end function postOrder */
    136