Implementation of Huffman tree for C + + data structure and algorithm

This paper illustrates the implementation of the Huffman tree for C + + data structure and algorithm. I will share it with you for your reference as follows:

Huffman tree, also known as the optimal two-fork tree, is a kind of tree with the shortest weight path length.

For the optimal two-fork tree, the nodes with larger weight are closer to the root of the tree, and the nodes with smaller weight are further away from the root of the tree.

The principle of the Huffman tree and the implementation method of java are described in detail. Here we will have a look at the implementation method of C++.

The specific code is as follows:

#include <iostream>
using namespace std;
#if !defined(_HUFFMANTREE_H_)
#define _HUFFMANTREE_H_
/*
 *  Huffman tree structure 
 */
class HuffmanTree
{
public:
  unsigned int Weight;
  unsigned int Parent;
  unsigned int lChild;
  unsigned int rChild;
};
typedef char **HuffmanCode;
/*
 *  Select the two nodes with the least weight from the node set 
 *  Assign values to s1 and s2
 */
void Select(HuffmanTree* HT,int Count,int *s1,int *s2)
{
  unsigned int temp1=0;
  unsigned int temp2=0;
  unsigned int temp3;
  for(int i=1;i<=Count;i++)
  {
    if(HT[i].Parent==0)
    {
      if(temp1==0)
      {
        temp1=HT[i].Weight;
        (*s1)=i;
      }
      else
      {
        if(temp2==0)
        {
          temp2=HT[i].Weight;
          (*s2)=i;
          if(temp2<temp1)
          {
            temp3=temp2;
            temp2=temp1;
            temp1=temp3;
            temp3=(*s2);
            (*s2)=(*s1);
            (*s1)=temp3;
          }
        }
        else
        {
          if(HT[i].Weight<temp1)
          {
            temp2=temp1;
            temp1=HT[i].Weight;
            (*s2)=(*s1);
            (*s1)=i;
          }
          if(HT[i].Weight>temp1&&HT[i].Weight<temp2)
          {
            temp2=HT[i].Weight;
            (*s2)=i;
          }
        }
      }
    }
  }
}
/*
 *  Huffman coding function 
 */
void HuffmanCoding(HuffmanTree * HT,
          HuffmanCode * HC,
          int *Weight,
          int Count)
{
  int i;
  int s1,s2;
  int TotalLength;
  char* cd;
  unsigned int c;
  unsigned int f;
  int start;
  if(Count<=1) return;
  TotalLength=Count*2-1;
  HT = new HuffmanTree[(TotalLength+1)*sizeof(HuffmanTree)];
  for(i=1;i<=Count;i++)
  {
    HT[i].Parent=0;
    HT[i].rChild=0;
    HT[i].lChild=0;
    HT[i].Weight=(*Weight);
    Weight++;
  }
  for(i=Count+1;i<=TotalLength;i++)
  {
    HT[i].Weight=0;
    HT[i].Parent=0;
    HT[i].lChild=0;
    HT[i].rChild=0;
  }
  // Build Huffman trees 
  for(i=Count+1;i<=TotalLength;++i)
  {
    Select(HT, i-1, &s1, &s2);
    HT[s1].Parent = i;
    HT[s2].Parent = i;
    HT[i].lChild = s1;
    HT[i].rChild = s2;
    HT[i].Weight = HT[s1].Weight + HT[s2].Weight;
  }
  // Output Huffman coding 
  (*HC)=(HuffmanCode)malloc((Count+1)*sizeof(char*));
  cd = new char[Count*sizeof(char)];
  cd[Count-1]='\0';
  for(i=1;i<=Count;++i)
  {
    start=Count-1;
    for(c = i,f = HT[i].Parent; f != 0; c = f, f = HT[f].Parent)
    {
      if(HT[f].lChild == c)
        cd[--start]='0';
      else
        cd[--start]='1';
      (*HC)[i] = new char [(Count-start)*sizeof(char)];
      strcpy((*HC)[i], &cd[start]);
    }
  }
  delete [] HT;
  delete [] cd;
}
/*
 *  Look for a character in a string 
 *  If found, it returns its location 
 */
int LookFor(char *str, char letter, int count)
{
  int i;
  for(i=0;i<count;i++)
  {
    if(str[i]==letter) return i;
  }
  return -1;
}
void OutputWeight(char *Data,int Length,
         char **WhatLetter,
         int **Weight,int *Count)
{
  int i;
  char* Letter = new char[Length];
  int* LetterCount = new int[Length];
  int AllCount=0;
  int Index;
  int Sum=0;
  float Persent=0;
  for(i=0;i<Length;i++)
  {
    if(i==0)
    {
      Letter[0]=Data[i];
      LetterCount[0]=1;
      AllCount++;
    }
    else
    {
      Index=LookFor(Letter,Data[i],AllCount);
      if(Index==-1)
      {
        Letter[AllCount]=Data[i];
        LetterCount[AllCount]=1;
        AllCount++;
      }
      else
      {
        LetterCount[Index]++;
      }
    }
  }
  for(i=0;i<AllCount;i++)
  {
    Sum=Sum+LetterCount[i];
  }
  (*Weight) = new int[AllCount];
  (*WhatLetter) = new char[AllCount];
  for(i=0;i<AllCount;i++)
  {
    Persent=(float)LetterCount[i]/(float)Sum;
    (*Weight)[i]=(int)(1000*Persent);
    (*WhatLetter)[i]=Letter[i];
  }
  (*Count)=AllCount;
  delete [] Letter;
  delete [] LetterCount;
}
#endif
void main()
{
  HuffmanTree * HT = NULL;
  HuffmanCode HC;
  char Data[100];
  char *WhatLetter;
  int *Weight;
  int Count;
  cout<<" Please enter the 1 Line text data :"<<endl;
  cin>>Data;
  cout<<endl;
  OutputWeight(Data,strlen(Data),
    &WhatLetter,
    &Weight,
    &Count);
  HuffmanCoding(HT, &HC, Weight, Count);
  cout<<" character   frequency   Coding results "<<endl;
  for(int i = 0; i<Count; i++)
  {
    cout<<WhatLetter[i]<<"   ";
    cout<<Weight[i]/1000.0<<"%\t";
    cout<<HC[i+1]<<endl;
  }
  cout<<endl;
}

I hope this article is helpful to you C++ programming.