training

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

fig12_19_mod.c (3611B)

      1 /* Exercise 12.16 */
      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 
     26 /* function main begins program execution */
     27 int main(void)
     28 { 
     29    int i; /* counter to loop from 1-10 */
     30    int item; /* variable to hold random values */
     31    TreeNodePtr rootPtr = NULL; /* tree initially empty */
     32 
     33    srand( time( NULL ) ); 
     34    printf( "The numbers being placed in the tree are:\n" );
     35 
     36    /* insert random values between 1 and 15 in the tree */
     37    for ( i = 1; i <= 10; i++ ) { 
     38       item = rand() % 15;
     39       printf( "%3d", item );
     40       insertNode( &rootPtr, item );
     41    } /* end for */
     42 
     43    /* traverse the tree preOrder */
     44    printf( "\n\nThe preOrder traversal is:\n" );
     45    preOrder( rootPtr );
     46 
     47    /* traverse the tree inOrder */
     48    printf( "\n\nThe inOrder traversal is:\n" );
     49    inOrder( rootPtr );
     50 
     51    /* traverse the tree postOrder */
     52    printf( "\n\nThe postOrder traversal is:\n" );
     53    postOrder( rootPtr );
     54 
     55    putchar('\n');
     56 
     57    return 0; /* indicates successful termination */
     58 
     59 } /* end main */
     60 
     61 /* insert node into tree */
     62 void insertNode( TreeNodePtr *treePtr, int value )
     63 { 
     64    
     65    /* if tree is empty */
     66    if ( *treePtr == NULL ) {   
     67       *treePtr = malloc( sizeof( TreeNode ) );
     68 
     69       /* if memory was allocated then assign data */
     70       if ( *treePtr != NULL ) { 
     71          ( *treePtr )->data = value;
     72          ( *treePtr )->leftPtr = NULL;
     73          ( *treePtr )->rightPtr = NULL;
     74       } /* end if */
     75       else {
     76          printf( "%d not inserted. No memory available.\n", value );
     77       } /* end else */
     78 
     79    } /* end if */
     80    else { /* tree is not empty */
     81 
     82       /* data to insert is less than data in current node */
     83       if ( value <= ( *treePtr )->data ) {
     84          insertNode( &( ( *treePtr )->leftPtr ), value );
     85       } /* end if */
     86 
     87       /* data to insert is greater than data in current node */
     88       else if ( value > ( *treePtr )->data ) {
     89          insertNode( &( ( *treePtr )->rightPtr ), value );
     90       } /* end else if */
     91 
     92    } /* end else */
     93 
     94 } /* end function insertNode */
     95 
     96 /* begin inorder traversal of tree */
     97 void inOrder( TreeNodePtr treePtr )
     98 { 
     99 
    100    /* if tree is not empty then traverse */
    101    if ( treePtr != NULL ) { 
    102       inOrder( treePtr->leftPtr );
    103       printf( "%3d", treePtr->data );
    104       inOrder( treePtr->rightPtr );
    105    } /* end if */
    106 
    107 } /* end function inOrder */
    108 
    109 /* begin preorder traversal of tree */
    110 void preOrder( TreeNodePtr treePtr )
    111 { 
    112 
    113    /* if tree is not empty then traverse */
    114    if ( treePtr != NULL ) { 
    115       printf( "%3d", treePtr->data );
    116       preOrder( treePtr->leftPtr );
    117       preOrder( treePtr->rightPtr );
    118    } /* end if */
    119 
    120 } /* end function preOrder */
    121 
    122 /* begin postorder traversal of tree */
    123 void postOrder( TreeNodePtr treePtr )
    124 { 
    125 
    126    /* if tree is not empty then traverse */
    127    if ( treePtr != NULL ) { 
    128       postOrder( treePtr->leftPtr );
    129       postOrder( treePtr->rightPtr );
    130       printf( "%3d", treePtr->data );
    131    } /* end if */
    132 
    133 } /* end function postOrder */
    134