[Data Structure] Creation and Basic Application of Huffman Tree

Hits: 0

[Generate Huffman] binary tree according to the given n weights , output Huffman code and decode

[The structure of] the nodes of the Huffman tree[]

struct  huffmannode //The structure of the Huffman tree node
{ 
    int weight; //Node weight

    int parent; //parent node

    int leftchild; //left subtree

    int rightchild;  //right subtree 
};

build

void  creat_tree ( huffmannode tree[], int w[], int n ) //Build Huffman tree
{
    int node1 = 0, node2 = 0;

    for ( int i= 0 ;i< 2 *n -1 ;++i) //initialize the node
    {
        tree[i].parent = -1;

        tree[i].leftchild = -1;

        tree[i].rightchild = -1;
    }

    for ( int i= 0 ;i<n;++i) //Enter the input node value into the Huffman tree
    {
        tree[i].weight = w[i];
    }

    for(int k=n;k<2*n-1;++k)
    {
        select (tree,k,node1,node2); //find the smallest node, the second smallest node

        tree[k].weight = tree[node1].weight + tree[node2].weight; //Generate a new node, the weight is the sum of the two nodes

        tree[node1].parent = k; //The parent node of the smallest node is the new node

        tree[node2].parent = k; //The parent node of the secondary node is the new node

        tree[k].leftchild = node1; //The left subtree of the new node is the smallest node

        tree[k].rightchild = node2; //The right subtree of the new node is the secondary node
    }
}

Idea: Put the first input nodes into the list of nodes to be selected, continuously select the nodes with the smallest weight and the next smallest weight , use them to generate new nodes, and make the new nodes their parent nodes, and then The new node is also put into the list of nodes to be selected, until n-1 nodes are newly generated , at this time the parent node is also the root node, and finally these 2*n-1 nodes become Huffman tree.

The lookup function used when building the tree

void  select (huffmannode tree[], int k, int &node1, int &node2) //In the nodes that have not been used, find the two nodes with the smallest weight
 {
    node1 = -1 , node2 = -1 ; //Initialize the position of the two smallest nodes without parent nodes

    int minweight = 1e8 ; //Initialize the minimum weight

    for(int i=0;i<k;++i)
    {
        if (tree[i].parent== -1 ) //no parent node
        {
            if (tree[i].weight<minweight) //less than the minimum weight
            {
                minweight = tree[i].weight; //Update the minimum weight

                node1 = i; //Update the minimum point position
            }
        }
    }

    minweight = 1e8 ; //Initialize the weight

    for(int i=0;i<k;++i)
    {
        if (tree[i].parent== -1 &&i!=node1) //No parent node and not the smallest node
        {
            if (tree[i].weight<minweight) //Update the secondary node
            {
                minweight = tree[i].weight;

                node2 = i;
            }
        }
    }
}

Idea: traverse twice, the first time finds the point that is not connected to the parent node and has the smallest weight , and marks it as node1; the second time, finds the point that is not connected to the parent node and has the smallest weight except node1, and marks it as node1 Marked as node2.

Generate the Huffman code corresponding to the node

void form_code(huffmannode tree[],int n) //Generate Huffman code
{
    int cur, parent, start;

    string huffcode;

    for (int i= 0 ;i<n;++i) //traverse n input nodes
    {
        cur = i;

        parent = tree[i].parent;

        while ( parent != -1 ) //When the root node is not reached, look up the parent node
        {
            if (tree[ parent ].leftchild==cur) //If the current node is the left subtree
            {
                huffcode = '0' + huffcode; //add 0 before Huffman code
            }
            else
            {
                huffcode = '1' + huffcode; //add 1
            }

            cur = parent ; //Update the current node

            parent = tree[ parent ]. parent ; //Update the parent node
        }

        code[tree[i].weight] = huffcode; //Save the generated Huffman code with map

        translate[huffcode] = ch[i]; //Save the value corresponding to the Huffman code

        huffcode.clear(); //Clear Huffman code
    }
}

Idea: Take the n input nodes as the starting point, and keep looking up its parent node until the parent node reaches the root node . If the current node is the left child node for the parent node, then in Add 0 before the generated Huffman code, and add 1 if it is a right child node. Use the map container to save the encoding after generating the complete encoding.

full code

#include<iostream>
#include<cstdio>
#include<string>
#include<map>

using namespace std;

const int Size = 1e4+5;

struct  huffmannode //The structure of the Huffman tree node
{ 
    int weight; //Node weight

    int parent; //parent node

    int leftchild; //left subtree

    int rightchild;  //right subtree
};

map < int , string > code; //Save the Huffman code corresponding to the value

map < string , char > translate; //Save the value corresponding to Huffman encoding

