8 Replies - 436 Views - Last Post: 03 January 2013 - 09:50 AM Rate Topic: -----

#1 lanza  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 17-March 10

Binary Search Tree and Recursion Not Displaying Properly

Posted 02 January 2013 - 04:28 PM

Hi Everyone,

As I mentioned in a previously posted of mine, I am working/studying subjects for a class I will have to take soon. It's an Advanced Data Structure and Algorithm class.

Presently, I am working on a little project using Binary Tree and Recursion however I have some questions/issues that I am still not able to solve or figure it out.

My code follows, and thereafter my questions/issues:

#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>

using namespace std;  

const string IN_FILENAME = "FILE.TXT";    // constant input file name 

struct node
{
  int    key_value;
  node*  left;
  node*  right;
};

// function prototypes 
void  ReadInFile(ifstream&, node*);       // read integers from input file into the tree
//void insert(int key, node** leaf);      // storing a list of integers into a binary tree
node* insert(int& key, node* leaf);       // storing a list of integers into a binary tree
void print_in_order(node*);               // display in traversal order the integers in the tree to the screen

//**********************************************************************
int main(int argc, char* argv[])
{
	ifstream inFile;       // to handle the input file
	int count = -1;        // for counting
	bool result = true;    // to control the loop	
	string file = " ";	   // to handle the filename
	node* root = new node; // create a tree       
	
	do 
	{	
		cout << "Please enter a filename: ";
		getline(cin, file);	
		transform( file.begin(), file.end(), file.begin(), toupper );	
		
		if ( file == IN_FILENAME.c_str() )
        { 
			inFile.open( IN_FILENAME.c_str() );
			ReadInFile( inFile, root );
			result = false;
		}
		else
		{
			cout << "The filename entered does not exist!" << endl;
			cout << "Please type it again." << endl << endl;
			result = true;
		}
 
	} while ( result );
	
    cout << endl << endl;
	system("PAUSE");  
    return 0;
}

//**************************************************************************
void ReadInFile(ifstream& inFile, node* node) 
{
	int number = 0;  
	int newNumber = 0;			
	
	node->key_value = 0;  
	node->left =      NULL; 
	node->right =     NULL; 
	cout << endl;
     
        // input file: 49 83 91 17 62
	
        while ( inFile )
	{
		inFile >> number;
		node->key_value = number;  
		insert( number, node );    
	}

	print_in_order( node );	
	
	inFile.close();		
}

//**************************************************************************
node* insert(int& key, node* leaf)
{
	if( key < leaf->key_value )
    {
		if( leaf->left != NULL )
			insert( key, leaf->left );
		
		else
		{
		  leaf->left = new node;
		  leaf->left->key_value = key;
		  leaf->left->left = NULL;       
		  leaf->left->right = NULL;      
		}  
    }
    
	else if( key >= leaf->key_value )
    {
		if( leaf->right != NULL )
			insert( key, leaf->right );
		
		else
		{
		  leaf->right = new node;
		  leaf->right->key_value = key;  
		  leaf->right->left = NULL;      
		  leaf->right->right = NULL;     
		}
    }
	
	return leaf;
}

//**************************************************************************
void print_in_order(node* p) 
{
    if( p != NULL )
    {
        if( p->left ) 
			print_in_order( p->left );
        
		cout<< " " << p->key_value << " ";
        
		if( p->right ) 
			print_in_order( p->right );
    }

	else 
		return;	
}



//*******************************************************************
Integer in the Input File:

49 83 91 17 62


Output So Far:

Please enter a filename: file.txt

62 17 49 62 62 83 91

Press any key to continue . . .


Questions:

1)Why my print_in_order function is printing extras 62?

2) It's the order being used in the code and then displaying using recursive "in-order" tree?

3) What number should be printed/displaying when using "in-order", 17 62 91 83 49 ?

4) Does my insert, and print_in_order function make sense?

5) Any mistakes/errors I am not seeing it.

My code compile but I am not sure if it's behaving the way I expected. I know that it should not display extras 62 but am not sure what is the order to be displayed when using "in order" based on the integers from my input file.

I attached the input file just in case.

Big Thanks in advance.

Marco

Is This A Good Question/Topic? 0
  • +

Replies To: Binary Search Tree and Recursion Not Displaying Properly

#2 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1327
  • View blog
  • Posts: 4,552
  • Joined: 19-February 09

Re: Binary Search Tree and Recursion Not Displaying Properly

Posted 02 January 2013 - 06:23 PM

