?
Solved

Build Huffman Tree with Priority Queue in C

Posted on 2007-04-08
8
Medium Priority
?
800 Views
Last Modified: 2011-09-20
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
Comment
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
  • Learn & ask questions
  • 3
  • 3
  • 2
8 Comments
 

Author Comment

by:Karamelg11
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

by:ozo
ID: 18873511
are you able to implement deleteMin and pqInsert?
0
Percona Live Europe 2017 | Sep 25 - 27, 2017

The Percona Live Open Source Database Conference Europe 2017 is the premier event for the diverse and active European open source database community, as well as businesses that develop and use open source database software.

 
LVL 84

Expert Comment

by:ozo
ID: 18873515
0
 
LVL 16

Expert Comment

by:AlexNek
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

by:Karamelg11
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

by:
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

by:ozo
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

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
This article will inform Clients about common and important expectations from the freelancers (Experts) who are looking at your Gig.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
Suggested Courses
Course of the Month8 days, 7 hours left to enroll

764 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question