THE FOLLOWING PROGRAM DEALS WITH BINARY TREES TO DETERMINE LENGTH ENCODINGS/DECODINGS. THIS PROGRAMS NEEDS A MAIN PROGRAM THAT BUILDS A HUFFMAN CODING TREE, ENCODE STRINGS, AND DECODE BIT STRINGS STARTING WITH A SET OF LETTERS AND THEIR CORRESPONDING FREQUENCIES.

EX. ENCODING STRINGS: STINT, SINE
DECODING STRINGS: 100101010001011, 10101001101001

THE HUFFMAN CODING TRE MENU CHOICES IN THE MAIN PROGRAM SHOULD BE...
(E) ENCODE A FILE
ASK THE NAME OF THE FILE THAT CONTAINS THE INFO. ITS TO ENCODE/DECODE
ASK THE NAME OF THE FILE THAT WILL HOLD THE RESULTS
(D) DECODE A FILE
ASK THE NAME OF THE FILE THAT CONTAINS THE INFO. ITS TO ENCODE/DECODE
ASK THE NAME OF THE FILE THAT WILL HOLD THE RESULTS
OUTPUT THE RESULTS OF THE ENCODING/DECODING TO CORRECT FILE
(I) OUTPUT AN INORDER TRAVERSAL OF THE HUFFMAN CODING TREE
(M) OUTPUT A PRINT OF THE FREQUENCY MATRIX
(E) THE PROGRAM SHOULD LOOP UNTIL THE USER WISHES TO QUIT

--------------------------------------------------------------------------------
#include "huffnode.h"
#include <iostream.h>
#include <stdlib.h>

HuffNode::HuffNode (const int value, int aValue, HuffNode *leftChild, HuffNode *rightChild)
{
freq = value;
ASCIINumber = aValue;
left = leftChild;
right = rightChild;
}

HuffNode::HuffNode ()
{
freq = -1;
ASCIINumber = aValue;
left = NULL;
right = NULL;
}

HuffNode::~HuffNode ()
{
if (left != NULL)
{
delete left;

}

if (right != NULL)
{
delete right;
}
freq = -1;
ASCIINumber = -1;
}

void HuffNode::setLeft (HuffNode *leftChild)
{
left = leftChild;
return;
}

void HuffNode::setRight (HuffNode *rightChild)
{
right = rightChild;
return;
}

void HuffNode::setFreq (int entry)
{
freq = entry;
return;
}

void HuffNode::setANumber (int value)
{
ASCIINumber = aValue;
return;
}

int HuffNode::getANumber ()
{
return ASCIINumber;
}

int HuffNode::getFreq()
{
return freq;
}

