哈夫曼编码（代码实现）

在我们有了建立哈夫曼树的能力之后，其实哈夫曼编码十分好实现，我们只需要一次遍历便可以将所有的哈夫曼编码集合成一个哈夫曼编码表了，具体代码如下。

//建立哈夫曼编码节点
//为了方便建立，这里使用的链表结构
struct haffMapNode      
{
    char symbol;       //实际字符
    string code;          //对应编码
    haffMapNode* next;
};

//头结点
struct haffMap
{
    haffMapNode* head;
};

//递归遍历二叉树
void travelHaffTree(haffMap* (&mapHead),haffTree* tree,string code)
{
//传入一个code来记录遍历的编码
    if(tree->lChild == NULL && tree->rChild == NULL)
    {
//当到最后的叶子节点的时候，这就是我们需要编码的字符
        haffMapNode* node = new haffMapNode;
        node->code = code;
        node->symbol = tree->symbol;
        node->next = NULL;

//链表插入
        if(mapHead->head == NULL)
        {
            mapHead->head = node;
        }
        else
        {
            node->next = mapHead->head;
            mapHead->head = node;
        }
    }
//当左子树不为NULL时，说明可以向左走，code追加‘0’
    if(tree->lChild != NULL)
    {
        code.push_back('0');
        travelHaffTree(mapHead,tree->lChild,code);
        code.pop_back();           //清除之前追加的字符，为了不影响之后向右走(在同一层中)
    }
//同理 
    if(tree->rChild != NULL)
    {
        code.push_back('1');
        travelHaffTree(mapHead,tree->rChild,code);
        code.pop_back();
    }
}

//建立哈夫曼编码图
haffMap* creataHaffMap(haffTreeRoot* root)
{
    haffMap* mapHead = new haffMap;
    mapHead->head = NULL;

    string code;

    travelHaffTree(mapHead,root->next,code);
    return mapHead;
}

这就是简单的建立哈夫曼编码图的方法。