When the read fails (at the end of file) then you still insert a number. The old number is not overwritten so will still be 62.

071	    while ( inFile )
072	    {
073	        inFile >> number;
074	        node->key_value = number; 
075	        insert( number, node );   
076	    }




The easiest way to prevent this is to check the read in the while condition.

071	    while ( inFile >> number)
072	    {
073	        
074	        node->key_value = number; 
075	        insert( number, node );   
076	    }




I would think this would insert only one extra 62, though.
Was This Post Helpful? 1
  • +
  • -

#3 lanza  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 17-March 10

Re: Binary Search Tree and Recursion Not Displaying Properly

Posted 03 January 2013 - 05:49 AM

Hi #define,

Thanks for your help.

I just replied to this topic here (using Fast Reply) but I CANNOT see my replied message. I already refresh it and still not able to see it.

Not sure what happened?

I wait before I replied again, thanks.

Marco
Was This Post Helpful? 0
  • +
  • -

#4 lanza  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 17-March 10

Re: Binary Search Tree and Recursion Not Displaying Properly

Posted 03 January 2013 - 06:02 AM

Hi,

Now it's working (adding).

Since it eliminate an extra 62, my next question (I am working on it/reading articles here an on other places as well) follows:

1) Does the following output make sense by using "a recursive in-order tree traversal"?

input file: 49 83 91 17 62

output: 62 17 49 62 83 91

I noticed that still outputs an extra 62. I understand also that the insertion occurred by adding "smaller numbers to the left while bigger numbers to the right" but then by displaying these numbers into the screen using "in order" is what I am not sure about it. What numbers come first and then after when displaying it.

Big thanks.

Marco
Was This Post Helpful? 0
  • +
  • -

#5 jimblumberg  Icon User is offline

  • member icon


Reputation: 4002
  • View blog
  • Posts: 12,349
  • Joined: 25-December 09

Re: Binary Search Tree and Recursion Not Displaying Properly

Posted 03 January 2013 - 08:17 AM

Please post your current code where you implemented the changes suggested.

Jim
Was This Post Helpful? 1
  • +
  • -

#6 lanza  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 17-March 10

Re: Binary Search Tree and Recursion Not Displaying Properly

Posted 03 January 2013 - 08:36 AM

the code changed follows:

void ReadInFile(ifstream& inFile, node* node) 
{
	int number = 0;  
	int newNumber = 0;			
	
	node->key_value = 0;  
	node->left =      NULL; 
	node->right =     NULL; 
	cout << endl;
    
	while ( inFile >> number )
	{
		node->key_value = number;  
		insert( number, node );    
	}

	print_in_order( node );	
	
	inFile.close();		
}


the whole code follows:

#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>

using namespace std;  

const string IN_FILENAME = "FILE.TXT";    // constant input file name 

struct node
{
  int    key_value;
  node*  left;
  node*  right;
};

