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