[MattWill]

I have been trying to follow some example to get a binary tree to print the left and right child of a number that the user inputs at search. I really am starting to confuse myself because of information overload. Can anyone take some time to go over my code to make sure I am going in the right way?

for tree.h:

#include <stdio.h> 
#include <stdlib.h>


/************************/
/* tree.h for Project 4*/
/**********************/


#define kFileName "../../Data.txt"


/************************/
/* TreeNode  structure */
/**********************/

typedef struct TreeNode TreeNode;
typedef TreeNode *TreeNodePtr;
struct TreeNode {
		struct TreeNode *leftPtr; 
		int value;
		struct TreeNode *rightPtr;
	}; 

/************************/
/* function prototypes */
/**********************/

void	InsertInTree( TreeNodePtr *treePtr, int value );
TreeNodePtr SearchTree( TreeNodePtr treePtr, const int key );
void	BuildTree( void );
int		GetNumberFromFile( int *numPtr, FILE *fp );
void	DeleteTree(TreeNodePtr treePtr);

for tree.c:

#include <stdio.h> 
#include <stdlib.h>
#include "tree.h"

/*****************************************/
/*InsertInTree- Directs the numbers     */
/* on where they are placed in the tree*/
/**************************************/
void InsertInTree( TreeNodePtr *treePtr, int value )
{
	/* if treePtr is NULL */ 
	if ( *treePtr == NULL ) { 

		/* dynamically allocate memory */ 
		*treePtr = malloc( sizeof( TreeNode ) ); 

		/* if memory was allocated, insert node */
		if ( *treePtr != NULL ) {
			( *treePtr )->value = value;
			( *treePtr )->leftPtr = NULL; 
			( *treePtr )->rightPtr = NULL; 
		}/*endif*/ 
	else { 
		printf("ERROR: Could not allocate memory!\n" );
		return; //I ADDED THIS
	}/*end else*/ 
 
	}/*endif*/ 
	else { /* recursively call InsertInTree */ 

			/* insert node in left subtree */ 
			if (value<( *treePtr )->value ) { 
				InsertInTree( &( ( *treePtr )->leftPtr ), value );
			}/*endif*/ 
			else { /* insert node in right subtree */ 
	
 				if (value>( *treePtr )->value ) {
					InsertInTree( &(( *treePtr )->rightPtr ), value );
				}
				else { /* duplicate value */
			printf( "Duplicate Found" );
				}/*endelse*/ 
 
			}/*endelse*/ 
	} /* end else */
 
} /* end function InsertInTree */

/********************************************/
/*BuildTree- Helper Function to read the   */
/* Data.txt file and print those on screen*/
/*****************************************/
void    BuildTree( void )
{
    int     num;
    FILE    *fp;

    if ( ( fp = fopen( "kFileName", "r" ) ) == NULL )
        printf( "Could not read numbers file!\n" );

    printf( "The numbers being placed in the tree are:\n" );

    while ( GetNumberFromFile( &num, fp ) )
    {
        printf( "%3d ", num );
        InsertInTree( &rootPtr, num );
	    }

	    fclose( fp );
	}
/*********************************************/
/*GetNumberFromFile- Specific function to  */
/* read the numbers from Data.txt         */
/*****************************************/	
int GetNumberFromFile( int *numPtr, FILE *fp )
	{
		    if ( fscanf( fp, "%d\n", numPtr ) == EOF )
		        return false;
		    else
		        return true;
		}
/*********************************************/
/*Search- Helper function to SearchTree    */
/*****************************************/		
void Search(TreeNodePtr treePtr) {
		        int searchKey;
		    printf("Enter number to be searched: ");
		    scanf( "%d", &searchKey );
		        searchResultPtr = SearchTree( rootPtr, searchKey );
		}
