Karamelg11
asked on
Build Huffman Tree with Priority Queue in C
Hi,
I am working on the Huffman Algorithm in C for my class project. I am having trouble building the huffman tree to start. This is what I have so far:
TreeNode * buildHuffmanTree(int freqs[256])
{
int i;
PriorityQueue forest;
TreeNode* leftP, *rightP, *tmp;
TreeEntry* top;
CreatePQueue(&forest);
/* YOU FILL IN THE REST OF THIS CODE */
for (i = 0; i < 256; i++)
{
if (freqs[i] > 0)
{
leftP = malloc (sizeof(TreeNode));
leftP->left = NULL;
leftP->right = NULL;
pqInsert(leftP, &forest);
}
}
while (freqs[i] > 1)
{
leftP = deleteMin(&forest);
rightP = deleteMin(&forest);
tmp->left = leftP;
tmp->right = rightP;
tmp = MakeNode(top->symbol, top->weight, tmp->left, tmp->right);
pqInsert(tmp, &forest);
}
return tmp;
{
If anyone has any advice I would appreciate it. Thanks.
I am working on the Huffman Algorithm in C for my class project. I am having trouble building the huffman tree to start. This is what I have so far:
TreeNode * buildHuffmanTree(int freqs[256])
{
int i;
PriorityQueue forest;
TreeNode* leftP, *rightP, *tmp;
TreeEntry* top;
CreatePQueue(&forest);
/* YOU FILL IN THE REST OF THIS CODE */
for (i = 0; i < 256; i++)
{
if (freqs[i] > 0)
{
leftP = malloc (sizeof(TreeNode));
leftP->left = NULL;
leftP->right = NULL;
pqInsert(leftP, &forest);
}
}
while (freqs[i] > 1)
{
leftP = deleteMin(&forest);
rightP = deleteMin(&forest);
tmp->left = leftP;
tmp->right = rightP;
tmp = MakeNode(top->symbol, top->weight, tmp->left, tmp->right);
pqInsert(tmp, &forest);
}
return tmp;
{
If anyone has any advice I would appreciate it. Thanks.
ASKER
I am familiar with all those web pages, and it doesn't really help me with implementing the actual code to create a tree using a priority queue.
are you able to implement deleteMin and pqInsert?
What is then your troubles? If you know algorithm very well then try to write pseudo code and then convert it to C
Here is one sample
http://www.codeproject.com/cpp/Huffman_coding.asp
Here is one sample
http://www.codeproject.com/cpp/Huffman_coding.asp
ASKER
ozo - I am able to implement deleteMin and pqInsert and I have in the following code. AlexNek, converting it to C is where I am having the problem. I had posted the code I had written in hopes of getting criticism on what I may be doing wrong.
TreeNode * buildHuffmanTree(int freqs[256])
{
int i;
PriorityQueue forest;
TreeNode* leftP, *rightP, *tmp;
TreeEntry* top;
CreatePQueue(&forest);
/* YOU FILL IN THE REST OF THIS CODE */
for (i = 0; i < 256; i++)
{
if (freqs[i] > 0)
{
leftP = malloc (sizeof(TreeNode));
leftP->left = NULL;
leftP->right = NULL;
top->weight = freqs[i];
top->symbol = (char) i;
leftP = MakeNode(top->symbol, top->weight, leftP->left, leftP->right);
pqInsert(leftP, &forest);
}
}
while (tmp->left&&tmp->right != NULL)
{
leftP = deleteMin(&forest);
rightP = deleteMin(&forest);
tmp->left = leftP;
tmp->right = rightP;
tmp = MakeNode(top->symbol, top->weight, tmp->left, tmp->right);
pqInsert(tmp, &forest);
}
return tmp;
{
TreeNode * buildHuffmanTree(int freqs[256])
{
int i;
PriorityQueue forest;
TreeNode* leftP, *rightP, *tmp;
TreeEntry* top;
CreatePQueue(&forest);
/* YOU FILL IN THE REST OF THIS CODE */
for (i = 0; i < 256; i++)
{
if (freqs[i] > 0)
{
leftP = malloc (sizeof(TreeNode));
leftP->left = NULL;
leftP->right = NULL;
top->weight = freqs[i];
top->symbol = (char) i;
leftP = MakeNode(top->symbol, top->weight, leftP->left, leftP->right);
pqInsert(leftP, &forest);
}
}
while (tmp->left&&tmp->right != NULL)
{
leftP = deleteMin(&forest);
rightP = deleteMin(&forest);
tmp->left = leftP;
tmp->right = rightP;
tmp = MakeNode(top->symbol, top->weight, tmp->left, tmp->right);
pqInsert(tmp, &forest);
}
return tmp;
{
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
top->weight and top->symbol also seem to be referencing an undefined pointer
what is MakeNode, and how are TreeNode and TreeEntry defined?
what is MakeNode, and how are TreeNode and TreeEntry defined?
http://www.siggraph.org/education/materials/HyperGraph/video/mpeg/mpegfaq/huffman_tutorial.html
http://www.maths.abdn.ac.uk/~igc/tch/mx4002/notes/node59.html
http://cs.wellesley.edu/~cs231/fall01/huffman-example.pdf
http://www.csl.mtu.edu/cs2321/www/newLectures/13_Huffman_Coding-2.html
http://datacompression.info/Huffman.shtml