$19\mathrm{.}13$ Lab $10$ Huffman Tree Puzzler

Overview

You will write a function that given an in$-$order and a level$-$order traversal builds the binary tree.

This will complete a program that reads three text files given as command line parameters. The first file is an inorder

traversal of a Huffman code tree and the second parameter is the levelorder traversal of the same tree. The third file is the

encoded text, given as ASCII $0$s and $1$s$.$

All but the function are provided for you.

Details

Your program will:

Read the input files $($DONE FOR YOU$)$

Compute the Huffman code tree from the two traversals. $($TODO$)$

Decode the text, writing the output to standard output $($cout$).($DONE FOR YOU$)$

The format of the in$-$order and level$-$order traversals will be integer values separated by whitespace. The leaves of the tree

will be values representing the ASCII value of the letter. The internal nodes of the tree will be values $128$ and greater.

Stated another way: the smaller values are characters in the leaf nodes and the larger values are non$-$leaf nodes.

Examples

An example run:

$./$decode inorder$0.$txt levelorder$0.$txt encoded$0.$txt

inorder$0.$txt:

$\{$:$[66,129,76,128,77,130,65]$:$\}$

Interpreted as: $\text{'}$B$\text{'}129\text{'}$L$\text{'}128\text{'}$M$\text{'}130\text{'}$A$\text{'}$

levelorder$0.$txt:

$\{$:$[130,129,65,66,128,76,77]$:$\}$

Interpreted as: $130129$ A B $128$ LM

encoded$0.$txt:

$101010010111$

Output:

ALABAMA

The Huffman tree:

This project given

#include

#include

#include

using namespace std;

class HuffNode $\{$

public:

int val;

HuffNode $*$left;

HuffNode $*$right;

HuffNode$($int v $=0,$ HuffNode $*$l $=$ nullptr, HuffNode $*$r $=$ nullptr$)\{$

val $=$ v;

left $=$ l;

right $=$ r;

$\}$

$\}$;

$//$TODO: All you have to do is build the tree $...$ complete this function

HuffNode $*$createTreeFromInAndLevel$($const vector &inorder, const vector &levelorder$)\{$

$//$build the tree

$//$level order gives you the root

$//$inorder gives you left$/$right of root

$//$construct vectors for left $/$ right and recursively build the tree

$\}$

$/*$

The rest is complete.

$*/$

void decode$($HuffNode $*$q$,$ HuffNode $*$root$,$ string encoded$)\{$

$//$if $($q$->$val $<mtext></mtext><mn>1</mn><mn>2</mn><mn>8</mn><mi>)</mi><mtext></mtext><mi>\{</mi>$

if $($q$->$left $==$ nullptr && q$->$right $==$ nullptr$)\{$

char ascii $=($char$)$q$->$val;

cout $$ ascii;

q $=$ root;

$\}$

if $($encoded$.$length$()==0)$ return;

char dir $=$ encoded$[0]$;

if $($dir $==\text{'}0\text{'})\{$

decode$($q$->$left, root, encoded.substr$(1))$;

$\}$

else if $($dir $==\text{'}1\text{'})\{$

decode$($q$->$right, root, encoded.substr$(1))$;

$\}$

$\}$

int main$($int argc, char $*$argv$[])\{$

ifstream inorderFile$($argv$[1])$;

ifstream levelorderFile$($argv$[2])$;

ifstream encodedFile$($argv$[3])$;

if $($inorderFile$.$fail$()||$ levelorderFile.fail$()||$ encodedFile.fail$())\{$

cout $$ "Could not open input file$($s$)"$ endl;

return $1$;

$\}$

vector inorder;

vector levelorder;

string encoded;

int val;

char ch;

$//$read the inorder file

while $($inorderFile $>>$ val$)\{$

inorder.push$\_$back$($val$)$;

$\}$

$//$read the level order file

while $($levelorderFile $>>$ val$)\{$

levelorder.push$\_$back$($val$)$;

$\}$

$//$read the encoded file

while $($encodedFile $>>$ ch$)\{$

encoded $+=$ ch;

$\}$

$//$close the files

inorderFile.close$()$;

levelorderFile.close$()$;

encodedFile.close$()$;

$//$build the decoding tree

HuffNode $*$root $=$ createTreeFromInAndLevel$($inorder$,$ levelorder$)$;

$//$decode the message

HuffNode $*$q $=$ root;

for $($int i $=0$; i $<mtext></mtext><mi>(</mi>$int$)$encoded$.$length$()$; i$++)\{$

$//$read the encoded bit

char dir $=$ encoded$[$i$]$;

$//$zero $==$ move left

if $($dir $==\text{'}0\text{'})\{$

q $=$ q$->$left;

$\}//1==$ move right

else if $($dir $==\text{'}1\text{'})\{$

q $=$ q$->$right;

$\}$

$//$if leaf node print the char and return to root

if $($q$->$val $<mtext></mtext><mn>1</mn><mn>2</mn><mn>8</mn><mi>)</mi><mtext></mtext><mi>\{</mi>$

char ascii $=($char$)$q$->$val;

cout $$ ascii;

q $=$ root;

$\}$

$\}$

$//$cout $$ endl;

return $0$;

$\}$