哈夫曼編碼

等長(zhǎng)編碼：占的位置一樣

變長(zhǎng)編碼（不等長(zhǎng)編碼）：經(jīng)常使用的編碼比較短，不常用的比較短

最優(yōu)：總長(zhǎng)度最短

最優(yōu)的要求：占用空間盡可能短，不占用多余空間，且不能有二義性

這里給出哈夫曼二叉樹(shù)的實(shí)現(xiàn)：

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

測(cè)試數(shù)據(jù)（主函數(shù)）：

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

運(yùn)行結(jié)果截圖：

如果發(fā)現(xiàn)文章中有錯(cuò)誤，還請(qǐng)大家指出來(lái)，我會(huì)非常虛心地學(xué)習(xí)，我們一起進(jìn)步?。?！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-586015.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法】哈夫曼編碼（最優(yōu)二叉樹(shù)實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！