哈夫曼树定义（哈夫曼树是二叉树吗）

本文目录

• 哈夫曼树是二叉树吗
• 最小生成树和哈夫曼树有什么区别
• 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近()
• 哈夫曼树的定义是：带权路径长度最小的二叉树 我先请问：为何它是带全路径长度最小的二叉树最小是
• 为什么 哈夫曼树的度只能为0或者2 不能为1
• 哈夫曼树！！与普通二叉树的区别是
• 哈夫曼树的基本概念是什么
• 哈夫曼树左小右大是指什么

哈夫曼树是二叉树吗

哈夫曼树来源于哈夫曼编码，哈夫曼编码其实不只是针对二进制，可以说任何进制都能使用哈夫曼编码（详见信息与编码相关书籍）。但是在计算机领域由于使用二进制，在数据结构上只介绍了二进制的哈夫曼编码，构造出来的哈夫曼树是度为二的树。
楼上，请问二叉树定义是什么？你的哈夫曼树分左右子树？

最小生成树和哈夫曼树有什么区别

最短路径和最小生成树是不同的概念.
最短路径是对于一个图的两个结点而言的.在一个图中,结点A通过某些结点和边可以走到结点B,那这些结点和边就组成一条A到B的路径,A到B的最短路径就是A到B的所有路径中边权值总和最小的那一条（或多条）.
最小生成树是对于一个图本身而言的.对于一个有n个结点的无向连通图（边没有方向,任意两点之间都存在路径可以到达）,必然可以去掉某些边,使得最终剩下n-1条边,并且n个结点仍然是连通的,这n个结点和n-1条边组成了原图的一个生成树,而最小生成树就是所有可能的生成树中n-1条边的权值总和最小的那一个（或多个）.
最短路径常用算法有：floyd,dijkstra,SPFA,A*等
最小生成树常用算法有：prim,kr***al

哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近()

这句话是错的。书上说过是带权路径最短的二叉树，以树表达与以二叉树表达完全不同。

在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

结点的权及带权路径长度若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

扩展资料：

哈夫曼树也可以是k叉的，只是在构造k叉哈夫曼树时需要先进行一些调整。构造哈夫曼树的思想是每次选k个权重最小的元素来合成一个新的元素，该元素权重为k个元素权重之和。但是当k大于2时，按照这个步骤做下去可能到最后剩下的元素少于k个。

对给定的n个权值构造k叉哈夫曼树时，可以先考虑增加一些权值为0的叶子节点，使得叶子节点总数为(k-1)nk+1这种形式，然后再按照哈夫曼树的方法进行构造即可。

哈夫曼树的定义是：带权路径长度最小的二叉树 我先请问：为何它是带全路径长度最小的二叉树最小是

只有带权路径长度最小的二叉树，才是哈夫曼树。当然是可以证明带权路径长度最小。

树的路径长度是从树根到树中每一结点的路径长度之和，在结点数目相同的二叉树中，完全二叉树的路径长度最短。

结点的权：在一些应用中，赋予树中结点的一个有某种意义的实数。

结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。

扩展资料：

哈夫曼树：所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。可以证明哈夫曼树的WPL是最小的。

为什么 哈夫曼树的度只能为0或者2 不能为1

因为哈夫曼树的定义是构造一棵最短的带权路径树，所以这种树为最优二叉树。最优二叉树的度只有0或者2。

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

扩展资料：

历史

1951年，哈夫曼在麻省理工学院（MIT）攻读博士学位，他和修读信息论课程的同学得选择是完成学期报告还是期末考试。

导师罗伯特·法诺（Robert Fano）出的学期报告题目是：查找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。

哈夫曼使用自底向上的方法构建二叉树，避免了次优算法香农-范诺编码（Shannon–Fano coding）的最大弊端──自顶向下构建树。

1952年，于论文《一种构建极小多余编码的方法》（A Method for the C***truction of Minimum-Redundancy Codes）中发表了这个编码方法。

哈夫曼树！！与普通二叉树的区别是

哈夫曼树针对带权值的问题，是一种特殊的二叉树。由哈夫曼树解出的编码不一定是理想中的最优解，但一定是实际可行的最优解。

哈夫曼树的基本概念是什么

（1）结点路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。

（2）路径长度：从一个结点到另一个结点所经过的分支数目。

（2）树的路径长度：从根结点到树中每一结点的路径长度之和。

（4）结点的权：赋予树中某结点的一个有某种意义的数量值。

（5）结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。

（6）树的带权路径长度：树中所有叶子结点的带权路径长度之和，记为WPL＝w1？l1＋w2？l2＋…＋wn？ln＝∑wi？li（i＝1，2，…，n），其中，n为叶子结点的个数；wi为第i个结点的权值；li为第i个结点的路径长度。

（7）哈夫曼树（最优二叉树）：在权为wl，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度WPL最小的二叉树称为哈夫曼树（最优二叉树）。