//The following is the old Bintree code. may need to be changed
void HuffNode :: add (int newValue)
{
if(newValue == contents){
return;
}

else if(newValue < contents){
if(left != NULL){
left->add(newValue); // add to the left
} // Create the left subtree
else{
if(right != NULL){ // add to the right
right->add(newValue); // add to the right subtree
}
else{
right=new HuffNode (newValue);
}
}
return;
}

void HuffNode :: preorder() const
{
cout << contents << endl;
if(left != NULL){
left->preorder();
}
if(right != NULL){
right->preorder();
}
return;
}

void HuffNode :: inorder() const
{
if(left != NULL){
left->inorder();
}
cout << contents << endl;
if(right != NULL){
right->inorder;
}
return;
}

void HuffNode :: postorder() const
{
if(left != NULL){
left->postorder();
}
if(right != NULL){
right->postorder();
}
cout << contents << endl;





return;
}

bool HuffNode::includes (int searchValue)
{
if (contents == searchValue)
{
return true;
}
else if (contents < searchValue)
{
if (right != NULL)
{
return right->includes (searchValue);
}else
{
return false;
}
}else {
if (left != NULL)
{
return left->includes (searchValue);
}else
{
return false;
}
}
}

int max (int a, int b)
{
return a > b ? a : b;
}

int HuffNode::height () const
{
int leftHeight, rightHeight;

if (left == NULL)
{
leftHeight = 0;
}
else {
leftHeight = left->height ();
}
if (right == NULL){
rightHeight = 0;
}
else {
rightHeight = right->height ();
}

return max (rightHeight = right->height () + 1;
}

huffnode.h
#ifndef huffNode_h
#define huffNode_h
#include <stdlib.h>

class HuffNode
{
private:
int freq;
int ASCIINumber;
HuffNode *left;
HuffNode *right;

public:
HuffNode (const int value, int aValue = -1, HuffNode *leftChild = NULL,
HuffNode *rightChild = NULL);

HuffNode ();
~HuffNode ();

void setLeft (HuffNode *leftChild);
void setRight (HuffNode *rightChild);
void setFreq (int entry);
void setANumber (int value);
int getANumber ();
int getFreq ();

// BinTree codes
void add (HuffNode *leftNode, HuffNode *rightNode);
void preorder () const;
void inorder () const;
void postorder () const;
void includes (int searchValue);
int height () const;
};
#endif

linkeditem.cpp
#include <iostream.h>
#include <string.h>
#include <iomanip.h>

#include "LinkedItem.h"



LinkedItem* LinkedItem::getNext()
{
return link;
}
HuffNode* LinkedItem::getTreePtr()
{
return treePtr;
}
int LinkedItem::getFreq()
{
return freq;
}
char* LinkedItem::getLetter()
{
return letter;
}
void LinkedItem::setNext (LinkedItem *next)
{
link = next;
return;
}
void LinkedItem::setFreq (int entry)
{
freq = entry;
return;
}
void LinkedItem::setLetter (char entry [])
{
strcpy (letter, entry);
return;
}
void LinkedItem::setTreePtr (HuffNode *hnode)
{
treePtr = hnode;
return;
}
LinkedItem::LinkedItem ()
{
freq = -1;
letter = -1;
link = -1;
treePtr = -1;
}


LinkedItem::~LinkedItem()
{
freq = -1;
letter = NULL;
link = NULL;
treePtr = NULL;
}

bool LinkedItem:perator!= (LinkedItem v)const
{
if (strncmp (v.letter, letter, 1) == 0)
return false;
else
return true;
}

bool LinkedItem:perator == (LinkedItem v) const
{
return !(operator != v);
}

bool LinkedItem:perator>(LinkedItem v)const
{
if (freq > v.freq)
return false;
else
return true;
}
/*
ostream& operator<< (ostream& ostr, const LinkedItem& source)
{

ostr << setw(7) << source.data << endl;

return ostr;

}



/*

* >> overload defines standard input method for item.

* Args: istr input stream

* target location to store input

* Return: input stream

*/

/*
istream& operator>> (istream& istr, LinkedItem& target)

{

istr >> target.letter >> target.freq;

// return istr;

}
*/

likeditem.h
#ifndef __LINKITEM_H__
#define __LINKITEM_H__

#include <iostream.h>
#include <stdlib.h>
#include "HuffNode.h"class LinkedItem {
private:
int freq;
char letter [10];

HuffNode *treePtr;
LinkedItem *link;
public:
LinkedItem();
~LinkedItem();

//
// To allow the user to use the links...
//
LinkedItem *getNext();
HuffNode *getTreePtr();
int getFreq();
char* getLetter ();

void setNext (LinkedItem *next);
void setTreePtr (HuffNode *Node);
void setFreq (int entry);
void setLetter (char entry []);

bool operator > (LinkedItem v) const;
bool operator== (LinkedItem v) const;
bool operator!= (LinkedItem v) const;
//bool operator>(LinkedItem v)const;
// I/O Friend Operators
/*
friend ostream& operator<< (ostream& ostr, const LinkedItem& source); friend istream& operator>> (istream& istr, LinkedItem& target);
*/
};
#endif

hufffreq.dat
10 2184
13 2184
32 1293934
33 31069
34 470
35 1
36 1
37 1
38 21
39 31069
40 628
41 629
42 63
43 1
44 83174
45 8074
46 78025
47 5
48 299
49 928
50 366
51 330
52 93
53 82
54 63
55 41
56 40
57 948
58 1827
59 17199
60 468
61 1
62 441
63 10476
64 8
65 44486
66 15413
67 21497
68 15683
69 42583
70 11713
71 11164
72 18462
73 55806
74 2067
75 6196
76 23858
77 15872
78 27338
79 33209
80 11939
81 1178
82 28970
83 34011
84 39800
85 14129
86 3580
87 16496
88 606
89 9099
90 532
91 2085
92 1
93 2077
94 1
95 71
96 1
97 244664
98 46543
99 66688
100 133779
101 404621
102 68803
103 57035
104 218406
105 198184
106 2712
107 29212
108 146161
109 95580
110 215924
111 281391
112 46525
113 2404
114 208894
115 214978
116 289975
117 114818
118 33969
119 72894
120 4688
121 85271
122 1099
123 2
124 33
125 2
126 1