Traversing through a Binary Tree

Expand Post »

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.

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:

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

Similar Threads

What means O(log n) time ? in C++
Help w/ Traversing a Huffman Tree in C++
Recursive Binary Search Tree Header File in C++
Traversing a Huffman Tree in C++
recursive algorithm in C++

tiki_master

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

2 posts
since Nov 2007

Permalink

Apr 6th, 2009

Re: Traversing through a Binary Tree

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.

seanhunt

Reputation Points: 13

Solved Threads: 6

Light Poster

Offline

40 posts
since Oct 2008

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: Linked List, Classes, and Pointers HELP

Next Thread in C++ Forum Timeline: Check if given one string part of other using wildcards

DaniWeb Message

Cancel Changes

User Name
Password