如图6－40所示，各树权值都由2，2，4，11组成，但构成的二叉树的带权路径长度WPL不同，图1所示的树的带权路径长度WPL＝11？1＋4？2＋2？2＋2？2＝24；图1（b）所示的树的带权路径长度WPL＝2？1＋2？2＋4？2＋11？2＝52；图1所示的树的带权路径长度WPL＝2？2＋11？2＋2？2＋4？2＝40。在这三棵二叉树中，图6－40（a）所示的树的带权路径长度WPL最小，因此它是最优二叉树。

具有不同带权路径长度的二叉树

66037817268

哈夫曼树左小右大是指什么

哈弗曼（Huffman）树，也称最优树，是一类带全路径长度最短的树，在实际中有广泛的应用，也是二叉树的一个具体应用。
在哈夫曼树的定义中，涉及到了路径、路径长度、权等概念，下面先给出概念的定义。
一、概念与定义
路径：从树的一个结点到另一个结点的分支构成这两个结点之间的路径，对于哈夫曼树特指从根节点到某节点的路径。
路径长度：路径上的分支数目叫做路径长度。
树的路径长度：从树根到每一结点的路径长度之和。
权：赋予某一个事物的一个量，是对事物的某个或某些属性数值化描述。在数据结构中，包括结点和边两大类，所以对应有结点权和边权。其具体代表的意义有具体情况而定。
结点的带权路径长度：从树根到结点之间的路径长度与结点上权的乘积。
树的带权路径长度：树中所有叶子结点的带权路径长度之和(WPL--weighted path length)。它的权值分别为，从根到各叶子结点的路径长度分别为。则其带权路径长度WPL通常记作：
WPL的计算如下所示：
对于图a：WPL=2*(9+8+1+6)=48;
对于图b：WPL=8*1+9*2+(1+6)*3=47;
对于图c：WPL=9*1+8*2+(1+6)*3=46;
由图可以看出，权值越大的结点离根节点越近。
二、哈夫曼树构造算法
哈弗曼树的构造步骤：
1、根据给定的n个权值（w1,w2,w3,....wn）,构造n棵只有根结点的二叉树，令起权值为wj；
2、在森林中选取两棵根结点权值最小的树作为左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和
3、在森林中删除这两棵树，同时将新得到的二叉树加入森林中；
4、重复上述两个步骤，最后构成的树即为哈弗曼树。
下图显示了构造一棵哈弗曼树的两种方法：
常见的构造比较简单，这里我选择了两种比较特殊的数据进行了构造：
哈弗曼树并行生长的原则：如果新形成的二叉树的根节点的值大于或等于森林中的另外两个只有根结点树的值，那么接下来的两棵树将并行生长。并不是线性的直接向上生长。
构造方法一：
构造方法二：
最后显示了哈夫曼树的编码，编码的原则左小右大。
三、哈夫曼树在编码中的应用
哈夫曼树最常应用的地方就是对报文进行编码传输通信。在数据的交流中，我们对数据是有要求的：
（1）解码结果与发送方发送的电文完全一样。也就是说发送方传输的二进制编码，到接收方解码后必须具有唯一性；
（2）为了传输的效率和网络的通信及时占用资源少，发送的二进制编码尽可能地短。
下面介绍两种编码方式：
1. 等长编码
这种编码方式的特点是每个字符的编码长度相同，编码长度就是每个编码被翻译的二进制位数。假设字符集只含有4个字符A，B，C，D，用二进制两位表示的编码分别为00，01，10，11。 若现在有一段电文为：ABACCDA，则应发送二进制序列：000100101011000111，总长度为16位。当接收方接收到这段电文后，将按两位一段进行译码。这种编码的特点是译码简单且具有唯一性，但是存在的问题是编码长度并不是最短的，不满足上面的（2）的要求，因为在大数据量的情况下，我们必须的考虑效率问题，那么如何得到最短的编码呢？使用哈夫曼树就可以解决这个问题。这里先介绍一个前缀吗的概念。
前缀码：如果在一个系统中，任意一个编码都不是其他任何编码的前缀（最左子串），则称此编码系统中的编码是前缀码。
例如：（A:110、B:111、C:10、D:0）就是前缀码。但是（A:110、B:11、C:00、D:0）就不是前缀码。0是00的前缀，11是110的前缀。如果不定长的编码不是前缀码，则在译码时会产生二义性。例如110是A呢？还是BD呢？所以对于不定长编码一定要是前缀码。
2. 不等长编码
不等长编码可以叫最优的前缀码。在传送报文时，为了使其二进制位数尽可能地少，可以将每个字符的编码设计为不等长的， 使用频度较高的字符分配一个相对比较短的编码，使用频度较低的字符分配一个比较长的编码。如何得到最优的前缀编码呢？我们就可以利用上述的哈夫曼树来设计，同常成这种编码为哈夫曼编码，它不仅减少电文的总长，还必须考虑编码的唯一性。
四、哈夫曼树中的唯一和不唯一
唯一：哈夫曼树的WPL一定是最小的，唯一，最优是不变的。
不唯一：编码不唯一（表现出来就是形态不唯一）。比如说左小右大，或者是左大右小，树枝左右顺序是可以交换的，也就是说所得的哈夫曼编码则可能不同