### 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

## Overview

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 .

### 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 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`

## 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 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.
2. Submissions must meet the code quality standards and other course policies on homework.

## Submit

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`

## Pre-tester ●

The pre-tester for HW14 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 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.