Assignment 2 Solution

Description

Part 1 (7 pts). Programming

Description:

This project is to create a binary search tree class called BinTree along with some additional functions (remove function is not required).

Your code should be able to read a data file consisting of many lines (an example file called data2.txt will be given containing lines as shown below) to build binary search trees.

61. not tttt eee r not and jj r eee pp r sssss eee not tttt ooo ff m m y z $$ b a c b a c $$

c b a $$

Each line consists of many strings and terminates with the string “$$”. Each line will be used to build one tree. The duplicated strings (i.e., having equal values with existing node data) are discarded, smaller strings go left, and bigger go right. For instance, the internal tree built from the first line of data2.txt should look like in Figure 1.

iii

1. • \

eeenot

1. data2.txt: input data file;

2. nodedata.h and nodedata.cpp: NodeData class;

3. lab2.cpp: containing main(), to help clarify the functional requirements;

4. lab2output: correct output in using lab2.cpp;

5. classAndSideway.txt: structure of BinTree class and 2 functions for helping display a

binary tree as if you are viewing it from the side. NOTE: They will be part of your program. You can adjust this definition to your implementation (although you must have the three pointers in the Node and it must work with lab2.cpp).

Submission Requirements:

All the rules, submission requirements, and evaluation criteria are the same as the assignment 1. The only difference is that Valgrind is required in this assignment for 1 point total grade. Part of the point will be deducted for “definitely lost” memory leak.

Part 2 (2 pts). Use as many 8½ by 11 inch pieces of paper to make your work clear. Scan or take pictures and upload to canvas.

1. Use Huffman coding to encode these symbols with given frequencies:

   1. 0.10 b: 0.25 c: 0.05 d: 0.15 e: 0.30 f: 0.07 g: 0.08

2. Build (draw) a heap (minheap, smallest value at root) by inserting one item at a time with the values:

1520348109514225

3. Build (draw) a heap (minheap, smallest value at root) using the linear algorithm with the values:

1028620351241015

Page 3 of 3