首页 > 其他 > 详细

哈弗曼树

时间:2020-05-17 19:09:02      阅读:45      评论:0      收藏:0      [点我收藏+]

路径:从一个节点到达另一个节点的分支序列

路径长度:路径上分支的条数称为路径长度

数据路径长度:从树根到每个节点的路径长度之和

节点的权:给树中节点赋予一个数值,该数值叫做节点的权

带权路径长度:节点到树根之间的路径长度与节点的权的乘积

树的带权路径长度(WPL):树中所有叶子节点的带权路径之和

最优二叉树(又称哈夫曼树):在叶子节点数n以及各叶子节点的权值Wk确定的前提下,树的带权路径长度WPL值最小的二叉树称为最优二叉树

哈夫曼树的存储结构一般使用静态三叉链表来存储

哈夫曼树的特点:没有度数为1的节点,又称为正则二叉树

n 个叶子节点的哈夫曼树,度数为2的节点数为你n-1个,所以哈夫曼树一共有2n-1个节点

前缀编码:同一字符集中任何一个字符的编码都不是另一个字符编码的前缀(最左字串)

哈弗曼树

原文:https://www.cnblogs.com/ykq188/p/12906180.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!