霍夫曼树

霍夫曼树

给定n个权值1作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

构成哈夫曼树的思路

  • 从小到大进行排序，将每一个数据，每个数据都是一个结点，每个结点可以看成是一颗最简单的二叉树
  • 取出根结点权值最小的两颗二叉树
  • 组成一颗新的二叉树，该新的二叉树的根结点的权值是前面两个二叉树根结点权值的和
  • 再将这颗新的二叉树，以根结点的权值大小再次排序，不断重复1-2-3-4的步骤，直到数列中所有数据都被处理，就得到一颗哈夫曼树。
赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码
本站总访问量次 |

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

永远保持对技术的那颗追求的心。