/********************************************/
/*SearchTree- Searches tree in a preorder  */
/*traversal and stores required values    */
/*****************************************/
TreeNodePtr SearchTree( TreeNodePtr treePtr, const int key )
{
	/* traverse the tree inOrder */
	if ( treePtr == NULL ) {
		return NULL; /* key not found */
	} /* end if */
	else if ( treePtr->value == key ) {
		return treePtr; /* key found */
	} /* end else if */
	else if ( key < treePtr->value ) {
		SearchTree( treePtr->leftPtr, key ); /* search left */
	} /* end else if */
	else if ( key > treePtr->value ) {
		SearchTree( treePtr->rightPtr, key ); /* search right */
	} 	/* end else if */
} 	/* end function SearchTree */

/**********************************************/
/*DeleteTree- Destroy's the tree after search*/
/********************************************/
void DeleteTree (TreeNodePtr treePtr)
{	 if(treePtr!=NULL)

	{ 
		DeleteTree(treePtr->left);
		DeleteTree(treePtr->right);
		free(treePtr);

	}
	
}

for main.c:

#include <stdio.h> 
#include <stdlib.h>
#include "tree.h"

/************************/
/*    Main Function    */
/**********************/

int main()
{
	int num;	/* random value to insert in tree */
	int searchKey;	/* value to search for */
	TreeNodePtr rootPtr = NULL; /* points to the tree root */
	TreeNodePtr searchResultPtr; /* pointer to search result */
	
	BuildTree();
	
	Search(TreeNodePtr treePtr) //maybe rootPtr ?

	DeleteTree (TreeNodePtr treePtr)
	
	return;
	
}

Thanks for any help anyone might be able to provide.

[Salem_c]

> SearchTree( treePtr->leftPtr, key ); /* search left */
And what result is going to come back from the callee?

And what result is going to go back to the caller?

[MattWill]

Salem, I believe it actually won't return the actual key but only traverse it. How would one implement a call to print the actual value?

[Salem_c]

> return treePtr;
How does this get back to the caller, through several recursive calls?

> Search(TreeNodePtr treePtr) //maybe rootPtr ?
Yes, call it with the root.
AND assign the return result to something so you can USE it.

[MattWill]

Salem, thanks for helping me. I am starting to see it. However, I am able to execute y program but as soon as I insert my number it tells me that the value isn't found even though I know the number is in the tree. Also, I have reworked my code since this morning. And instead of breaking it up into three files I just consolidated to one so you or anyone else can just see it as a whole. Thanks again!

#include <stdbool.h>
#include <stdio.h> 
#include <stdlib.h> 

 
 /* TreeNode structure definition */ 
 struct TreeNode { 
	int data;
	struct TreeNode *leftPtr; /* pointer to left subtree */ 
	struct TreeNode *rightPtr; /* pointer to right subtree */ 
 }; /* end struct TreeNode */ 
 
 typedef struct TreeNode TreeNode;
 typedef TreeNode *TreeNodePtr; 
 
/* function prototypes */ 
void    BuildTree( void );
void insertInTree( TreeNodePtr *treePtr, int value ); 
int GetNumberFromFile( int *numPtr, FILE *fp );
TreeNodePtr binaryTreeSearch( TreeNodePtr treePtr, const int key );
void    PrintChild( TreeNodePtr searchResultPtr );

