数据结构(Java版)哈夫曼(Haffman)树及其应用

哈夫曼(Haffman)树及其应用主要内容•基本概念•何为哈夫曼树？•哈夫曼编码•项目实践：哈夫曼编码应用程序（求通讯编码）基本概念•路径长度：从树中一个结点另一个结点所经过的分支序列构成这两个结点之间的路径，路径上的分支数目称为路径长度。•树的路径长度：从树的根结点到树中每个叶子结点的路径长度之和称为该树的路径长度。•结点的带权路径长度：从该结点到树的根结点之间路径长度与该结点上权值的乘积。•树的带权路径长度：树中所有叶子结点的带权路径长度之和称为树的带权路径长度。•最优二叉树：带权路径最小的二叉树称为最优二叉树。如何计算二叉树的带权路径长度•设二叉树具有n个带权的叶子结点，那么从根结点到各叶子结点的路径长度与相应叶子结点权值的乘积之和就叫做二叉树的带权路径长度(WPL)。•n•WPL=∑WK.LK•k=1•其中：•WK为第k个叶子结点的权值•LK为第k个叶子结点到根结点的路径长度计算二叉树的带权路径长度举例(a)WPL=2*2+3*2+5*2+9*2=38(b)WPL=2*3+3*3+5*2+9*1=34(c)WPL=9*3+5*3+3*2+2*1=50(d)WPL=2*2+5*3+3*3+9*1=37•四个图的叶子结点具有相同的权值，由于其构成的形态不同，所以它们的带权路径长度也不同。•权值越大的叶子结点越靠近根结点，权值越小的叶子结点越远离根结点，这种二叉树的WPL就越小。•WPL最小的二叉树就是最优二叉树何为哈夫曼树？•最优二叉树就是哈夫曼树。因为构成最优二叉树的方法是由D.Haffman最早提出的，所以又称为哈夫曼树。•在分析一些决策判定问题的时候，利用哈夫曼树可以获得最佳的决策算法。哈夫曼树的构成•问题：给定n个权值｛w1,w2,…wn｝，求由这n个值作为叶子权值的哈夫曼树。•基本思想：(1)由给定的n个权值｛w1,w2,…wn｝构造n棵只有一个叶子结点的二叉树，，从而得到一个二叉树的集合F=｛T1,T2,…Tn｝；(2)在F中选取根结点的权值最小和次小的两棵树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；(3)在F中删除作为新二叉树左、右子树的那两棵子树，并将这棵新二叉树加入到森林F中。(4)重复步骤（2）和（3）,当森林F中只剩下一棵二叉树时，这棵二叉树就是所要求的哈夫曼树。哈夫曼树的构成举例•给定一组叶子权值｛1，3，5，7｝，由此权值构造哈夫曼树的过程如下：哈夫曼树应用•在数据通讯中，经常需要将传送的文字转换为二进制字符0和1组成的二进制串，这样的二进制串称之为通讯编码。•如果在编码时考虑字符在整个电文中出现的频率，让出现频率高的字符尽可能采用短的编码，出现频率低的字符采用稍长一点的编码，这样电文要传送的总代码就会比较短，从而能节省数据传送的时间。•哈夫曼树可用于解决最优化问题。由哈夫曼树构造一组不等长的通讯编码，这是一种使电文编码总长最短的编码方案，这样由哈夫曼树构造的通讯编码称为哈夫曼编码。哈夫曼编码构造方法•设需要编码的字符集合为｛d1,d2,…dn｝,它们在电文中出现的频率集合为｛w1,w2,…wn｝，则构造哈夫曼编码的步骤为：•1）以d1,d2,…dn作为叶子结点，w1,w2,…wn作为它们的权值，构造哈夫曼树•2）在哈夫曼树上求叶子结点的编码。规定哈夫曼树中的左分支代表0，右分支代表1，则从根结点到每个叶子结点所经过路径分支上的0和1所组成的序列就是该结点对应字符的通讯编码。哈夫曼编码构造举例•假设一段电文传送的字符为A,B,C,D,E,F组成，其每个字符在电文中出现的频率分别为6，5，4，3，2，1.试构造一组通讯编码。哈夫曼编码如下：A=10B=01C-00D=110E=1111F=1110[i]weightlChildrChildparentflag06-1-19115-1-18124-1-18133-1-17142-1-16151-1-16163547176369189211019120710110218900程序分析•定义哈夫曼树结点类HaffNode•定义哈夫曼编码类Code•哈夫曼树类HaffmanTree•使用哈夫曼树求哈夫曼编码项目拓展•99页实战演练