Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
Solved

# Build Huffman Tree with Priority Queue in C

Posted on 2007-04-08
Medium Priority
811 Views
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.
0
Question by:Karamelg11
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 3
• 3
• 2

LVL 16

Expert Comment

ID: 18873408
0

Author Comment

ID: 18873454
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.
0

LVL 84

Expert Comment

ID: 18873511
are you able to implement deleteMin and pqInsert?
0

LVL 84

Expert Comment

ID: 18873515
0

LVL 16

Expert Comment

ID: 18873521
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
0

Author Comment

ID: 18873596
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;
{
0

LVL 16

Accepted Solution

AlexNek earned 2000 total points
ID: 18873653
>converting it to C is where I am having the problem.
It can't be a big problem. Post the pseudo code and notice the parts with troubles.

>...in hopes of getting criticism
This lines look not so good for me.
tmp->left = leftP;
tmp->right = rightP;

tmp = MakeNode(top->symbol, top->weight, tmp->left, tmp->right);
You assign unassigned variable /at least I can't see where it was/, fill the fields and then assign variable.

I have a small notices in addition. I don't like:
- function parameters like int freqs[256
- variables declaration in one line TreeNode* leftP, *rightP, *tmp;
- such a logical expression while (tmp->left&&...
0

LVL 84

Expert Comment

ID: 18880541
top->weight and top->symbol also seem to be referencing an undefined pointer
what is MakeNode, and how  are TreeNode and TreeEntry defined?
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Computer science students often experience many of the same frustrations when going through their engineering courses. This article presents seven tips I found useful when completing a bachelors and masters degree in computing which I believe may heâ€¦
Make the most of your online learning experience.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.
Introduction to Processes
###### Suggested Courses
Course of the Month12 days, 5 hours left to enroll