建设银行交罚款网站,平面设计培训学校推荐,厦门做商城网站,鹰潭市网站建设公司哈夫曼树 哈夫曼树的相关概念构造哈夫曼树基础算法 哈夫曼编码 哈夫曼树的相关概念
结点的权#xff1a;有某种现实含义的数值。结点的带权路径长度#xff1a;从树的根结点到该结点的路径长度#xff08;经过的边数#xff09;与该结点上权值的乘积。树的带权路径长度有某种现实含义的数值。结点的带权路径长度从树的根结点到该结点的路径长度经过的边数与该结点上权值的乘积。树的带权路径长度树中所有叶节点的带权路径长度之和WPL只算叶子结点的不算分支的。
树的带权路径长度图解 哈夫曼树在含有n个带权叶节点的二叉树中其中WPL最小的二叉树为哈夫曼树也称最优二叉树。
构造哈夫曼树
基础算法
给定n个权值的结点
将这n个结点分别作为n棵仅含一个结点的二叉树构成森林F。构造一个新结点从F中选取两棵结点权值最小的数作为新结点的左、右子树并且将新结点的权值置为左、右子树上根结点的权值之和。从F中删除刚才选出的两棵树同时将新得到的树加入F中。重复2、3直至F中之剩下一棵树为止。
哈夫曼树的结论
每个手术室结点最终都将成为叶节点且权值越小的结点到根结点的路径长度越大哈曼夫树的结点总数为2n-1哈曼夫树不存在度为1的结点哈曼夫树并不唯一左右顺序任意但WPL必然相同且为最优
哈夫曼编码
采用哈夫曼树的性质构成的编码。 将字符集中的每个字符作为一个叶子结点各个字符出现的频度最为结点的权值根据之前介绍的方法构造哈夫曼树。 采用0、1来表示。
图示
