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);
		}
	}