Code:
//========================================================
// CHARACTER METHODS
//========================================================
Symbol::Symbol() {
Parent = NULL;
LeftChild = NULL;
RightChild = NULL;
Probability=0;
Character='\0';
Mark = false;
CodeBit[0] = '\0';
Depth = 1;
}
//==========================================
Symbol::Symbol(char InputChar, float InputProb) {
Parent = NULL;
LeftChild = NULL;
RightChild = NULL;
Mark = false;
CodeBit[0] = '\0';
Depth = 1;
Character = InputChar;
Probability = InputProb;
}
//==========================================
Symbol::~Symbol() {;}
//========================================================
// TREE METHODS
//========================================================
Tree::Tree() {
Root = NULL;
Count=0;
PtrCurrent=Root;
Depth=0;
BranchCounter=0;
}
//==========================================
Tree::~Tree() { //Delete all Character objects before
//Destruction
}
//========================================================
//INSERTSYMBOL IS USED BY THE LIST TREE TO CONSTRUCT
//A LINKED LIST OF SYMBOLS. FOR THIS PURPOSE, IT USES
//THE LEFTCHILD POINTERS TO POINT TO THE NEXT ENTRY AND
//PARENT POINTERS TO POINT TO THE LAST ENTRY
void Tree::insertSymbol(char MyCharacter, float MyProb){
Symbol *Ptr = new Symbol(MyCharacter,MyProb);
assert (Ptr !=NULL);
Ptr->LeftChild = Root;
Root->Parent = Ptr;
Root = Ptr;
Count++;
//Watch for special case of an empty tree
if (Root == NULL) {
Root = PtrCurrent = Ptr;
return;
}
return;
}
//==========================================
//THIS OVERLOADED METHOD IS USED TO INSERT A SYMBOL
//OBJECT INTO THE HUFFMAN TREE
void Tree::insertSymbol(Symbol *Symbol1, Symbol *Symbol2) {
Symbol *Nanny = new Symbol();
Nanny->LeftChild = Symbol1;
Nanny->RightChild = Symbol2;
Symbol1->Parent = Symbol2->Parent = Nanny;
Nanny->Probability = Symbol1->Probability + Symbol2->Probability;
BranchCounter++;
if (BranchCounter==1)
Root=Nanny;
if (BranchCounter>=2) {
Symbol *NewRoot=new Symbol();
NewRoot->LeftChild=Root;
NewRoot->RightChild=Nanny;
Nanny->Parent = Root->Parent = NewRoot;
NewRoot->Probability = Root->Probability + Nanny->Probability;
Root=NewRoot;
}
}
//==========================================
//THIS OVERLOADED METHOD IS USED TO INSERT A SYMBOL
//OBJECT INTO THE HUFFMAN TREE
void Tree::insertSymbol(Symbol *Symbol1) {
Symbol *NewRoot = new Symbol;
NewRoot->LeftChild = Root;
NewRoot->RightChild = Symbol1;
Root->Parent = Symbol1->Parent = NewRoot;
NewRoot->Probability = Symbol1->Probability + Root->Probability;
BranchCounter++;
Root=NewRoot;
}
//==========================================
int Tree::showLength(void){
return Count;
}
//==========================================
void Tree::displayTree() {
for (Symbol *Ptr=Root; Ptr; Ptr=Ptr->LeftChild)
cout << Ptr->Character << " " << Ptr->Probability << " ";
cout << endl;
}
//==========================================
//FINDLOW FINDS THE LOWEST UNMARKED SYMBOL IN THE LIST.
//IF ALL SYMBOLS ARE USED UP (I.E. MARKED), IT RETURNS
//-1. OTHERWISE IT RETURNS 0
int Tree::findLow() {
Symbol *Ptr = Root;
bool FoundFlag = false;
float LowValue = 1;
while (Ptr != NULL) {
if ((Ptr->Probability<=LowValue) && (Ptr->Mark==false)) {
FoundFlag = true;
PtrCurrent=Ptr;
LowValue = Ptr->Probability;
}
Ptr=Ptr->LeftChild;
}
if (FoundFlag == true)
return 0;
else
return -1;
}
//==========================================
int Tree::markSymbol(){
if (PtrCurrent == NULL)
return -1;
else {
PtrCurrent->Mark = true;
return 0;
}
}
//==========================================
Symbol* Tree::removeSymbol(){
Symbol *Tmp;
if (Root == NULL) //Is the list empty?
return 0;
if ((PtrCurrent->Mark != true) || (PtrCurrent == NULL))
return 0;
//EXTRICATE SYMBOL FROM LIST TREE
Tmp = PtrCurrent;
if (PtrCurrent != Root)
PtrCurrent->LeftChild->Parent = PtrCurrent->Parent;
else {
PtrCurrent->LeftChild->Parent=NULL;
Root=PtrCurrent->LeftChild;
}
PtrCurrent->Parent->LeftChild = PtrCurrent->LeftChild;
PtrCurrent->Parent=PtrCurrent->LeftChild = NULL;
PtrCurrent = NULL;
return Tmp;
}
//==========================================
void Tree::moveSymbols(Tree *HuffmanTree){
Symbol *Symbol1=NULL, *Symbol2=NULL;
int Length=this->showLength();
while (Length > 1) {
if (findLow()) {
Symbol1=NULL;
cerr << "Error: Lowest value not found" << endl;
}
else {
markSymbol();
Symbol1=removeSymbol();
Length--;
}
if (findLow()){
Symbol2=NULL;
cerr << "Error: Lowest value not found" << endl;
}
else{
markSymbol();
Symbol2=removeSymbol();
Length--;
}
HuffmanTree->insertSymbol(Symbol1,Symbol2);
}
if (Length == 1) {
if (!findLow())
cerr << "Error: Last element not found!" << endl;
markSymbol();
Symbol1=removeSymbol();
Length--;
HuffmanTree->insertSymbol(Symbol1);
}
return;
}
//==========================================
void Tree::printTree(){
Symbol *Current=Root;
if (Root != NULL) {
//Print Header
cout << "Char Probability Code Location Neighbours" \
<< endl;
printTree(Root->LeftChild);
printTree(Root->RightChild);
cout << hex;
cout <<setiosflags(ios::fixed | ios::showpoint | ios::internal);
cout << setiosflags(ios::unitbuf | ios::right);
cout << "\""<< setw(1) << Current->Character<<"\"";
if (Current->Character=='\0') cout << " ";
cout << setiosflags(ios::left);
cout << setw(12) << setprecision(7) << Current->Probability << " ";
cout << setw(17) << setfill(' ') << Current->CodeBit;
cout << " " << hex << Current;
cout << " " << hex << Current->Parent << " " << Current->LeftChild;
cout << " " << Current->RightChild << dec << endl;
}
return;
}
//==========================================
void Tree::printTree(Symbol *Current){
if (Current != NULL) {
printTree(Current->LeftChild);
printTree(Current->RightChild);
cout << hex;
cout <<setiosflags(ios::fixed | ios::showpoint | ios::internal);
cout << setiosflags(ios::unitbuf | ios::right);
cout << "\""<< setw(1) << Current->Character<<"\"";
if (Current->Character=='\0') cout << " ";
cout << setiosflags(ios::left);
cout << setw(12) << setprecision(7) << Current->Probability << " ";
cout << setw(17) << setfill(' ') << Current->CodeBit;
cout << " " << hex << Current;
cout << " " << hex << Current->Parent << " " << Current->LeftChild;
cout << " " << Current->RightChild << dec << endl;
}
return;
}
//==========================================
void Tree::assignBits(){
if (Root != NULL) {
assignBits(Root->LeftChild,"0");
assignBits(Root->RightChild,"1");
}
return;
}
//==========================================
void Tree::assignBits(Symbol *Current, char *BitSet){
char BitBuffer[16];
BitBuffer[0]='\0';
strcat(BitBuffer,BitSet);
if (Current != NULL) {
strcpy(Current->CodeBit,BitSet);
assignBits(Current->LeftChild,strcat(BitBuffer,"0"));
BitBuffer[0]='\0';
strcat(BitBuffer,BitSet);
assignBits(Current->RightChild,strcat(BitBuffer,"1"));
}
return;
}
//==========================================
void Tree::writeTable(ofstream *OUTPUT){
Symbol *Current=Root;
if (Root !=NULL) {
if (Current->Character!='\0'){
*OUTPUT << Current->Character << " " << Current->CodeBit << endl;
}
writeTable(OUTPUT,Current->LeftChild);
writeTable(OUTPUT,Current->RightChild);
}
}
//==========================================
void Tree::writeTable(ofstream *OUTPUT,Symbol* Current){
if (Current !=NULL) {
if (Current->Character!='\0')
*OUTPUT << Current->Character << " " << Current->CodeBit << endl;
this->writeTable(OUTPUT,Current->LeftChild);
this->writeTable(OUTPUT,Current->RightChild);
}
}
huffman.zip [2]