第十五章 数据结构 哈夫曼树
哈夫曼树的基本概念
在T集合中选取最小和次小的两棵二叉树作为左，右子树。
例题：构造哈夫曼树 + 实例
在解决电文传输中，加快输出速度，我们可以使用哈夫曼树。
●由此可见:设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，设计一棵哈夫曼树，由此得到的二进制前缀编码便称为哈夫曼编码。
哈夫曼编码-哈夫曼树(最优二叉树)的应用
最优二叉树解决问题
.数据的最小冗余编码问题
.译码的唯一性问题
关于哈夫曼编码的结论
判断是否为哈夫曼编码
不可能出现一个字符的哈夫曼编码是另一个字符哈夫曼编码的前缀
常用换算
哈夫曼编码树中没有度为1的结点。设叶子结点的个数为n,则哈夫曼编码树的结点总数为2n - 1.
哈夫曼树最典型、最广泛的应用是在编码技术上。利用哈夫曼树，构造所得的哈弗曼编码是一种最优前缀编码。
每个树节点有两个指针，99个节点共有198个指针，除了没有指针指向根节点，其余节点都有一个指针指过去，这样就有98个指针被使用，所以还剩100个指针未使用。