哈夫曼树编码

type

status

date

slug

summary

功能需求

设计并实现一个写一个哈夫曼码的编/译码系统，系统功能包括：

（1）I：初始化（Initialization）。

从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中；

（2）E：编码（Encoding）。

利用以建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中；

（3）D：译码（Decoding）。

利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中；

（4）P：打印代码文件（Print）。

将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中；

（5）T：印哈夫曼树（Tree printing）。

将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。

界面需求

打印出哈弗曼编码指令的界面，并显示程序进程与错误信息，编码解码与树的界面打印信息。

概要设计

代码实现

必要库引入

宏变量定义

基本数据结构定义

我们需要定义哈夫曼树节点，每个节点存储对应的元素及权值，同时存储他的左右子节点，由于后面要用到队列指针，同时也需要存储后节点

定义优先队列，后续读取时需要用到

函数声明

后续会用到的所有函数如下

定位光标函数

调用库函数，实现光标定位，打印菜单

打印主页面菜单

调用光标位置函数打印具体功能，用户键入不同数字实现不同功能

哈夫曼树的实现

先放最后封装好的构建函数，接下来我们一步步看如何实现的

首先，用户输入要构建几个节点 n ，然后我们使用 for 循环持续读取 n 个节点信息，将节点信息存储起来。但是考虑到哈夫曼树的性质，我们夫节点绝对是大于子节点的 value 的，而我们用户输入的数据并不能保持有序性，可能是大小随机的，如 7、12、1、4、6 ，所以我们需要考虑将用户输入的数据进行统一的排列，此时就需要用到优先队列，我们可以将用户输入的每个节点都存储起来，构建优先队列，保持从小到大的顺序，如 1、4、6、7、12 ，这样我们在后续构建哈夫曼树时，可以依次取出最小的节点来构建

for 循环完成后我们成功构建出优先队列，此时开始构建哈夫曼树。我们将优先队列中的数值依次取出，构建节点，取出两个小节点后，将两个左右节点的数值相加得到父节点数值，再将父节点存入到优先队列，多次遍历后实现哈夫曼树的构建

接下来我们依次看各个函数的实现：

初始化优先队列

首先我们需要初始化优先队列，传入节点后先开辟内存空间，然后将队列的前指针和后指针都指向自身，置空节点的左右子节点及后节点

优先队列入队

然后要考虑怎么将节点插入进来，构建优先队列：

传入节点后，先将节点赋值，然后将节点的左右节点及后节点置空，然后在优先队列中寻找合适的位置，插入到合适顺序，保持优先队列由大到小排列

优先队列出队

和正常队列一样，取出头节点即可，记得判断是不是最后一个节点，如果是需要将头尾指针对齐

创建哈夫曼树节点

创建哈夫曼树节点，存储传入的元素及权值，注意将左右节点置空即可

将哈夫曼树节点入队

将哈夫曼树节点入队，插入到优先队列中即可，有同学可能会问，这为什么不调用之前的优先队列入队函数 offerQueue(LinkedQueue queue, T value, E element) 呢？

其实认真观察即可发现，在offerQueue 函数中，传入的value element 后，是重新新建了一个节点，如果我们调用这个方法，将无法保存我们在上一步构建的左右子节点关系，所以我们需要重新封装一个函数，传入我们的 node 节点进去来进入优先队列

构建哈夫曼树

最后将封装好的函数依次调用即可，整理后如下：

整体思路总结

至此，我们哈夫曼树的构建就算成功实现。我们再来整体复原一下思路：

第一步，我们需要构建优先队列，将用户输入的乱序的信息由小到大存储到优先队列中

第二步，我们每次用优先队列中取出最小的两个节点，将两节点的数值相加，构建出第三个父节点，并将其两节点拼接为左右字节点，再将父节点重新加入优先队列

然后重复第二步，即可完成哈夫曼树的构建

将哈夫曼树写入文件

由于题目要求，如果没有构建哈夫曼树需要支持从文件中提取，所以我们在构建成功后，还需要实现将哈夫曼树写入文件，这样才能在后续实现读取哈夫曼树

考虑到我们的构建哈夫曼树函数是依次取出最小的节点，然后构建父节点的流程，所以我们存储时，可以进行层序遍历哈夫曼树，将哈夫曼树按照层序遍历写入文件。我们同样构建一个优先队列，这里传入的 root 节点是已经构建好的哈夫曼树的根节点，我们从根节点开始依次将节点打印到文件中，然后将左右子树分别入队，再依次出队打印到文件中，即可实现将哈夫曼树写入文件的操作

队列入队操作

由于我们并不需要非常复杂的操作，仅仅使用队列节点的入队出队操作即可，所以单独封装出一个对 queue_p 使用的入队操作，出队操作一样所以不用更改

判断队列是否为空

层序遍历哈夫曼树写入文件

读取哈夫曼树

题目需要我们实现如果没有构建哈夫曼树则要能够从文件中读取，所以我们需要编写从文件中读取哈夫曼树的函数。

我们在构建哈夫曼树时已经实现了将其层序遍历存入到文件中，所以直接依次读取每行的 element value 即可，思路和构造哈夫曼树类似，分别存入优先队列，然后再依次取出两个小节点，构建父节点后再次入队，循环几次直到构建成功。

编码单个元素

哈夫曼树的编码，我们定义向左为0，向右为1，所以每个节点都可以被编码。我们从根节点开始依次递归遍历，如果遍历到要找到的元素，则返回 "" ，在遍历过程中，向左后拼接0，向右后拼接1

从文件中编码

我们从文件中读取到数据，首先检测文件是否为空，依次读取文件中的字符，然后依次编译元素。将编译好的元素写入到文件 CodeFile.txt 后，再将文件内容打印到控制台中，便于直观显示

译码文件

由于哈夫曼树的编码在文件中是以连续的长串字符存储的，如100101010011这样，所以我们需要根据一长串字符来译码存储的字符，思路为将字符存储到数组中，我们从根节点开始，如果字符串的字符为0，则将根节点向左走，若为1则向右走，直到没有子树说明单个字符译码完成，读取该字符即可

打印哈夫曼树

我们使用凹入表形式来打印哈夫曼树，可以直观的看到哈夫曼树的层级关系

使用前序遍历很容易实现，在进入左右子节点前，根据层级关系打印出-------，层级越低显示的---也就越少，表示为高层的子树

由于我们需要将哈夫曼树以凹入表形式写入文件中，但是我们又利用了递归调用，所以不能使用w+模式来打开文件，因为每次调用函数时都会清空原先内容再重新写入，但是我们使用a模式追写的话，每次运行一遍函数都会在文件内追写一次，我们只需要文件存入最后一次运行的哈夫曼树，所以我们就要考虑在每次运行前清空一次文件来实现功能

我们可以在外部调用此函数时，以w模式打开一次文件，再关闭，就可以实现清空文件的功能，然后再调用 PrePrint 功能，即可实现打印哈夫曼树到文件