// function prototypes 
void  ReadInFile(ifstream&, node*);       // read integers from input file into the tree
//void insert(int key, node** leaf);      // storing a list of integers into a binary tree
node* insert(int& key, node* leaf);       // storing a list of integers into a binary tree
void print_in_order(node*);               // display in traversal order the integers in the tree to the screen
//*********************************************************************
//  FUNCTION:	main
//  DESCRIPTION:	initializes variables and call ReadInFile to open and 
//  loop the file and then call functions to process the data into the 
//  binary tree.   
//  INPUT:
//      Parameters: argc, *argv[]
//      File:	    Lanza-assn3-testdataA.txt
//  OUTPUT:	
//      Return Val: 0 if successful 
//      Parameters: none
//      File:	    none
//  CALLS TO:       ReadInFile
//**********************************************************************
int main(int argc, char* argv[])
{
	ifstream inFile;       // to handle the input file
	int count = -1;        // for counting
	bool result = true;    // to control the loop	
	string file = " ";	   // to handle the filename
	node* root = new node; // create a tree       
	
	do 
	{	
		cout << "Please enter a filename: ";
		getline(cin, file);	
		transform( file.begin(), file.end(), file.begin(), toupper );	
		
		if ( file == IN_FILENAME.c_str() )
        { 
			inFile.open( IN_FILENAME.c_str() );
			ReadInFile( inFile, root );
			result = false;
		}
		else
		{
			cout << "The filename entered does not exist!" << endl;
			cout << "Please type it again." << endl << endl;
			result = true;
		}
 
	} while ( result );
	
    cout << endl << endl;
	system("PAUSE");  
    return 0;
}
//*************************************************************************
//  FUNCTION:	ReadInFile
//  DESCRIPTION:	read its data into the tree
//  INPUT:
//      Parameters: inFile - input file stream
//      File:	    numbers.txt (integers 5-digits long)
//  OUTPUT:	
//      Return Val: none
//      Parameters: none
//      File:	    none
//  CALLS TO:       insert, print_in_order
//**************************************************************************
void ReadInFile(ifstream& inFile, node* node) 
{
	int number = 0;  
	int newNumber = 0;			
	
	node->key_value = 0;  
	node->left =      NULL; 
	node->right =     NULL; 
	cout << endl;
    // input file: 49 83 91 17 62
	while ( inFile >> number )
	{
		node->key_value = number;  
		insert( number, node );    
	}

	print_in_order( node );	
	
	inFile.close();		
}
//*************************************************************************
//  FUNCTION:	insert
//  DESCRIPTION:	storing a list of integers into a binary tree
//  INPUT:
//      Parameters: key  - input integer from file
//                  leaf - to be stored
//      File:	    none
//  OUTPUT:	
//      Return Val: data pointer pointing to the tree
//      Parameters: none
//      File:	    none
//  CALLS TO:       none
//**************************************************************************
node* insert(int& key, node* leaf)
{
	if( key < leaf->key_value )
    {
		if( leaf->left != NULL )
			insert( key, leaf->left );
		
		else
		{
		  leaf->left = new node;
		  leaf->left->key_value = key;
		  leaf->left->left = NULL;       
		  leaf->left->right = NULL;      
		}  
    }
    
	else if( key >= leaf->key_value )
    {
		if( leaf->right != NULL )
			insert( key, leaf->right );
		
		else
		{
		  leaf->right = new node;
		  leaf->right->key_value = key;  
		  leaf->right->left = NULL;      
		  leaf->right->right = NULL;     
		}
    }
	
	return leaf;
}
//*************************************************************************
//  FUNCTION:	print_in_order
//  DESCRIPTION:	print the tree in traversal order
//  INPUT:
//      Parameters: node - tree with data to be printed
//      File:	    none
//  OUTPUT:	
//      Return Val: none
//      Parameters: none
//      File:	    none
//  CALLS TO:       none
//**************************************************************************
void print_in_order(node* p) 
{
    if( p != NULL )
    {
        if( p->left ) 
			print_in_order( p->left );
        
		cout<< " " << p->key_value << " ";
        
		if( p->right ) 
			print_in_order( p->right );
    }

	else 
		return;	
}



Thanks.

Marco

This post has been edited by jimblumberg: 03 January 2013 - 09:00 AM
Reason for edit:: Added missing Code Tags, Please learn to use them.

Was This Post Helpful? 0
  • +
  • -

#7 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 352
  • View blog
  • Posts: 770
  • Joined: 27-June 09

Re: Binary Search Tree and Recursion Not Displaying Properly

Posted 03 January 2013 - 09:12 AM

while ( inFile >> number )  
{  
	node->key_value = number;    
	insert( number, node );      
}



Currently, node is the root. You write each value in the file to the root, then run the insert. This will screw up the ordering. For example, you set the root to 49, then insert 49. Then you set the root to 83 and then insert 83, and so on. You should read the first number and set the key, then on all subsequent reads insert the number.

if ( inFile >> number )
{
	node->key_value = number;
} 
while ( inFile >> number )  
{      
	insert( number, node );      
}

Was This Post Helpful? 1
  • +
  • -

#8 jimblumberg  Icon User is offline

  • member icon


Reputation: 4002
  • View blog
  • Posts: 12,349
  • Joined: 25-December 09

Re: Binary Search Tree and Recursion Not Displaying Properly

Posted 03 January 2013 - 09:40 AM

First your program doesn't compile for me. I get the following errors.

Quote

