Advanced C Programming

Spring 2020 ECE 264 :: Purdue University

⚠ This is a PAST SEMESTER (Spring 2020).
Due 4/17

Huffman 4: build Huffman tree

Learning goals

You should learn:

  1. Practice using linked lists and trees.
  2. Combining linked lists with trees
  3. Learning objectives: structures and dynamic structures


This is part 4 in an 8-part series in which you are implementing the Huffman Coding algorithm to compress files.

  1. HW11: Implement priority queue for future use
  2. HW12: Calculate character frequencies from a file
  3. HW13: Create a priority queue of trees from the character frequencies in a file.
  4. HW14: Build a single Huffman tree. ◀◀◀ this homework
  5. HW15: Implement functions to write arbitrary bits to a file, for future use.
  6. HW16: Write the Huffman Tree to the disk.
  7. HW17: Write the encoded file contents to the disk.
  8. HW18: Create a command-line interface for compressing files.

Your task in this homework is to transform the priority queue of tree nodes that you generated in HW13 into a single Huffman tree. The algorithm is described in the article (originally linked from HW12), as well as this Huffman walkthrough .


The input to your code will be a priority queue like this:


The output to your code will be a tree like this. Note that this is a Huffman tree, not a binary search tree (BST).

Getting Started

There is no starter code. However, we recommend creating a new directory for each step of the Huffman series.

  1. Read the Huffman walkthrough and make sure you understand the algorithm for building the Huffman tree.
  2. Create a directory for HW14 and change into it.
    you@ecegrid-thin1 ~ $ mkdir hw14
    you@ecegrid-thin1 ~ $ cd hw14
  3. Copy all of your files from HW13 into your HW14 directory.
    you@ecegrid-thin1 ~/hw14 $ cp ../hw13/{*.[ch],Makefile} -t ./
    See the Q&A for an explanation of this cp command.
  4. Update your Makefile with the new ASG_NICKNAME.
    you@ecegrid-thin1 ~/hw14 $ vim Makefile
    This should require chaning only a single line. You should now have this: ASG_NICKNAME=HW14
  5. Edit your huffman.h to add the declarations for make_huffman_tree(…) and destroy_huffman_tree(…). No other edits are necessary.
    you@ecegrid-thin1 ~/hw14 $ vim huffman.h


  1. Your submission must contain each of the following files, as specified:
    file contents
    huffman.c functions
    make huffman tree(Node✶ head)
    return type: TreeNode✶
    Create a tree from the given priority queue.
    • Follow the algorithm given in the article and Huffman walkthrough .
    • Set the .character field of each newly created cluster (non-leaf) node to '\0'.
    • All Node objects in the priority queue must be freed.
    • Use your pq_enqueue(…) and pq_dequeue(…).
    • If the priority queue is empty (i.e., head==NULL), return an empty Huffman tree (i.e., NULL).
    • The parameter to this function may be called head or pq.
    destroy huffman tree(TreeNode✶✶ a root)
    return type: void
    Destroy a Huffman tree that was created using make_huffman_tree(…).
    • *a_root refers to the root of a Huffman tree created by make_huffman_tree(…).
    • Set *a_root to NULL.
    huffman.h types All types from HW13.
    declarations All declarations from HW13, plus those added for HW14 (specified above).
    test_huffman.c functions
    main(int argc, char✶ argv[])
    return type: int
    • 100% code coverage is required for huffman.c.
      • Direct testing of frequencies.c and priority_queue.c is optional for HW14.
    • Use your miniunit.h.
  2. Submissions must meet the code quality standards and other course policies on homework.


To submit HW14 from within your hw14 directory, type

make submit

That should result in the following command: 264submit HW14 huffman.c huffman.h frequencies.c frequencies.h priority_queue.c priority_queue.h test_huffman.c miniunit.h clog.h Makefile


The pre-tester for HW14 has been released and is ready to use.


  1. What is the weird syntax in the cp command?

    That command copies all files ending with “.c” or “.h” and your Makefile from your hw13 directory into your into your hw14 directory.

    It is equivalent to the following three commands, but shorter and more error-resistant.

    $ cp hw13/*.c hw14/
    $ cp hw13/*.h hw14/
    $ cp hw13/Makefile hw14/
    There are a few things going on here.
    • cp files… -t target_directory means to copy files… to target_directory.

      It is equivalent to cp files… target_directory.

      The -t makes it explicit that the thing after it is the target directory. That prevents some errors people sometimes make when you mistype something and end up copying one file over another—and losing the second file. With -t the thing after it must be a directory.
    • .. means the parent directory, relative to your current directory.

      Since you are currently in ~/hw14, (hw14 directory within your home directory), .. means your home directory, and ../hw13 means the hw13 directory within your home directory.

    • ./ means the current directory.

      The slash at the end is optional, but prevent errors. Without it, you might forget the dot (.). Also, adding a slash to the end of something explicitly states that it is a directory, so you don't accidentally mix up a file and a directory.

    • {♥,♦,♣} means ♥, ♦, and ♣. Thus, hw13/{*.[ch],Makefile} means hw13/*.[ch] and hw13/Makefile.
    • [♥♦♣] is a character class, and is equivalent to ♥, ♦, and/or ♣. Unlike the pattern with curly braces, in a character class, ♥, ♦, and ♣ must be single characters.

      Thus, hw13/*.[ch] means hw13/*.c and/or hw13/*.h.

  2. How much work is this?

    The instructor's solution uses 16 sloc for make_huffman_tree(…) and 8 sloc for destroy_huffman_tree(…).

    Note: destroy_huffman_tree(…) is extremely similar to the destroy function you already wrote for tree_sort.

  3. The instructor's solution seems awfully short. Is it legit?

    That solution is compliant with our code quality standards, but does take one shortcut: It reuses head -> next as a cluster node, to avoid freeing one Node and then malloc'ing space for another Node as the cluster. That's not exactly the way we described the algorithm in lecture, but it's equivalent. Also, some unnecessary #include's have been removed.


4/16/2020 Added destroy_huffman_tree(…) and details about test_huffman.c.
4/17/2020 Fixed a few issues…
  • destroy_huffman_tree(…) should return void.
  • huffman.h should include declarations for destroy_huffman_tree(…), as well as make_huffman_tree(…) and the ones from previous assignments.