数据结构_树_哈夫曼树

github地址：
https://github.com/arkulo56/thought/blob/master/software/dataStruct/数据结构树哈夫曼树.md

哈夫曼树

权值越大的叶子越靠近根，带权路径越短！

  1. 路径：节点到另一个节点间之间边的数量
  2. 树的路径长度：根到每个叶子节点的路径之和
  3. 叶子的带权路径：根到叶子节点的路径*权重
  4. 树的带权路径长度（WPL）：各叶子结点带权路径之和

用途

  1. 数据权重越高，从根节点到其叶子结点的路径也越短，效率越高
  2. 数据压缩：数据发送越频繁的数据元素，权重越高，则其编码越短

构造

https://raw.githubusercontent.com/arkulo56/thought/master/images/datastruct/huffman.png
https://raw.githubusercontent.com/arkulo56/thought/master/images/datastruct/huffman.png
  1. 将带权重的数据按照权重由小到大进行排序
  2. 然后取出最小的两个数据，按照左小右大的原则进行生成，根为N，根的权重为两个叶子数据权重之和
  3. 循环步骤2，再拿出一个数据和N1进行对比权重，然后生成树结构
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 关于B树的一些总结(一)
    B树的定义 一棵m阶的B树满足下列条件： 树中每个结点至多有m个孩子。 除根结点和叶子结点外，其它每个结点至少有m...
    文档随手记阅读 14,585评论 0赞 25
  • 《大话数据结构》总结
    第一章 绪论 什么是数据结构？ 数据结构的定义：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 第二章...
    SeanCheney阅读 11,099评论 0赞 19
  • 数据结构与算法 —— 05 树
    1.树(Tree): 树是 n(n>=0) 个结点的有限集。当 n=0 时称为空树。在任意一颗非空树中：有且仅有一...
    ql2012jz阅读 4,751评论 0赞 3
  • B树（转）
    原文链接 B树 1.前言： 动态查找树主要有：二叉查找树（Binary Search Tree），平衡二叉查找树（...
    非典型程序员阅读 4,897评论 0赞 3
  • <<大话数据结构>>之浅谈哈夫曼树
    你比他好一点，他不会承认你，反而会嫉妒你，只有你比他好很多，他才会承认你，然后还会很崇拜你，所以要做，就一定要比别...
    神经骚栋阅读 7,525评论 5赞 13