/main.cpp||In function ‘int main(int, char**)’:|
/main.cpp|48|error: no matching function for call to ‘transform(std::basic_string<char>::iterator, std::basic_string<char>::iterator, std::basic_string<char>::iterator, <unresolved overloaded function type>)’|
/main.cpp|48|note: candidates are:|
/opt/gcc-4.7.2/lib/gcc/i686-pc-linux-gnu/4.7.2/../../../../include/c++/4.7.2/bits/stl_algo.h|4940|note: template<class _IIter, class _OIter, class _UnaryOperation> _OIter std::transform(_IIter, _IIter, _OIter, _UnaryOperation)|
/opt/gcc-4.7.2/lib/gcc/i686-pc-linux-gnu/4.7.2/../../../../include/c++/4.7.2/bits/stl_algo.h|4940|note: template argument deduction/substitution failed:|
/main.cpp|48|note: couldn't deduce template parameter ‘_UnaryOperation’|
/opt/gcc-4.7.2/lib/gcc/i686-pc-linux-gnu/4.7.2/../../../../include/c++/4.7.2/bits/stl_algo.h|4977|note: template<class _IIter1, class _IIter2, class _OIter, class _BinaryOperation> _OIter std::transform(_IIter1, _IIter1, _IIter2, _OIter, _BinaryOperation)|
/opt/gcc-4.7.2/lib/gcc/i686-pc-linux-gnu/4.7.2/../../../../include/c++/4.7.2/bits/stl_algo.h|4977|note: template argument deduction/substitution failed:|
/main.cpp|48|note: candidate expects 5 arguments, 4 provided|
/main.cpp|39|warning: unused variable ‘count’ [-Wunused-variable]|
/main.cpp|36|warning: unused parameter ‘argc’ [-Wunused-parameter]|
/main.cpp|36|warning: unused parameter ‘argv’ [-Wunused-parameter]|
/main.cpp||In function ‘void ReadInFile(std::ifstream&, node*)’:|
/main.cpp|85|warning: unused variable ‘newNumber’ [-Wunused-variable]|
||=== Build finished: 8 errors, 4 warnings ===|

These errors are all being caused by the "using namespace std;" clause. There are two different toupper() functions available. One in the std namespace and one in the global namespace. The one you want to use in your transform function is the the one in the global namespace. to solve this problem you should properly scope the toupper function:
		transform( file.begin(), file.end(), file.begin(), ::toupper );

This is one of the hazards of using the "using namespace std;" clause.

Next trying to force your file name to upper case is a very poor idea. Some, if not most, modern operating systems are or can be case sensitive. I suggest you start getting used to this idea. Just tell you user to enter the file name properly. More importantly you should be checking that the file opened correctly, just because the file name is the same as what you expect doesn't insure the file actually opened correctly.

Now in the following snippet:
node* insert(int& key, node* leaf)
{
	if( key < leaf->key_value )
    {
		if( leaf->left != NULL )
			insert( key, leaf->left );

		else
		{
		  leaf->left = new node;
		  leaf->left->key_value = key;
		  leaf->left->left = NULL;
		  leaf->left->right = NULL;
		}
    }

	else if( key >= leaf->key_value )
    {
		if( leaf->right != NULL )
			insert( key, leaf->right );

		else
		{
		  leaf->right = new node;
		  leaf->right->key_value = key;
		  leaf->right->left = NULL;
		  leaf->right->right = NULL;
   print_in_order(leaf);
   cout << endl;
		}
    }
//   print_in_order(leaf);
//   cout << endl;

	return leaf;
}

I added the print_in_order() statement to see what was actually happening after adding the information and I got this output:

 49  49 
 49  83 
 83  91 
 62  17  49  62  83  91 


And moving these tow statements to just above the return I got this output.

 49  49 
 49  83 
 83  49  83 
 83  91 
 49  83  91 
 91  49  83  91 
 17  49  83  91 
 17  17  49  83  91 
 62  83  91 
 17  49  62  83  91 
 62  17  49  62  83  91 
 62  17  49  62  83  91 



Jim

This post has been edited by jimblumberg: 03 January 2013 - 09:41 AM

Was This Post Helpful? 1
  • +
  • -

#9 lanza  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 17-March 10

Re: Binary Search Tree and Recursion Not Displaying Properly

Posted 03 January 2013 - 09:50 AM

Hi Mojo666, Jimblumber, and #define,

The following is the output from the code (using in order, pre order and post order, respectivelly):

in_order:

17 49 62 83 91

pre_order:

49 17 83 62 91

post_order:

17 62 91 83 49

As I said before, I assume that the one that matters to me now, in order is correct but for sure I will figure myself later.

Thanks for "re-adding" my function; I thought that I put it between

; apparently, I did not. -:)

Big thanks in advance for all of you. I still have more features to add/code and soon I will have to learn and deal/fiddling with Efficiency Analysis such as analyzing the efficiency of each function not including main; explaining it; using it to determine the big-O efficiency for the whole program and etc.

Once again big thanks for all of you; "you guys rock".

Marco

oops, my "code..." added one line, sorry.

Thanks again.

Marco
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1