/* Fig. 12.19: fig12_19.c Create a binary tree and traverse it preorder, inorder
ID: 3712152 • Letter: #
Question
/* Fig. 12.19: fig12_19.c Create a binary tree and traverse it preorder, inorder, and postorder */ #include <stdio.h> #include <stdlib.h> #include <time.h>
/* self-referential structure */ struct treeNode { struct treeNode *leftPtr; /* pointer to left subtree */ int data; /* node value */ struct treeNode *rightPtr; /* pointer to right subtree */ }; /* end structure treeNode */
typedef struct treeNode TreeNode; /* synonym for struct treeNode */ typedef TreeNode *TreeNodePtr; /* synonym for TreeNode* */
/* prototypes */ void insertNode( TreeNodePtr *treePtr, int value ); void inOrder( TreeNodePtr treePtr ); void preOrder( TreeNodePtr treePtr ); void postOrder( TreeNodePtr treePtr );
/* function main begins program execution */ int main() { int i; /* counter to loop from 1-10 */ int item; /* variable to hold random values */ TreeNodePtr rootPtr = NULL; /* tree initially empty */
srand( time( NULL ) ); printf( "The numbers being placed in the tree are: " );
/* insert random values between 1 and 15 in the tree */ for ( i = 1; i <= 10; i++ ) { item = rand() % 15; printf( "%3d", item ); insertNode( &rootPtr, item ); } /* end for */
/* traverse the tree preOrder */ printf( " The preOrder traversal is: " ); preOrder( rootPtr );
/* traverse the tree inOrder */ printf( " The inOrder traversal is: " ); inOrder( rootPtr );
/* traverse the tree postOrder */ printf( " The postOrder traversal is: " ); postOrder( rootPtr );
return 0; /* indicates successful termination */
} /* end main */
/* insert node into tree */ void insertNode( TreeNodePtr *treePtr, int value ) { /* if tree is empty */ if ( *treePtr == NULL ) { *treePtr = malloc( sizeof( TreeNode ) );
/* if memory was allocated then assign data */ if ( *treePtr != NULL ) { ( *treePtr )->data = value; ( *treePtr )->leftPtr = NULL; ( *treePtr )->rightPtr = NULL; } /* end if */ else { printf( "%d not inserted. No memory available. ", value ); } /* end else */
} /* end if */ else { /* tree is not empty */
/* data to insert is less than data in current node */ if ( value < ( *treePtr )->data ) { insertNode( &( ( *treePtr )->leftPtr ), value ); } /* end if */
/* data to insert is greater than data in current node */ else if ( value > ( *treePtr )->data ) { insertNode( &( ( *treePtr )->rightPtr ), value ); } /* end else if */ else { /* duplicate data value ignored */ printf( "dup" ); } /* end else */
} /* end else */
} /* end function insertNode */
/* begin inorder traversal of tree */ void inOrder( TreeNodePtr treePtr ) {
/* if tree is not empty then traverse */ if ( treePtr != NULL ) { inOrder( treePtr->leftPtr ); printf( "%3d", treePtr->data ); inOrder( treePtr->rightPtr ); } /* end if */
} /* end function inOrder */
/* begin preorder traversal of tree */ void preOrder( TreeNodePtr treePtr ) {
/* if tree is not empty then traverse */ if ( treePtr != NULL ) { printf( "%3d", treePtr->data ); preOrder( treePtr->leftPtr ); preOrder( treePtr->rightPtr ); } /* end if */
} /* end function preOrder */
/* begin postorder traversal of tree */ void postOrder( TreeNodePtr treePtr ) {
/* if tree is not empty then traverse */ if ( treePtr != NULL ) { postOrder( treePtr->leftPtr ); postOrder( treePtr->rightPtr ); printf( "%3d", treePtr->data ); } /* end if */
} /* end function /* Fig. 12.19: fig12_19.c Create a binary tree and traverse it preorder, inorder, and postorder */ #include <stdio.h> #include <stdlib.h> #include <time.h>
/* self-referential structure */ struct treeNode { struct treeNode *leftPtr; /* pointer to left subtree */ int data; /* node value */ struct treeNode *rightPtr; /* pointer to right subtree */ }; /* end structure treeNode */
typedef struct treeNode TreeNode; /* synonym for struct treeNode */ typedef TreeNode *TreeNodePtr; /* synonym for TreeNode* */
/* prototypes */ void insertNode( TreeNodePtr *treePtr, int value ); void inOrder( TreeNodePtr treePtr ); void preOrder( TreeNodePtr treePtr ); void postOrder( TreeNodePtr treePtr );
/* function main begins program execution */ int main() { int i; /* counter to loop from 1-10 */ int item; /* variable to hold random values */ TreeNodePtr rootPtr = NULL; /* tree initially empty */
srand( time( NULL ) ); printf( "The numbers being placed in the tree are: " );
/* insert random values between 1 and 15 in the tree */ for ( i = 1; i <= 10; i++ ) { item = rand() % 15; printf( "%3d", item ); insertNode( &rootPtr, item ); } /* end for */
/* traverse the tree preOrder */ printf( " The preOrder traversal is: " ); preOrder( rootPtr );
/* traverse the tree inOrder */ printf( " The inOrder traversal is: " ); inOrder( rootPtr );
/* traverse the tree postOrder */ printf( " The postOrder traversal is: " ); postOrder( rootPtr );
return 0; /* indicates successful termination */
} /* end main */
/* insert node into tree */ void insertNode( TreeNodePtr *treePtr, int value ) { /* if tree is empty */ if ( *treePtr == NULL ) { *treePtr = malloc( sizeof( TreeNode ) );
/* if memory was allocated then assign data */ if ( *treePtr != NULL ) { ( *treePtr )->data = value; ( *treePtr )->leftPtr = NULL; ( *treePtr )->rightPtr = NULL; } /* end if */ else { printf( "%d not inserted. No memory available. ", value ); } /* end else */
} /* end if */ else { /* tree is not empty */
/* data to insert is less than data in current node */ if ( value < ( *treePtr )->data ) { insertNode( &( ( *treePtr )->leftPtr ), value ); } /* end if */
/* data to insert is greater than data in current node */ else if ( value > ( *treePtr )->data ) { insertNode( &( ( *treePtr )->rightPtr ), value ); } /* end else if */ else { /* duplicate data value ignored */ printf( "dup" ); } /* end else */
} /* end else */
} /* end function insertNode */
/* begin inorder traversal of tree */ void inOrder( TreeNodePtr treePtr ) {
/* if tree is not empty then traverse */ if ( treePtr != NULL ) { inOrder( treePtr->leftPtr ); printf( "%3d", treePtr->data ); inOrder( treePtr->rightPtr ); } /* end if */
} /* end function inOrder */
/* begin preorder traversal of tree */ void preOrder( TreeNodePtr treePtr ) {
/* if tree is not empty then traverse */ if ( treePtr != NULL ) { printf( "%3d", treePtr->data ); preOrder( treePtr->leftPtr ); preOrder( treePtr->rightPtr ); } /* end if */
} /* end function preOrder */
/* begin postorder traversal of tree */ void postOrder( TreeNodePtr treePtr ) {
/* if tree is not empty then traverse */ if ( treePtr != NULL ) { postOrder( treePtr->leftPtr ); postOrder( treePtr->rightPtr ); printf( "%3d", treePtr->data ); } /* end if */
} /* end function
-----
/* Fig. 12.13: fig12_13.c Operating and maintaining a queue */
#include <stdio.h> #include <stdlib.h>
/* self-referential structure */ struct queueNode { char data; /* define data as a char */ struct queueNode *nextPtr; /* queueNode pointer */ }; /* end structure queueNode */
typedef struct queueNode QueueNode; typedef QueueNode *QueueNodePtr;
/* function prototypes */ void printQueue( QueueNodePtr currentPtr ); int isEmpty( QueueNodePtr headPtr ); char dequeue( QueueNodePtr *headPtr, QueueNodePtr *tailPtr ); void enqueue( QueueNodePtr *headPtr, QueueNodePtr *tailPtr, char value ); void instructions( void );
/* function main begins program execution */ int main() { QueueNodePtr headPtr = NULL; /* initialize headPtr */ QueueNodePtr tailPtr = NULL; /* initialize tailPtr */ int choice; /* user's menu choice */ char item; /* char input by user */
instructions(); /* display the menu */ printf( "? " ); scanf( "%d", &choice );
/* while user does not enter 3 */ while ( choice != 3 ) {
switch( choice ) {
/* enqueue value */ case 1: printf( "Enter a character: " ); scanf( " %c", &item ); enqueue( &headPtr, &tailPtr, item ); printQueue( headPtr ); break;
/* dequeue value */ case 2:
/* if queue is not empty */ if ( !isEmpty( headPtr ) ) { item = dequeue( &headPtr, &tailPtr ); printf( "%c has been dequeued. ", item ); } /* end if */
printQueue( headPtr ); break;
default: printf( "Invalid choice. " ); instructions(); break;
} /* end switch */
printf( "? " ); scanf( "%d", &choice ); } /* end while */
printf( "End of run. " ); return 0; /* indicates successful termination */
} /* end main */
/* display program instructions to user */ void instructions( void ) { printf ( "Enter your choice: " " 1 to add an item to the queue " " 2 to remove an item from the queue " " 3 to end " ); } /* end function instructions */
/* insert a node a queue tail */ void enqueue( QueueNodePtr *headPtr, QueueNodePtr *tailPtr, char value ) { QueueNodePtr newPtr; /* pointer to new node */
newPtr = malloc( sizeof( QueueNode ) );
if ( newPtr != NULL ) { /* is space available */ newPtr->data = value; newPtr->nextPtr = NULL;
/* if empty, insert node at head */ if ( isEmpty( *headPtr ) ) { *headPtr = newPtr; } /* end if */ else { ( *tailPtr )->nextPtr = newPtr; } /* end else */
*tailPtr = newPtr; } /* end if */ else { printf( "%c not inserted. No memory available. ", value ); } /* end else */
} /* end function enqueue */
/* remove node from queue head */ char dequeue( QueueNodePtr *headPtr, QueueNodePtr *tailPtr ) { char value; /* node value */ QueueNodePtr tempPtr; /* temporary node pointer */
value = ( *headPtr )->data; tempPtr = *headPtr; *headPtr = ( *headPtr )->nextPtr;
/* if queue is empty */ if ( *headPtr == NULL ) { *tailPtr = NULL; } /* end if */
free( tempPtr );
return value;
} /* end function dequeue */
/* Return 1 if the list is empty, 0 otherwise */ int isEmpty( QueueNodePtr headPtr ) { return headPtr == NULL;
} /* end function isEmpty */
/* Print the queue */ void printQueue( QueueNodePtr currentPtr ) {
/* if queue is empty */ if ( currentPtr == NULL ) { printf( "Queue is empty. " ); } /* end if */ else { printf( "The queue is: " );
/* while not end of queue */ while ( currentPtr != NULL ) { printf( "%c --> ", currentPtr->data ); currentPtr = currentPtr->nextPtr; } /* end while */
printf( "NULL " ); } /* end else */
} /* /* Fig. 12.13: fig12_13.c Operating and maintaining a queue */
#include <stdio.h> #include <stdlib.h>
/* self-referential structure */ struct queueNode { char data; /* define data as a char */ struct queueNode *nextPtr; /* queueNode pointer */ }; /* end structure queueNode */
typedef struct queueNode QueueNode; typedef QueueNode *QueueNodePtr;
/* function prototypes */ void printQueue( QueueNodePtr currentPtr ); int isEmpty( QueueNodePtr headPtr ); char dequeue( QueueNodePtr *headPtr, QueueNodePtr *tailPtr ); void enqueue( QueueNodePtr *headPtr, QueueNodePtr *tailPtr, char value ); void instructions( void );
/* function main begins program execution */ int main() { QueueNodePtr headPtr = NULL; /* initialize headPtr */ QueueNodePtr tailPtr = NULL; /* initialize tailPtr */ int choice; /* user's menu choice */ char item; /* char input by user */
instructions(); /* display the menu */ printf( "? " ); scanf( "%d", &choice );
/* while user does not enter 3 */ while ( choice != 3 ) {
switch( choice ) {
/* enqueue value */ case 1: printf( "Enter a character: " ); scanf( " %c", &item ); enqueue( &headPtr, &tailPtr, item ); printQueue( headPtr ); break;
/* dequeue value */ case 2:
/* if queue is not empty */ if ( !isEmpty( headPtr ) ) { item = dequeue( &headPtr, &tailPtr ); printf( "%c has been dequeued. ", item ); } /* end if */
printQueue( headPtr ); break;
default: printf( "Invalid choice. " ); instructions(); break;
} /* end switch */
printf( "? " ); scanf( "%d", &choice ); } /* end while */
printf( "End of run. " ); return 0; /* indicates successful termination */
} /* end main */
/* display program instructions to user */ void instructions( void ) { printf ( "Enter your choice: " " 1 to add an item to the queue " " 2 to remove an item from the queue " " 3 to end " ); } /* end function instructions */
/* insert a node a queue tail */ void enqueue( QueueNodePtr *headPtr, QueueNodePtr *tailPtr, char value ) { QueueNodePtr newPtr; /* pointer to new node */
newPtr = malloc( sizeof( QueueNode ) );
if ( newPtr != NULL ) { /* is space available */ newPtr->data = value; newPtr->nextPtr = NULL;
/* if empty, insert node at head */ if ( isEmpty( *headPtr ) ) { *headPtr = newPtr; } /* end if */ else { ( *tailPtr )->nextPtr = newPtr; } /* end else */
*tailPtr = newPtr; } /* end if */ else { printf( "%c not inserted. No memory available. ", value ); } /* end else */
} /* end function enqueue */
/* remove node from queue head */ char dequeue( QueueNodePtr *headPtr, QueueNodePtr *tailPtr ) { char value; /* node value */ QueueNodePtr tempPtr; /* temporary node pointer */
value = ( *headPtr )->data; tempPtr = *headPtr; *headPtr = ( *headPtr )->nextPtr;
/* if queue is empty */ if ( *headPtr == NULL ) { *tailPtr = NULL; } /* end if */
free( tempPtr );
return value;
} /* end function dequeue */
/* Return 1 if the list is empty, 0 otherwise */ int isEmpty( QueueNodePtr headPtr ) { return headPtr == NULL;
} /* end function isEmpty */
/* Print the queue */ void printQueue( QueueNodePtr currentPtr ) {
/* if queue is empty */ if ( currentPtr == NULL ) { printf( "Queue is empty. " ); } /* end if */ else { printf( "The queue is: " );
/* while not end of queue */ while ( currentPtr != NULL ) { printf( "%c --> ", currentPtr->data ); currentPtr = currentPtr->nextPtr; } /* end while */
printf( "NULL " ); } /* end else */
} /*
Explanation / Answer
/* Fig. 12.24: fig12_19.c + fig 12.13.c + levelorder Traversal
Create a binary tree and traverse it
preorder, inorder, postorder and levelorder*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* self-referential structure */
struct treeNode {
struct treeNode *leftPtr; /* pointer to left subtree */
int data; /* node value */
struct treeNode *rightPtr; /* pointer to right subtree */
}; /* end structure treeNode */
typedef struct treeNode TreeNode; /* synonym for struct treeNode */
typedef TreeNode *TreeNodePtr; /* synonym for TreeNode* */
/* prototypes */
void insertNode( TreeNodePtr *treePtr, int value );
void inOrder( TreeNodePtr treePtr );
void preOrder( TreeNodePtr treePtr );
void postOrder( TreeNodePtr treePtr );
void levelOrder( TreeNodePtr treePtr );
/* QUEUE self-referential structure */
struct queueNode {
struct treeNode *ptr; /* define data as struct treeNode * */
struct queueNode *nextPtr; /* queueNode pointer */
}; /* end structure queueNode */
typedef struct queueNode QueueNode;
typedef QueueNode *QueueNodePtr;
/* function prototypes */
void printQueue( QueueNodePtr currentPtr );
int isEmpty( QueueNodePtr headPtr );
struct treeNode * dequeue( QueueNodePtr *headPtr, QueueNodePtr *tailPtr );
void enqueue( QueueNodePtr *headPtr, QueueNodePtr *tailPtr,
struct treeNode * value );
/* function main begins program execution */
int main()
{
int i; /* counter to loop from 1-10 */
int item; /* variable to hold random values */
TreeNodePtr rootPtr = NULL; /* tree initially empty */
srand( time( NULL ) );
printf( "The numbers being placed in the tree are: " );
/* insert random values between 1 and 15 in the tree */
for ( i = 1; i <= 10; i++ ) {
item = rand() % 15;
printf( "%3d", item );
insertNode( &rootPtr, item );
} /* end for */
/* traverse the tree preOrder */
printf( " The preOrder traversal is: " );
preOrder( rootPtr );
/* traverse the tree inOrder */
printf( " The inOrder traversal is: " );
inOrder( rootPtr );
/* traverse the tree postOrder */
printf( " The postOrder traversal is: " );
postOrder( rootPtr );
/* traverse the tree levelOrder */
printf( " The levelOrder traversal is: " );
levelOrder( rootPtr );
return 0; /* indicates successful termination */
} /* end main */
/* insert node into tree */
void insertNode( TreeNodePtr *treePtr, int value )
{
/* if tree is empty */
if ( *treePtr == NULL ) {
*treePtr = malloc( sizeof( TreeNode ) );
/* if memory was allocated then assign data */
if ( *treePtr != NULL ) {
( *treePtr )->data = value;
( *treePtr )->leftPtr = NULL;
( *treePtr )->rightPtr = NULL;
} /* end if */
else {
printf( "%d not inserted. No memory available. ", value );
} /* end else */
} /* end if */
else { /* tree is not empty */
/* data to insert is less than data in current node */
if ( value < ( *treePtr )->data ) {
insertNode( &( ( *treePtr )->leftPtr ), value );
} /* end if */
/* data to insert is greater than data in current node */
else if ( value > ( *treePtr )->data ) {
insertNode( &( ( *treePtr )->rightPtr ), value );
} /* end else if */
else { /* duplicate data value ignored */
printf( "dup" );
} /* end else */
} /* end else */
} /* end function insertNode */
/* begin inorder traversal of tree */
void inOrder( TreeNodePtr treePtr )
{
/* if tree is not empty then traverse */
if ( treePtr != NULL ) {
inOrder( treePtr->leftPtr );
printf( "%3d", treePtr->data );
inOrder( treePtr->rightPtr );
} /* end if */
} /* end function inOrder */
/* begin preorder traversal of tree */
void preOrder( TreeNodePtr treePtr )
{
/* if tree is not empty then traverse */
if ( treePtr != NULL ) {
printf( "%3d", treePtr->data );
preOrder( treePtr->leftPtr );
preOrder( treePtr->rightPtr );
} /* end if */
} /* end function preOrder */
/* begin postorder traversal of tree */
void postOrder( TreeNodePtr treePtr )
{
/* if tree is not empty then traverse */
if ( treePtr != NULL ) {
postOrder( treePtr->leftPtr );
postOrder( treePtr->rightPtr );
printf( "%3d", treePtr->data );
} /* end if */
}
/* begin inorder traversal of tree */
void levelOrder( TreeNodePtr treePtr )
{
QueueNodePtr headPtr = NULL; /* initialize headPtr */
QueueNodePtr tailPtr = NULL; /* initialize tailPtr */
enqueue(&headPtr, &tailPtr, treePtr);
while( isEmpty( headPtr ) == 0 ) {
TreeNodePtr nodePtr = dequeue( &headPtr, &tailPtr );
printf( "%3d", nodePtr->data);
if ( nodePtr->leftPtr )
enqueue( &headPtr, &tailPtr, nodePtr->leftPtr );
if ( nodePtr->rightPtr )
enqueue( &headPtr, &tailPtr, nodePtr->rightPtr );
}
printf(" ");
}
/* insert a node a queue tail */
void enqueue( QueueNodePtr *headPtr, QueueNodePtr *tailPtr,
struct treeNode * value )
{
QueueNodePtr newPtr; /* pointer to new node */
newPtr = malloc( sizeof( QueueNode ) );
if ( newPtr != NULL ) { /* is space available */
newPtr->ptr = value;
newPtr->nextPtr = NULL;
/* if empty, insert node at head */
if ( isEmpty( *headPtr ) ) {
*headPtr = newPtr;
} /* end if */
else {
( *tailPtr )->nextPtr = newPtr;
} /* end else */
*tailPtr = newPtr;
} /* end if */
else {
printf( "%c not inserted. No memory available. ", value );
} /* end else */
} /* end function enqueue */
/* remove node from queue head */
struct treeNode * dequeue( QueueNodePtr *headPtr, QueueNodePtr *tailPtr )
{
struct treeNode * value; /* node value */
QueueNodePtr tempPtr; /* temporary node pointer */
value = ( *headPtr )->ptr;
tempPtr = *headPtr;
*headPtr = ( *headPtr )->nextPtr;
/* if queue is empty */
if ( *headPtr == NULL ) {
*tailPtr = NULL;
} /* end if */
free( tempPtr );
return value;
} /* end function dequeue */
/* Return 1 if the list is empty, 0 otherwise */
int isEmpty( QueueNodePtr headPtr )
{
return headPtr == NULL;
} /* end function isEmpty */
/* Print the queue */
void printQueue( QueueNodePtr currentPtr )
{
/* if queue is empty */
if ( currentPtr == NULL ) {
printf( "Queue is empty. " );
} /* end if */
else {
printf( "The queue is: " );
/* while not end of queue */
while ( currentPtr != NULL ) {
printf( "%p (%d)--> ", currentPtr->ptr, *(currentPtr->ptr) );
currentPtr = currentPtr->nextPtr;
} /* end while */
printf( "NULL " );
} /* end else */
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.