【数据结构与算法】哈夫曼编码（最优二叉树）实现

哈夫曼编码

等长编码：占的位置一样

变长编码（不等长编码）：经常使用的编码比较短，不常用的比较短

最优：总长度最短

最优的要求：占用空间尽可能短，不占用多余空间，且不能有二义性

这里给出哈夫曼二叉树的实现：

HuffmanTree.h:

#pragma once

template <typename T>
class HuffmanTree {
public:
    HuffmanTree(int nCount, T* InData, int* InWeight);
private:
    typedef struct _HuffNode {
        T tValue;
        int weight;
        int n_lChild;
        int n_rChild;
        int n_Father;
    }Tree, *pTree;
    pTree m_pTreeRoot;
    int nTreeCount;
public:
    void show();
    void HuffmanCode(char** &InHuffmanCode,int nCount);
private:
    void select(int nCount, int* SmallValueA_Index, int* SmallValueB_Index);
};

template<typename T>
inline HuffmanTree<T>::HuffmanTree(int nCount, T * InData, int* InWeight)
{
    nTreeCount = 2 * nCount;
    m_pTreeRoot = (pTree)calloc(nTreeCount + 1, sizeof(Tree));
    for (size_t i = 1; i <= nCount; i++) {
        m_pTreeRoot[i].tValue = InData[i-1];
        m_pTreeRoot[i].weight = InWeight[i-1];
    }
    for (size_t i = nCount + 1; i < nTreeCount; i++) {
        int SmallValueA_Index;
        int SmallValueB_Index;
        select(i - 1, &SmallValueA_Index, &SmallValueB_Index);
        m_pTreeRoot[SmallValueA_Index].n_Father = i;
        m_pTreeRoot[SmallValueB_Index].n_Father = i;
        m_pTreeRoot[i].n_lChild = SmallValueA_Index;
        m_pTreeRoot[i].n_rChild = SmallValueB_Index;
        m_pTreeRoot[i].weight = m_pTreeRoot[SmallValueA_Index].weight + m_pTreeRoot[SmallValueB_Index].weight;
        m_pTreeRoot[i].tValue = '0';
    }

}

template<typename T>
inline void HuffmanTree<T>::show()
{
    std::cout << "Index" << "   " << "Value" << "   " << "weight" << "   " << "ParentIndex" << "   " << "lChild" << "   " << "rChild" << "   " << std::endl;
    for (size_t i = 1; i < nTreeCount; i++) {
        printf("%-5.0d   %-5c   %-6d   %-11d   %-6d    %-6d\r\n", i, m_pTreeRoot[i].tValue, m_pTreeRoot[i].weight, m_pTreeRoot[i].n_Father, m_pTreeRoot[i].n_lChild, m_pTreeRoot[i].n_rChild); 
    }
}

template<typename T>
inline void HuffmanTree<T>::HuffmanCode(char **& InHuffmanCode, int nCount)
{
    InHuffmanCode = (char**)malloc(sizeof(char*)*(nCount + 1));
    char* code = (char*)malloc(nCount);
    code[nCount-1] = '\0';
    for (size_t i = 1; i <= nCount; i++) {
        int cha = i;
        int parent = m_pTreeRoot[i].n_Father;
        int start = nCount - 1;
        while (parent) {
            if (m_pTreeRoot[parent].n_lChild == cha) {
                code[--start] = '0';
            }
            else {
                code[--start] = '1';
            }
            cha = parent;
            parent = m_pTreeRoot[parent].n_Father;
        }
        InHuffmanCode[i] = (char*)malloc(nCount - start);
        strcpy(InHuffmanCode[i], &code[start]);
    }
}



template<typename T>
inline void HuffmanTree<T>::select(int nCount, int * SmallValueA_Index, int * SmallValueB_Index)
{
    int nMin;
    for (size_t i = 1; i < nCount; i++) {
        if (m_pTreeRoot[i].n_Father == 0) {
            nMin = i;
            break;
        }
    }
    for (size_t i = nMin + 1; i <= nCount; i++) {
        if (m_pTreeRoot[i].n_Father == 0 && m_pTreeRoot[i].weight < m_pTreeRoot[nMin].weight) {
            nMin = i;
        }
    }
    *SmallValueA_Index = nMin;
    for (size_t i = 1; i <= nCount; i++)
    {
        if (m_pTreeRoot[i].n_Father == 0 && i != *SmallValueA_Index)
        {
            nMin = i;
            break;
        }
    }
    for (size_t i = nMin + 1; i <= nCount; i++)
    {
        if (m_pTreeRoot[i].n_Father == 0 && m_pTreeRoot[i].weight < m_pTreeRoot[nMin].weight &&  i != *SmallValueA_Index)
        {
            nMin = i;
        }
    }
    *SmallValueB_Index = nMin;
}

测试数据（主函数）：

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include "HuffmanTree.h"

int main() {
	char a[] = { 'A','B','C','D','E','F' };
	int b[] = { 5,32,18,7,25,13 };
	HuffmanTree<char> arr(6, a, b);
	arr.show();
	char** HuffmanCode = nullptr;
	arr.HuffmanCode(HuffmanCode,6);
	std::cout << "编码值：" << std::endl;
	for (size_t i = 1; i <= 6; i++)
	{
		printf("  %c:   %s\n",a[i-1],HuffmanCode[i]);
	}
	return 0;
}