int main() 
{ 
int i;	/* loop counter */ 
int item;	/* random value to insert in tree */ 
int searchKey;	/* value to search for */ 

TreeNodePtr rootPtr = NULL; /* points to the tree root */ 
TreeNodePtr searchResultPtr; /* pointer to search result */ 

FILE    *fp;

   if ( ( fp = fopen( "Data.txt", "r" ) ) == NULL )
       printf( "Could not read numbers file!\n" );

 printf( "The numbers being placed in the tree are:\n" );

    while ( GetNumberFromFile( &item, fp ) )
    {
        printf( "%3d ", item );
        insertInTree( &rootPtr, item );
	    }

	 fclose( fp );
/* prompt user and read integer search key */ 
printf( "\n\nEnter an integer to search for: " ); 
scanf( "%d", &searchKey ); 

searchResultPtr = binaryTreeSearch( rootPtr, searchKey ); 

/* if searchKey not found */ 
	if ( searchResultPtr == NULL ) { 
	printf( "\n%d was not found in the tree.\n\n", searchKey ); 
	} /* end if */ 
	else{ /* if key found */ 
			printf( "\n%d was found in the tree.\n\n", searchResultPtr->data );
			printf("With left child: ");
			printChild(searchResultPtr->leftPtr);
			printf("With right child: ");
			printChild(searchResultPtr->rightPtr);

	} /* end else */ 
		return 0; /* indicate successful termination */ 
}/*endmain*/

void    PrintChild( TreeNodePtr searchResultPtr ) {
    printf( "%d ", searchResultPtr );
}
/*********************************************/
/*GetNumberFromFile- Specific function to  */
/* read the numbers from Data.txt         */
/*****************************************/	

int GetNumberFromFile( int *numPtr, FILE *fp )
	{
		    if ( fscanf( fp, "%d\n", numPtr ) == EOF )
		        return false;
		    else
		        return true;
	}

/*****************************/
/* insert numbers into treec*/ 
/***************************/
void insertInTree( TreeNodePtr *treePtr, int value ) 
{
	if ( *treePtr == NULL ) {
/* dynamically allocate memory */ 
*treePtr = malloc( sizeof( TreeNode ) ); 
			/* if memory was allocated, insert node */ 
		if ( *treePtr != NULL ) { 
		( *treePtr )->data = value; 
		( *treePtr )->leftPtr = NULL; 
		( *treePtr )->rightPtr = NULL; 
	}
		else { 
			printf( "%d not inserted. No memory available.\n", value ); 
	
		}
	 
	}
		else { /* recursively call insertInTree */ 
			
			if (value<( *treePtr )->data ) { 
				insertInTree( &( ( *treePtr )->leftPtr ), value ); 
			} 
			else { 
				/* insert node in right subtree */ 
				if (value>( *treePtr )->data ) { 
					insertInTree( &(( *treePtr )->rightPtr ), value ); 
				} 
			}  
		}
} 
/***************************/
/* search for key in tree */ 
/***************************/
TreeNodePtr binaryTreeSearch( TreeNodePtr treePtr, const int key )
{
	 
if ( treePtr == NULL ) {
	return NULL; /* key not found */ 
	}
		else if ( treePtr->data == key ) { 
			return treePtr; /* key found */ 
		}
			else if ( key < treePtr->data ) { 
				binaryTreeSearch( treePtr->leftPtr, key ); /* search left */	
			}
				else if ( key > treePtr->data ) { 
					binaryTreeSearch( treePtr->rightPtr, key ); /* search right */
				} 
} 

[jimblumberg]

When I compiled the above code these are the warning/error messages.

Quote

main.c||In function ‘main’:|
main.c|25|warning: unused variable ‘i’|
main.c||In function ‘PrintChild’:|
main.c|68|warning: format ‘%d’ expects type ‘int’, but argument 2 has type ‘TreeNodePtr’|
main.c||In function ‘binaryTreeSearch’:|
main.c|134|warning: control reaches end of non-void function|
||=== Build finished: 0 errors, 3 warnings ===|

Can you post the numbers input file?

Jim

[MattWill]

Hey Jim, thanks for your reply. I should note that I just had inserted the printChild function because my goal is to print the child nodes of the value being searched for and if the value is not found then print something like "Value Not Found." As for Data.txt, it is just a bunch of random integers. Currently I have the following in Data.txt:

2
4
3
10
5
11
1
29
15

Before I did add the printChild function the following was from gdb:

Enter an integer to search for: 10

10 was not found in the tree.


Program exited normally.

But 10 was in my list of integers so it should of been found. Argh!

