数据结构实验六:哈夫曼树

一、实验目的

1、进一步掌握指针变量、动态变量的含义。

2、掌握二叉树的结构特性，以及各种存储结构的特点和适用范围。

3、最优二叉树(哈夫曼树)的创建。

4、哈夫曼编码算法。
二、实验内容
1、构造最优二叉树
2、实现哈夫曼编码算法
三、实验步骤
1、理解最优二叉树并创建
2、理解哈夫曼编码的主要思想
3、根据哈夫曼树实现哈夫曼编码
四、代码实现

#include <iostream>
#include <cstring>
#include <string>

using namespace std;

typedef struct HuffListNode//使用单链表完成哈夫曼树
{
    int HuffData;
    int loc;//表示叶子节点的字母在字母表中的位置（其他点为0）

    HuffListNode* LChild;
    HuffListNode* RChild;
    HuffListNode* next;

}HuffListNode, *Huff;

char message[105];

HuffListNode* HuffListInit()
{
    HuffListNode* head = new HuffListNode();
    head->HuffData = 0;
    head->loc = 0;
    head->LChild = NULL;
    head->RChild = NULL;
    head->next = NULL;
    return head;
}

void HuffListInsert(Huff& head, Huff& insNode)
{
    HuffListNode* now = head->next;
    HuffListNode* nowPri = head;
    while (now && insNode->HuffData > now->HuffData)
    {
        now = now->next;
        nowPri = nowPri->next;
    }
    insNode->next = now;
    nowPri->next = insNode;
}

void AHuffmanWork(Huff& head)//取出链表中前两个元素并合并
{
    Huff LNode = head->next;
    Huff RNode = head->next->next;
    
    head->next = head->next->next->next;
    LNode->next = NULL;
    RNode->next = NULL;

    Huff newNode = HuffListInit();
    newNode->LChild = LNode;
    newNode->RChild = RNode;
    newNode->HuffData = LNode->HuffData + RNode->HuffData;

    HuffListInsert(head, newNode);
}

void MyDelete(Huff now)
{
    if (!now->LChild && !now->RChild)
    {
        delete now;
        return;
    }
    if (now->LChild) MyDelete(now->LChild);
    if (now->RChild) MyDelete(now->RChild);
}

void HuffDelete(Huff& head)
{
    MyDelete(head->next);
    delete head;
}

int AlphaBet[27];//记录每个小写字母出现的次数
string ciphertext[27];

void getCode(Huff now, string HuffCode)//遍历哈夫曼树根节点到叶子节点的所有路径求哈夫曼编码
{
    if (!now->LChild && !now->RChild)
    {
        ciphertext[now->loc] = HuffCode;
        return;
    }
    if (now->LChild) getCode(now->LChild, HuffCode + '0');
    if (now->RChild) getCode(now->RChild, HuffCode + '1');
}


int main()
{
    printf("请输入要翻译的报文（只输入小写字母）：\n");
    scanf("%s", message);

    memset(AlphaBet, 0, sizeof(AlphaBet));
    for (int i = 0; i < strlen(message); i++)
        AlphaBet[message[i] - 96]++;

    Huff head = HuffListInit();
    int tot = 0;
    for (int i = 1; i <= 26; i++)
    if (AlphaBet[i])
    {
        tot++;
        Huff now = new HuffListNode();
        now->HuffData = AlphaBet[i];
        now->loc = i;
        HuffListInsert(head, now);
    }

    for (int i = 1; i <= tot - 1; i++)
        AHuffmanWork(head);

    getCode(head->next, "");

    cout << "哈夫曼编码:\n";
    for (int i = 1; i <= 26; i++)
    if (AlphaBet[i])
    {
        if (tot != 1)
            cout << (char)(i + 96) << " : " << ciphertext[i] << endl;
        else
            cout << (char)(i + 96) << " : " << '1' << endl;//只有一个数的话随便取0或1编码就ok了
    }

    HuffDelete(head);
}

五、实验难点
1、构造最优二叉树的方法
目的：使带权值的结点都是叶子结点，权值越小的结点，其到根结点的路径越长。
(1) 将每个带有权值的结点作为一棵仅有根结点的二叉树，树的权值为结点的权值；
(2) 将其中两棵权值最小的树组成一棵新二叉树，新树的权值为两棵树的权值之和；
(3) 重复(2)，直到所有结点都在一棵二叉树上。这棵二叉树就是最优二叉树。
2、哈夫曼编码的实现
主要思想：从根节点出发递归生成哈夫曼编码（初值为空字符串），向左分支走向编码中加入’0’，向右分支走向编码中加入’1’。
例如实现aabbe的哈夫曼编码：

则a的哈夫曼编码为：0；b的哈夫曼编码为：11；a的哈夫曼编码为：10；
哈夫曼树结点的结构包括数据域（节点的权值以及用于表示叶子节点对应字母的值）、左右孩子、next指针。其中next指针是用于单链表的实现（平时求哈夫曼树时是把当前权值从小到大排成一排去求，这也是为什么想到要用单链表，然后因为某个权值有可能是一棵子树的树根了，所以加入了LChild和RChild来表示这样的子树）
六、运行程序
省略

七、实验心得
关于哈夫曼编码的讨论：我们说，哈夫曼编码的目的是为了让原文以最简短的方式加密发出去，那么有一个问题，我们在拿到加密后的文章以及哈夫曼编码表（里面有所有字符的哈夫曼编码）后有没有办法将这篇密文唯一还原呢？其实是有的。这也和哈夫曼编码的来源有关，哈夫曼编码其实也就是对哈夫曼树求出从根节点到叶子节点的路径后，根据路径中是往左儿子走还是往右儿子走给出一个编码。这也就决定了一点，即任意两个哈夫曼编码互相不为对方的前缀。这说明了什么呢？说明当我们从第一个字符开始翻译时，只要读到当前的编码串和我们已知的哈夫曼编码表中任意一个编码相对应，即可判断出这段当前编码串所表示的内容就是编码表中对应编码对应的字母。这么做是正确的是因为第一个字母的密文一定会在密文一开始就出现，并且没有任何哈夫曼编码是另一个哈夫曼编码的前缀，所以你再往后读是读不出任何信息的，所以这就是我们要从密文找出的哈夫曼编码。那既然这样，我们找出了一个编码后可以直接从密文的下一个字符开始找哈夫曼编码表中的编码，如此往复，直到翻译完整个密文即可。
在建立好赫夫曼树后求赫夫曼编码有不同方法，其中一种是先找到叶子结点(左右孩子均为0的结点)，再根据其双亲结点逐步找到根结点来求赫夫曼编码；另一种是由根结点出发，依次查找其左右孩子，直到找到叶子结点来求赫夫曼编码。最优二叉树除了叶子结点就是度为2的结点，没有度为1的结点，这样才使得树的带权路径长度最短。根据二叉树的性质可以得到最优二叉树的结点数为叶子数的2倍减1。当二叉树所有结点的权值相同，最优二叉树就成为完全二叉树的形状。通过本次实验，掌握了最优二叉树的基本操作和应用，以及各种存储结构的特点和适用范围，并对课上学习的一些知识进行了加深。