霍夫曼树是一种静态最优查找树吗？

哈夫曼树是二叉树吗？~

哈夫曼树不一定是二叉树，也有可能有度为m的哈弗曼树，度为m的哈弗曼树只有度为m的结点和度为0的结点。

二叉树具有以下重要性质：
性质1 二叉树第i层上的结点数目最多为2i-1(i≥1)。
证明：用数学归纳法证明：
归纳基础：i=1时，有2i-1=20=1。因为第1层上只有一个根结点，所以命题成立。
归纳假设：假设对所有的j(1≤j<i)命题成立，即第j层上至多有2j-1个结点，证明j=i时命题亦成立。
归纳步骤：根据归纳假设，第i-1层上至多有2i-2个结点。由于二叉树的每个结点至多有两个孩子，故第i层上的结点数至多是第i-1层上的最大结点数的2倍。即j=i时，该层上至多有2×2i-2=2i-1个结点，故命题成立。

性质2 深度为k的二叉树至多有2k-1个结点(k≥1)。
证明：在具有相同深度的二叉树中，仅当每一层都含有最大结点数时，其树中结点数最多。因此利用性质1可得，深度为k的二叉树的结点数至多为：
20+21+…+2k-1=2k-1
故命题正确。

性质3 在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1。
证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)应等于0度结点数、1度结点(记为n1)和2度结点数之和：
n=no+n1+n2 (式子1)
另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：
nl+2n2
树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为：
n=n1+2n2+1 (式子2)
由式子1和式子2得到：
no=n2+1

满二叉树和完全二叉树是二叉树的两种特殊情形。
1、满二叉树(FullBinaryTree)
一棵深度为k且有2k-1个结点的二又树称为满二叉树。
满二叉树的特点：
（1） 每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。
（2） 满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。
【例】图(a)是一个深度为4的满二叉树。



2、完全二叉树(Complete BinaryTree)
若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。
特点：
（1） 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。
（2） 在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。
（3） 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。
【例】如图(c)中，结点F没有左孩子而有右孩子L，故它不是一棵完全二叉树。
【例】图(b)是一棵完全二叉树。

性质4 具有n个结点的完全二叉树的深度为

证明：设所求完全二叉树的深度为k。由完全二叉树定义可得：
深度为k得完全二叉树的前k-1层是深度为k-1的满二叉树，一共有2k-1-1个结点。
由于完全二叉树深度为k，故第k层上还有若干个结点，因此该完全二叉树的结点个数：
n>2k-1-1。
另一方面，由性质2可得：
n≤2k-1，
即：2k-1-l<n≤2k-1
由此可推出：2k-1≤n<2k，取对数后有：
k-1≤lgn<k
又因k-1和k是相邻的两个整数，故有
,
由此即得：

注意：
的证明【参见参考书目】

哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。
平均查找路径长度最小的树的一种。
至于结论，建议题主看下最小生成树并与它比较区别下，再做定论。

---

潢川县15746229498： 数据结构与算法分析 - ？
绪畏癫痫： 书上写的挺简单,不过要用到实际中去就困难了,这是最基本的东西是以后学习计算机的基础,就像大一要学习高数 大物一样,是一门基础课程~至于学到什么程度就看你自己对自己的要求啦! (一)基本概念和术语 1.数据结构的概念 2.抽象...

潢川县15746229498： 哈夫曼编码原理 - ？
绪畏癫痫： 原发布者:a2420092945 Huffman树及其应用一、最优二叉树(霍夫曼树)预备知识:若干术语路d径:由一结点到另一结点间的分支所构成a→e的路径长度=2beacfg路径长度:路径上的分支数目树长度=10树的路径长度:从树根到每一结点的...

潢川县15746229498： 哈夫曼编码与译码的算法思想 - ？
绪畏癫痫： 基本思想就是概率,用得越多的编码长度越短,最终就会导致最优编码.如果有兴趣,可以看看数据压缩方面的书请查看如下网页: http://zh.wikipedia.org/zh-cn/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81 霍夫曼编...

潢川县15746229498： 霍夫曼树一定是满二叉树吗? - ？
绪畏癫痫： 不是. 满二叉树是所有分支都有左孩子右孩子结点,叶子结点在二叉树最下一层. 霍夫曼树是带权路径最短,也叫最优二叉树.

潢川县15746229498： 什么是赫夫曼树?？
绪畏癫痫： 1、是一种利用二叉树实现的编码原理 霍夫曼(Huffman)编码原理 霍夫曼(Huffman)编码是1952年为文本文件而建立,是一种统计编码.属于无损压缩编码. 霍夫曼编码的码长是变化的,对于出现频率高的信息,编码的长度较短;而对于出...

潢川县15746229498： 如何建一棵霍夫曼树？
绪畏癫痫： 霍夫曼树 在数据结构与算法中,人们把最小带权路径长度的二叉树称为霍夫曼树或者最优二叉树. 霍夫曼算法 对应于霍夫曼树的算法也叫做霍夫曼算法.此算法的思想是: (1)设给定的一组权值为{W1,W2,W3,……Wn},据此生成森林F={T1,...

潢川县15746229498： 给定一组权值,可以唯一构造出一棵哈夫曼树ma? - ？
绪畏癫痫： 不可以.因为没有限定左右子树,并且有权值重复时,可能树的高度都不唯一,唯一的只是 带权路径长度之和最小.哈夫曼树(霍夫曼树)又称为最优树. 1、路径和路径长度 在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径.通路中分支的数目称为路径长度.若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1. 2、结点的权及带权路径长度 若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权.结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积. 3、树的带权路径长度 树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为WPL.

潢川县15746229498： 3. 找到最优树(霍夫曼树)问题分别用C、C++进行算法描述、流程图以及可实现的具体程序 - ？
绪畏癫痫： 霍夫曼树: 带权路径长度达到最小的扩充二叉树即为霍夫曼树.在霍夫曼树中,权值大的结点离根最近. 霍夫曼算法 (1) 由给定的n个权值{w0, w1, w2, …, wn-1},构造具有n棵扩充二叉树的森林F = {T0, T1, T2, …, Tn-1},其中每一棵扩充二叉...

潢川县15746229498： 权重值为4的叶结点的哈夫曼编码为 A.0001 B. 1110 C.001 D. 110 - ？
绪畏癫痫： 至于哈夫曼树中的权值可以理解为:权值大表明出现概率大!哈夫曼树(霍夫曼树)又称为最优树. 1、路径和路径长度 在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径.通路中分支的数目称为路径长度.若规定...

潢川县15746229498： 霍夫曼算法的详细思路及解释？
绪畏癫痫： 霍夫曼树: 带权路径长度达到最小的扩充二叉树即为霍夫曼树. 在霍夫曼树中,权值大的结点离根最近. 霍夫曼算法 (1) 由给定的n个权值{w0, w1, w2, …, wn-1},构造具有n棵扩充二叉树的森林F = {T0, T1, T2, …, Tn-1},其中每一棵扩充二叉树Ti只有一个带有权值wi的根结点,其左、右子树均为空. (2) 重复以下步骤, 直到F中仅剩下一棵树为止: ① 在F中选取两棵根结点的权值最小的扩充二叉树, 做为左、右子树构造一棵新的二叉树.置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和. ② 在F中删去这两棵二叉树. ③ 把新的二叉树加入F.