c++ huffman code

[scott123]

never mind i solved this today and it works perfectly

edit: my question was if i have a tree that represents huffman code ( google what the tree is like ), how could i get the huffman code corresponding to the chacters stored in the leaf nodes. what i did was make it so that each node knew its parent. this is my code :

void Huffman::makeHuffCode(TreeNode *ptr)
{
	//standard tree traversal
	if(!ptr){
		return;
	}
    makeHuffCode(ptr->left);
	//dont print the huffman code for blank nodes 
	string str = getBitString(ptr);
	if( isalpha(ptr->letter) ){
		cout << ptr->letter << " with a frequence of " << ptr->freq <<  ", corresponds to : " << str << endl;
	}
	makeHuffCode(ptr->right);
}

which calls this function

//this function returns the bit string to a corresponding node
	string getBitString(TreeNode *ptr){
		string str;
		//keep stepping up until you are at the root
		while(ptr->parent){
			if( ptr->parent){
				//if this node is a left child of its parent
				if(ptr->parent->left == ptr ){
					str.push_back('0');
				}
				//if this node is a right child of its parent
				else if(ptr->parent->right == ptr){
					str.push_back('1');
				}
				ptr=ptr->parent;
			}
		}
		//reverse str
		string toRet;
		for( int i = 0; i < str.size(); i++){
			toRet.push_back(str[str.size()-1-i]);
		}
		return toRet;
	}

 

[jpmkm]

You answered your own question. When you move left, print out a 0; when you move right, print out a 1. When you hit a node with no children, print out the character. Or perhaps I missed the point of the question. Did you want to take a specific character as input and then output its corresponding huffman code? I don't think you can directly do that with a tree traversal without trying every traversal until you hit the character. Or perhaps you could just ask your professor for help.

 

[Tawnos]

stacks fri your ends... er... are your friends..

here's how I'd do it if I needed to hack it right now...
keep track of last node, start going left, pushing 0s and node order... when you reach the end (may have to go right... the end being the first leaf node) check to see if that node contains the character you want the code for, if not, pop both stacks until a new direction is possible (you can tell this by comparing last node to what you're popping... if you can't figure out what I mean by that, I'll explain better, but that should get you going in the right direction). Basically, do a postorder style traversal and keep track.

Once you have your match, simply print the character, then the stack in reverse order.

 

[mikeblas]

Bummer that you deleted the question. Why not leave it around, so other can search and learn?