C++ to achieve Huffman tree simple creation and traversal methods

In this paper, the method of simple creation and traversal of Huffman tree is described in the form of an example, which is a classical C++ algorithm.

The function of this example is: given n nodes with weight, how to construct a binary tree of n leaf nodes with given weight, so as to minimize WPL with full path length.

The optimal tree algorithm is constructed as follows:

Huffman algorithm:

1. Set n weights as w1,w2,w3... Wn -1, wn nodes are sorted by increasing weight, and each weight is treated as a binary tree. Constitute n binary tree forest F={T1,T2,T3,T4... Tn}, where each binary tree has only one weight and the left and right words are empty

2. In forest F, the root node weight least-binary tree is selected to form a new binary tree as the number of words left and right, and the root node of the new binary tree is
Its left and right word weight sum, in which the leaves are the original tree

3. Delete the two trees in forest F, and add the newly acquired binary trees to forest F instead of the two trees, so that the number of binary trees in the forest is one less than before

4. Repeat 2 and 3 for the new forest until there is only one tree in the forest, and that tree is the Huffman tree.

#include <iostream>
using namespace std;
#define LEAFNUM 10        //The number of leaf nodes, the weight tree
#define HUFNUM 2*LEAFNUM
#define MAXWEIGHT 999.9
//********** storage structure *********** **
class HufTree;
//***** Node**********
class NODE
{
private:
 char Data;          //The data domain of the node
 double Weight;   //The weight range of the node
 int Lchild,Rchild,Parent;   //Node left child right child and parent fields
public:
 NODE()            //The constructor
 {
 Data = '0';
 Weight = 0;
 Lchild = -1;
 Rchild = -1;
 Parent = -1;        //Initialize the data for the node
 }
 int Re_L(){return Lchild;}
 int Re_R(){return Rchild;}
 char Re_Data(){return Data;}
 double Re_Weight(){return Weight;}
 friend class HufTree;     //Declare a friend
};//Node

//HufTree class * * * * * * * * * * * * * * * * * *
class HufTree
{
private:
 int NodeNum;
 NODE HufArry[HUFNUM];
public:
 HufTree(){NodeNum = 0;}
 void SetHuf(int,double,char);   //Set weights and data fields
 void CreatHuf();          //Create a Huffman tree
 void SelectMin(int,int&,int&);   //Find the two least weighted trees of Huffman tree
 void Find_Root_and_Print();       //Find the root node location
 void PrintHuf(int);          //Traverse the Huffman tree
};//huftree
 
void HufTree::SetHuf(int i,double wei,char ch)
{
 HufArry[i].Data = ch;
 HufArry[i].Weight = wei;
}
void HufTree::CreatHuf()
{
 cout<<" Query the location of the two smallest trees at a time :"<<endl;
 for(int i = LEAFNUM; i < HUFNUM - 1; i++)
 {
 int p1 = 0;
 int p2 = 0;
 SelectMin(i,p1,p2);           //Find the two trees with the least weight of the current tree species
 cout<<p1<<"   < - >    "<<p2<<endl;
 HufArry[p1].Parent = i;   //Set the parents of the two smallest trees
 HufArry[p2].Parent = i;
 HufArry[i].Lchild = p1;   //Sets the weight of the root of the 3-node tree and the child
 HufArry[i].Rchild = p2;   
 HufArry[i].Weight = HufArry[p1].Weight + HufArry[p2].Weight;
 }
 cout<<"************************"<<endl;
}
void HufTree::SelectMin(int i,int &p1,int &p2)
{
 int least1 = MAXWEIGHT;
 int least2 = MAXWEIGHT;
 for(int j = 0; j < i; j++)
 {
 if(HufArry[j].Parent == -1)
 {
  
  if(HufArry[j].Weight < least1)
  {
  least2 = least1;
  least1 = HufArry[j].Weight;
  p2 = p1;
  p1 = j;
  }
  else
  {
  if(HufArry[j].Weight < least2)
  {
   least2 = HufArry[j].Weight;
   p2 = j;
  }
  }
 }
 }
}
void HufTree::Find_Root_and_Print()
{
 int root;
 for(int i = 0; i < HUFNUM - 1; i++)
 {
 if(HufArry[i].Parent == -1)
 {
  root = i;
  break;
 }
 }
 PrintHuf(root);
}
void HufTree::PrintHuf(int position)
{
 if(NodeNum == LEAFNUM)
 {
 
 return;
 }
 else
 {
 if(HufArry[position].Data != '0') //If it's a leaf node
 {
  cout<<" A weight :"<<HufArry[position].Weight<<"<->  data :"<<HufArry[position].Data<<"  This node is a leaf "<<endl;
  NodeNum = NodeNum + 1;
 }
 else
 {
  cout<<" A weight :"<<HufArry[position].Weight<<"  This node has no data domain , Not a leaf "<<endl;
  PrintHuf(HufArry[position].Lchild);
  PrintHuf(HufArry[position].Rchild);
 }
 }
 
  
}
int main()
{
 HufTree Tree;
 cout<<" Please enter the "<<LEAFNUM<<" right ( A weight , data ):"<<endl;
 double wei;
 char ch;
 for(int i = 0; i < LEAFNUM; i++)
 {
 cin>>wei;
 cin>>ch;
 Tree.SetHuf(i,wei,ch);
 }
 Tree.CreatHuf();     //Create a Huffman tree
 Tree.Find_Root_and_Print();           //Traverse the Huffman tree
 return 0;
}

Test results:

1 a
2 b
5 c
7 d
4 e
13 f
3 g
6 h
11 i
8 l