DaniWeb Forum Index > Software Development > C++

Traversing through a Binary Tree

Please support our C++ advertiser: Intel Parallel Studio Home

•

Join Date: Nov 2007

Posts: 2

Reputation: tiki_master is an unknown quantity at this point

Solved Threads: 0

tiki_master tiki_master is offline

Offline

Newbie Poster

Traversing through a Binary Tree

Apr 6th, 2009

I have the following code below which is part of a program to create a Huffman Coding tree. The problem is that it runs through correctly for one node, outputting that character 'l' for a certain file has a specific frequency. However...after going through several iterations, it runs into a segmentation fault on the line "if(root->isLeaf)" I see the output of "root!=NULL", but then it displays Segmentation Fault.

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
string encoding;
void FileData::getEncoding(Node *root,string encoding){
 
	if(root!=NULL){
		cout << "root!=NULL" << endl;
		if(root->isLeaf){
			cout << "This is a leaf" << endl;
			cout << "Encoding for character '"<< root->value << "' is '" << encoding << "'" << endl;
		}
 
	}else{
		cout << "return reached" << endl;
	return;
	}
 
	string encode0;
	encode0=encoding+"0";
	cout << "getEncoding for left" << endl;
	getEncoding(root->left,encode0);
 
	string encode1;
	encode1=encoding+"1";
	cout << "getEncoding for right" << endl;
	getEncoding(root->right,encode1);
 
 
}
string encoding;
void FileData::getEncoding(Node *root,string encoding){
	
	if(root!=NULL){
		cout << "root!=NULL" << endl;
		if(root->isLeaf){
			cout << "This is a leaf" << endl;
			cout << "Encoding for character '"<< root->value << "' is '" << encoding << "'" << endl;
		}
		
	}else{
		cout << "return reached" << endl;
	return;
	}
	
	string encode0;
	encode0=encoding+"0";
	cout << "getEncoding for left" << endl;
	getEncoding(root->left,encode0);
	
	string encode1;
	encode1=encoding+"1";
	cout << "getEncoding for right" << endl;
	getEncoding(root->right,encode1);
	
	
}

Output is as follows:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
root!=NULL
getEncoding for left
root!=NULL
getEncoding for left
root!=NULL
This is a leaf
Encoding for character 'l' is '00'
getEncoding for left
root!=NULL
getEncoding for left
return reached
getEncoding for right
root!=NULL
Segmentation fault
root!=NULL
getEncoding for left
root!=NULL
getEncoding for left
root!=NULL
This is a leaf
Encoding for character 'l' is '00'
getEncoding for left
root!=NULL
getEncoding for left
return reached
getEncoding for right
root!=NULL
Segmentation fault

•

Join Date: Oct 2008

Posts: 40

Reputation: seanhunt is an unknown quantity at this point

Solved Threads: 6

seanhunt

Offline

Light Poster

Re: Traversing through a Binary Tree

Apr 6th, 2009

First, using the same name for an argument and a global is confusing (string encoding)...if you are using it as a constant, make sure you initialize it (not all compilers will do this for you, especially in release), and remove the argument from the method declaration and definition.
I don't have everything to debug it, but, this is probably caused by a pointer to memory that is not valid. Pointers may be initialized when they are defined (again, depending on the compiler and optimizations it uses), and are never automatically "reset" to NULL when they are not valid. So the test (root!=NULL) will pass on any pointer, valid or not, that or not initialized to NULL.