[jimblumberg]

Quote

main.c||In function ‘binaryTreeSearch’:|
main.c|134|warning: control reaches end of non-void function

What about this warning? Shouldn't it be returning something?

Jim

[MattWill]

I am guessing I should include a return for the left and rightPtr something like this maybe?

else if ( key < treePtr->data ) { 
				binaryTreeSearch( treePtr->leftPtr, key ); /* search left */	
			       return leftPtr; //ADDED
}
				else if ( key > treePtr->data ) { 
					binaryTreeSearch( treePtr->rightPtr, key ); /* search right */
				return rightPtr; //ADDED
				} 

As a side note, I am not getting that error. I get the following:

test.c: In function ‘PrintChild’:
test.c:68: warning: format ‘%d’ expects type ‘int’, but argument 2 has type ‘TreeNodePtr’
Undefined symbols:
  "_printChild", referenced from:
      _main in cc2iA7jh.o
ld: symbol(s) not found
collect2: ld returned 1 exit status

[Salem_c]

> binaryTreeSearch( treePtr->leftPtr, key ); /* search left */
> return leftPtr; //ADDED
Try something like this instead.

return binaryTreeSearch( treePtr->leftPtr, key ); /* search left */

> As a side note, I am not getting that error. I get the following:
That's because the language is case sensitive.
Look at the first letter.

This post has been edited by Salem_c: 17 November 2010 - 10:23 PM

[MattWill]

Thanks for catching my typo Salem. I added your suggestion and changed my printChild command to accommodate that and I am almost there. It's printing the child however it only has 0's as the output. Code is as follows:

#include <stdbool.h>
#include <stdio.h> 
#include <stdlib.h> 

 
 /* TreeNode structure definition */ 
 struct TreeNode { 
	int data;
	struct TreeNode *leftPtr; /* pointer to left subtree */ 
	struct TreeNode *rightPtr; /* pointer to right subtree */ 
 }; /* end struct TreeNode */ 
 
 typedef struct TreeNode TreeNode;
 typedef TreeNode *TreeNodePtr; 
 
/* function prototypes */ 
void    BuildTree( void );
void insertInTree( TreeNodePtr *treePtr, int value ); 
int GetNumberFromFile( int *numPtr, FILE *fp );
TreeNodePtr binaryTreeSearch( TreeNodePtr treePtr, const int key );
void    PrintChild( TreeNodePtr searchResultPtr );

int main() 
{ 
int i;	/* loop counter */ 
int item;	/* random value to insert in tree */ 
int searchKey;	/* value to search for */ 

TreeNodePtr rootPtr = NULL; /* points to the tree root */ 
TreeNodePtr searchResultPtr; /* pointer to search result */ 

FILE    *fp;

   if ( ( fp = fopen( "Data.txt", "r" ) ) == NULL )
       printf( "Could not read numbers file!\n" );

 printf( "The numbers being placed in the tree are:\n" );

    while ( GetNumberFromFile( &item, fp ) )
    {
        printf( "%3d ", item );
        insertInTree( &rootPtr, item );
	    }

	 fclose( fp );
/* prompt user and read integer search key */ 
printf( "\n\nEnter an integer to search for: " ); 
scanf( "%d", &searchKey ); 

searchResultPtr = binaryTreeSearch( rootPtr, searchKey ); 

/* if searchKey not found */ 
	if ( searchResultPtr == NULL ) { 
	printf( "\n%d was not found in the tree.\n\n", searchKey ); 
	} /* end if */ 
	else{ /* if key found */ 
			printf( "\n%d was found in the tree.\n\n", searchResultPtr->data );
			printf("With left child: ");
			printChild(searchResultPtr->leftPtr);
			printf("With right child: ");
			printChild(searchResultPtr->rightPtr);

	} /* end else */ 
		return 0; /* indicate successful termination */ 
}/*endmain*/

