### Spring 2022 ECE 264 :: Purdue University

⚠ This is a PAST SEMESTER (Spring 2022).
Due 4/19

# 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

## Overview

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

1. HW15: Implement priority queue for future use
2. HW16: Calculate character frequencies from a file
3. HW17: Create a priority queue of trees from the character frequencies in a file.
4. HW18: Build a single Huffman tree. ◀◀◀ this homework
5. HW19: Implement functions to write arbitrary bits to a file, for future use.
6. HW20: Write the Huffman Tree to the disk.
7. HW21: Write the encoded file contents to the disk.
8. huffman_8: 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 HW17 into a single Huffman tree. The algorithm is described in the article (originally linked from HW16), as well as this Huffman walkthrough .

### Input

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

### Output

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 HW18 and change into it.
```you@ecegrid-thin1 ~ \$ ````mkdir hw18`
```you@ecegrid-thin1 ~ \$ ````cd hw18`
3. Copy all of your files from HW17 into your HW18 directory.
```you@ecegrid-thin1 ~/hw18 \$ ````cp ../hw17/{*.[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 ~/hw18 \$ ````vim Makefile`
This should require chaning only a single line. You should now have this: `ASG_NICKNAME=HW18`
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 ~/hw18 \$ ````vim huffman.h`

## Requirements

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 HW17.
declarations All declarations from HW17, plus those added for HW18 (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 HW18.
2. Submissions must meet the code quality standards and other course policies on homework.

## Submit

To submit HW18 from within your hw18 directory, type

`make submit`

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

## Pre-tester ●

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

# Q&A

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 hw17 directory into your into your hw18 directory.

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

```you@ecegrid-thin1 ~/hw18 \$ ````cp hw17/*.c hw18/`
```you@ecegrid-thin1 ~/hw18 \$ ````cp hw17/*.h hw18/`
```you@ecegrid-thin1 ~/hw18 \$ ````cp hw17/Makefile hw18/`
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 `~/hw18`, (hw18 directory within your home directory), `..` means your home directory, and `../hw17` means the hw17 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, `hw17/{*.[ch],Makefile}` means `hw17/*.[ch]` and `hw17/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, `hw17/*.[ch]` means `hw17/*.c` and/or `hw17/*.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.