首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 ># 赫夫曼树

# 赫夫曼树

作者头像
用户1175783
发布2019-09-10 14:38:34
4480
发布2019-09-10 14:38:34
举报

# 赫夫曼树

赫夫曼树也叫做最优二叉树。

# 名词解释

由2,3,5,6,8构成的最优二叉树,如下图:

* **节点的权:**叶子节点的值

* **路径:**叶子结点与父节点的距离为1

* **路径长度:**指根节点到叶子节点的长度

* **带权的路径长度:**路径长度*节点的权

* **最优二叉树:**树的带权路径长度为树中所有叶子结点的带权路径长度之和最小。

# 原理

  1. 首先要求集合有序
  2. 取集合的两个最小值作为叶子节点,相加后得到的值插入有序集合,并删除原来的两个值
  3. 重复2步骤,直到集合只剩一下一个根元素即成为一颗二叉树,这就是最优二叉树

# 最优N叉树

# 原理

  1. 首先要求集合有序
  2. 取最小的n个节点作为叶子节点,相加后得到的值插入有序集合,并删除原来的n个值
  3. 重复2步骤,直到集合只剩下一个根元素即成为一颗n叉树,前3步同最优二叉树的步骤一样
  4. 遍历节点判断是不是标准的n叉树(有孙子节点的节点必须有n个子)
  5. 取孙子节点的最大节点补充该节点
  6. 重复4,5步骤,直到所有有孙子节点的节点都有n个子节点,即完整的n叉树,也是最优n叉树

# 原理图

构建一颗三叉树,重复步骤1,2,3

取孙子节点补齐98的子节点个数

补齐节点31的子节点

排序98的子节点,因为3个子都是节点类型,所以只排孙子节点就行了

重复步骤4,5,直到所有的节点都是有序的三叉树,最后即得最优三叉树。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019-08-30,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • # 赫夫曼树
    • # 名词解释
      • # 原理
      • # 最优N叉树
        • # 原理
          • # 原理图
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档