void    printChild( searchResultPtr ) {
    printf( "%d ", searchResultPtr );
}
/*********************************************/
/*GetNumberFromFile- Specific function to  */
/* read the numbers from Data.txt         */
/*****************************************/	

int GetNumberFromFile( int *numPtr, FILE *fp )
	{
		    if ( fscanf( fp, "%d\n", numPtr ) == EOF )
		        return false;
		    else
		        return true;
	}

/*****************************/
/* insert numbers into treec*/ 
/***************************/
void insertInTree( TreeNodePtr *treePtr, int value ) 
{
	if ( *treePtr == NULL ) {
/* dynamically allocate memory */ 
*treePtr = malloc( sizeof( TreeNode ) ); 
			/* if memory was allocated, insert node */ 
		if ( *treePtr != NULL ) { 
		( *treePtr )->data = value; 
		( *treePtr )->leftPtr = NULL; 
		( *treePtr )->rightPtr = NULL; 
	}
		else { 
			printf( "%d not inserted. No memory available.\n", value ); 
	
		}
	 
	}
		else { /* recursively call insertInTree */ 
			
			if (value<( *treePtr )->data ) { 
				insertInTree( &( ( *treePtr )->leftPtr ), value ); 
			} 
			else { 
				/* insert node in right subtree */ 
				if (value>( *treePtr )->data ) { 
					insertInTree( &(( *treePtr )->rightPtr ), value ); 
				} 
			}  
		}
} 
/***************************/
/* search for key in tree */ 
/***************************/
TreeNodePtr binaryTreeSearch( TreeNodePtr treePtr, const int key )
{
	 
if ( treePtr == NULL ) {
	return NULL; /* key not found */ 
	}
		else if ( treePtr->data == key ) { 
			return treePtr; /* key found */ 
		}
			else if ( key < treePtr->data ) { 
				return binaryTreeSearch( treePtr->leftPtr, key ); /* search left */	
			}
				else if ( key > treePtr->data ) { 
					return binaryTreeSearch( treePtr->rightPtr, key ); /* search right */
				} 
} 

I also noted that randomly it will blurt out 104678 as its child node for both. I looked up some sites trying to find one the could explain what is wrong. But nothing... Any ideas?

Thanks again!

[Salem_c]

Fixing ALL your errors would be a start.

$ gcc -std=c99 -W -Wall foo.c
foo.c: In function ‘main’:
foo.c:59: warning: implicit declaration of function ‘printChild’
foo.c:25: warning: unused variable ‘i’
foo.c: At top level:
foo.c:67: warning: conflicting types for ‘printChild’
foo.c:59: note: previous implicit declaration of ‘printChild’ was here
foo.c: In function ‘printChild’:
foo.c:67: warning: type of ‘searchResultPtr’ defaults to ‘int’
foo.c: In function ‘binaryTreeSearch’:
foo.c:134: warning: control reaches end of non-void function

You might think they're only "warnings", but there are quite a few warnings which change the semantics of your program to the point where is isn't doing what you expect.

Line 67 for example.

Oh, and thanks for the 'distraction'

[MattWill]

Are we not allowed to ask questions on two different boards? I have been working on this for nearly two weeks, and I am not asking for anyone to 'do my work' I am more or less just trying to understand the concept of what I am doing. I have looked through numerous examples and have applied that to what I thought would be correct and yet I still get stuck at a certain point which is printing only one value and not the whole tree for example.

I do appreciate your help though as I am working on a remote linux box through terminal so I might miss a semicolon or like you mentioned a mistyped function call.

[MattWill]

And quick correction to what I said above. I know there are a lot more error's than just a missing semicolon or mistyped functions.

Since I want to call a pointer to integer I am going to use my void function so to fix printChild would something like this look correct?

void    printChild( TreeNodePtr searchResultPtr ) {
    printf( "%d ", searchResultPtr->data );
}

[janotte]

When you tried it, did it compile, did it produce the expected output?