This code in C++ is supposed to take in characters that are in main and take their frequencies and build a Huffman tree out of them. I started building the build tree function but I couldn't finish it and the others I'm really unsure about. The other member functions im unsure about are the generate code, list codes, write codes, compress and decompress. If I could get some help building the rest of my functions it would be greatly appreciated. Thank you

EXAMPLE OUTPUT:

Another more clear example output(These are with different values other than the code supplies):

Huffman Codes

a 000010

b 0010

c 00000

d 00110

e 00111

f 0001

g 000011

m 01

y 1

Huffman Tree Index ch freq left right parent numBits bitCode

0 a 26 -1 -1 9 6 000010

1 b 139 -1 -1 13 4 0010

2 c 42 -1 -1 10 5 00000

3 d 88 -1 -1 11 5 00110

4 e 98 -1 -1 11 5 00111

5 f 121 -1 -1 12 4 0001

6 g 35 -1 -1 9 6 000011

7 m 999 -1 -1 15 2 01

8 y 1999 -1 -1 16 1 1

9 61 0 6 10 0

10 103 2 9 12 0

11 186 3 4 13 0

12 224 10 5 14 0

13 325 1 11 14 0

14 549 12 13 15 0

15 1548 4 7 16 0

16 3547 15 8 0 0

Compress bad = 001000001000110

Decompress 011 = my

huffman.h:

#ifndef HUFFMAN_H_INCLUDED #define HUFFMAN_H_INCLUDED

#include #include #include #include

#include "huffnode.h"

using namespace std;

class huffman {

public:

huffman();

void buildTree(const string& characters, const vector& charFreq); void generateCodes(); void listCodes(); void writeTree(); string Compress(string str); string Decompress(string bits);

private:

int numChars; int numLeaves; int treeSize;

//Huffman tree is stored in a vector of huffNode's vector tree; //Vector holding the locations of the characters (leaf nodes) in the Huffman tree vector charLoc;

//String of characters used to generate the Huffman tree string characters; //Corresponding frequencies for the characters vector charFreq;

};

huffman::huffman() { numChars = 0; numLeaves = 0; treeSize = 0; charLoc.resize(256); //chracters = "abcdef"; //charFreq = (16,4,8,6,20,3); //characters = "";

}

void huffman::buildTree(const string& chars, const vector& freqs) { characters = chars; charFreq=freqs; numChars = characters.size(); numLeaves=numChars; treeSize=2*numLeaves-1; tree.resize(treeSize); //priority queue used to build Huffman tree priority_queue, greater > huffPQ; int i, nodeIndex; huffNode hNode; nodeIndex = 0; for(i=0; i { hNode.ch = characters[i]; hNode.left = NIL; hNode.right = NIL; hNode.freq = charFreq[i]; hNode.index = nodeIndex; charLoc[(unsigned char)characters[i]] = nodeIndex; hNode.parent = 0; hNode.numBits = 0; hNode.bitCode = ""; huffPQ.push(hNode); tree[i]=hNode; nodeIndex++; }

huffNode x, y; for(i=1;i { x= huffPQ.top(); huffPQ.pop(); y= huffPQ.top(); huffPQ.pop();

hNode.ch=0; hNode.left=x.index; hNode.right=y.index; hNode.freq=x.freq + y.freq; hNode.index=nodeIndex; hNode.parent=0;

tree[nodeIndex]=hNode; nodeIndex++; }

}

void huffman::generateCodes() {

}

void huffman::listCodes() {

}

void huffman::writeTree() {

}

string huffman::Compress(string str) {

}

string huffman::Decompress(string bits) {

}

#endif // HUFFMAN_H_INCLUDED

huffNode.h:

#ifndef HUFFNODE_H_INCLUDED #define HUFFNODE_H_INCLUDED

#include

using namespace std;

//NIL represents empty subtree const short NIL = -1;

class huffNode { public:

unsigned char ch; short left, right; int freq; int index; int parent; int numBits; string bitCode;

huffNode();

friend bool operator> (huffNode lhs, huffNode rhs); };

huffNode::huffNode() { ch = 0; left = NIL; right = NIL; freq = 0; index = 0; parent = 0; numBits = 0; bitCode = ""; }

bool operator>(huffNode lhs, huffNode rhs) { return lhs.freq > rhs.freq; }

#endif // HUFFNODE_H_INCLUDED

main:

#include #include #include #include #include

#include "huffnode.h" #include "huffman.h"

using namespace std;

int main() { string characters; vector charFreq; characters = "etaoinsrhldcu"; charFreq = {125,93,80,76,73,71,65,61,55,41,40,31,27};

huffman huff1;

huff1.buildTree(characters, charFreq);

huff1.generateCodes();

huff1.listCodes();

huff1.writeTree();

string charStr, bitCode; charStr = "end"; //bitCode = huff1.Compress(charStr); cout

bitCode = "100010101010101000"; //charStr = huff1.Decompress(bitCode); cout

//Keep Console window open until keyboard input int hold; cin >> hold; }

1. ;seat tarter-at areat twist lat * area sz R> era ttle erse i ese 1. ;seat tarter-at areat twist lat * area sz R> era ttle erse i ese