哈夫曼树以及哈夫曼编码的问题

  今天看到一个哈夫曼编码的题目，给定一个字符串abcdabaa，问哈夫曼编码后的二进制串的总长度是多少，答案是14

  对于哈夫曼树我是一点都不了解啊，所以一顿查找，总结出以下知识点，与大家分享：当然部分内容参考了下百度

  哈夫曼树又称为最优二叉树，是一种带权路径最短的二叉树。哈夫曼树是二叉树的一种应用，在信息检索中很常用。

  一些相关的概念：

1、节点之间的路径长度：从一个节点到另一个节点之间的分支数量称为两个节点之间的路径长度。

2、树的路径长度：从根节点到树中每一个节点的路径长度之和。

3、节点的带权路径长度：从该节点到根节点之间的路径长度与节点的权的乘积。

4、树的带权路径长度：树中所有叶子节点的带权路径长度之和。

   带权路径最小的二叉树被称为哈夫曼树或最优二叉树。

对于哈夫曼树，有一个很重要的定理：对于具有n个叶子节点的哈夫曼树，一共需要2*n-1个节点。

  这个定理的解释如下：对于二叉树来说，有三种类型节点，即度数（只算出度）为2的节点，度数为1的节点和度数为0的叶节点。而哈夫曼树的非叶子节点是由两个节点生成的，因此不能出现度数为1的节点，而生成的非叶子节点的个数为叶子节点个数减一，于此定理就得证了。

构造哈夫曼树的算法如下：

海外公司注册、海外银行开户、跨境平台代入驻、VAT、EPR等知识和在线办理：https://www.xlkjsw.com

原标题：哈夫曼树以及哈夫曼编码的问题

关键词：编码