map<char,int> alp;

char ch[105];

int w[105];

void  select (huffmannode tree[], int k, int &node1, int &node2) //In the nodes that have not been used, find the two nodes with the smallest weight
 {
    node1 = -1 , node2 = -1 ; //Initialize the position of the two smallest nodes without parent nodes

    int minweight = 1e8 ; //Initialize the minimum weight

    for(int i=0;i<k;++i)
    {
        if (tree[i].parent== -1 ) //no parent node
        {
            if (tree[i].weight<minweight) //less than the minimum weight
            {
                minweight = tree[i].weight; //Update the minimum weight

                node1 = i; //Update the minimum point position
            }
        }
    }

    minweight = 1e8 ; //Initialize the weight

    for(int i=0;i<k;++i)
    {
        if (tree[i].parent== -1 &&i!=node1) //No parent node and not the smallest node
        {
            if (tree[i].weight<minweight) //Update the secondary node
            {
                minweight = tree[i].weight;

                node2 = i;
            }
        }
    }
}

void  creat_tree (huffmannode tree[], int w[], int n) //Builder
 {
     int node1 = 0 , node2 = 0 ;

    for ( int i= 0 ;i< 2 *n -1 ;++i) //initialize the node
    {
        tree[i].parent = -1;

        tree[i].leftchild = -1;

        tree[i].rightchild = -1;
    }

    for ( int i= 0 ;i<n;++i) //Enter the input node value into the Huffman tree
    {
        tree[i].weight = w[i];
    }

    for(int k=n;k<2*n-1;++k)
    {
        select(tree,k,node1,node2); //find the smallest node, the second smallest node

        tree[k].weight = tree[node1].weight + tree[node2].weight; //Generate a new node, the weight is the sum of the two nodes

        tree[node1].parent = k; //The parent node of the smallest node is the new node

        tree[node2].parent = k; //The parent node of the secondary node is the new node

        tree[k].leftchild = node1; //The left subtree of the new node is the smallest node

        tree[k].rightchild = node2; //The right subtree of the new node is the secondary node
    }
}

void  form_code (huffmannode tree[], int n) //Generate Huffman code
 {
     int cur, parent, start;

    string huffcode;

    for ( int i= 0 ;i<n;++i) //traverse n input nodes
    {
        cur = i;

        parent = tree[i].parent;

        while (parent!= -1 ) //When the root node is not reached, look up the parent node
        {
            if (tree[parent].leftchild==cur) //If the current node is the left subtree
            {
                huffcode = '0' + huffcode; //add 0 before Huffman code
            }
            else
            {
                huffcode = '1' + huffcode; //add 1
            }

            cur = parent; //update the current node

            parent = tree[parent].parent; //Update the parent node
        }

        code[tree[i].weight] = huffcode; //Save the generated Huffman code with map

        translate[huffcode] = ch[i]; //Save the value corresponding to the Huffman code

        huffcode.clear(); //Clear Huffman code
    }
}

void  print_code (huffmannode tree[], int n) //Output
 {
     cout << "The obtained Huffman value is" << endl ;

    for(int i=0;i<n;++i)
    {
    }
}

void  translate_code ( string unknown) //translation code
 {
     string s;

    for ( int i= 0 ;i<unknown.size();++i) //Read in unknown code
    {
        s = s + unknown[i];

        if (translate[s]!= 0 ) //The read part successfully matches the existing encoding
        {
            cout << translate[s]; //Output the corresponding value

            s.clear(); //Clear the read part
        }
    }

    cout << endl;
}

void  translate_string ( string unknown) //encoded string
 {  
     for ( int i= 0 ;i<unknown.size();++i) //read unknown encoding
    {
        cout << code[alp[unknown[i]]];
    }

    cout << endl;
}

int main()
{
    int n;

    cout << "Please enter the number of nodes (decoding process)" << endl ;

    cin >> n; 

    cout << "Please enter the characters and values ​​of each node" << endl ;

    for(int i=0;i<n;++i)
    {
        cin >> ch[i];

        cin >> w[i];

        alp[ch[i]] = w[i];
    }

    huffmannode *tree = new huffmannode[2*n-1];

    creat_tree(tree,w,n);

    form_code(tree,n);

    print_code(tree,n);

    string unknown;

    cout << "Please enter a 01 string to be translated (decoding process)" << endl ;

    cin >> unknown;

    cout << "The translation result is"   << endl ;

    translate_code(unknown);

    cout << "Please enter a string (encoding process)" << endl ;

    cin >> unknown;

    cout << "The result of transcoding is" << endl ;

    translate_string(unknown);

    return 0;   
}

You may also like...

Leave a Reply

Your email address will not be published.