哈夫曼树与霍夫曼树的区别
二叉树具有以下重要性质:
性质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是相邻的两个整数,故有
,
由此即得:
注意:
的证明【参见参考书目】
最短路径和最小生成树是不同的概念.
最短路径是对于一个图的两个结点而言的.在一个图中,结点A通过某些结点和边可以走到结点B,那这些结点和边就组成一条A到B的路径,A到B的最短路径就是A到B的所有路径中边权值总和最小的那一条(或多条).
最小生成树是对于一个图本身而言的.对于一个有n个结点的无向连通图(边没有方向,任意两点之间都存在路径可以到达),必然可以去掉某些边,使得最终剩下n-1条边,并且n个结点仍然是连通的,这n个结点和n-1条边组成了原图的一个生成树,而最小生成树就是所有可能的生成树中n-1条边的权值总和最小的那一个(或多个).
最短路径常用算法有:floyd,dijkstra,SPFA,A*等
最小生成树常用算法有:prim,kruskal
比如说第一次就是由2,3生成5,第二次由3,4生成7,第三次由5,6,生成11...由此类推就是了,直到剩下最后一个结点,也就是哈夫曼树生成了。
左右的大小嘛,呵呵,一般比较习惯将小的放在左边,但你在编码过程中和之后译码知道你大的数放在左边的话也是可以的!哈哈,这只是一种算法,理解了就简单了.
一棵哈夫曼树有多高?
根据哈夫曼编码左分支表示字符'0',右分支表示字符'1'的规则,在哈夫曼树上求叶子结点的编码。编码长度<=4,则哈夫曼树的高度是5。又已知两个字符编码是0和10,说明第2层和第3层各有一个子结点,如果还想对最多个字符进行编码,那么第3~5层要达到结点的最大数目,如图 最多4个 ...
计算机中的树是什么
树:数据结构名词。1、树状图是一种数据结构,它是由n(n>=1)个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。2、它具有以下的特点,每个结点有零个或多个子结点;没有父结点的结点称为根结点;每一个非根结点有且...
霍夫曼树是一种静态最优查找树吗?
哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。平均查找路径长度最小的树的一种。至于结论,建议题主看下最小生成树并与它比较区别下,再做定论。
哈夫曼树一定是完全二叉树吗
哈夫曼树也可以是k叉的,只是在构造k叉哈夫曼树时需要先进行一些调整。构造哈夫曼树的思想是每次选k个权重最小的元素来合成一个新的元素,该元素权重为k个元素权重之和。但是当k大于2时,按照这个步骤做下去可能到最后剩下的元素少于k个。解决这个问题的办法是假设已经有了一棵哈夫曼树(且为一棵满...
如果给定权值总数有N个,则其哈夫曼树的结点总数为多少
给定权值总数有N个,则其哈夫曼树的结点总数为2*N-1;给定n个权值作为n的叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。哈夫曼树只有叶子结点和度为2的结点,无度...
数据结构,设哈夫曼树的叶子结点总数为m,则结点总数为多少,这个题目怎么...
哈夫曼树是二叉树,且结点的度只有两种,一种是度为0的叶子节点,另一种则是度为2的内部结点,不存在度为1 的结点。根据二叉树的性质,度为0的结点和度为2 的结点的关系:n0=n2+1很容易算出;叶子结点总数为m的哈夫曼树的总结点数为:2m-1。在一棵树中,从一个结点往下可以达到的孩子或孙子...
哈夫曼树的带权路径长度是多少?
由权值分别为3,8,6,2,5的叶子节点生成一棵哈夫曼树,它的带权路径长度为53。哈夫曼树满足对于n个带权节点,总可以用他们作为叶节点构造出一颗最小WPL值。树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)。因为权值分别为3,8,6,2,5,所以WPL=2*3+3*3+5...
哈夫曼树是二叉树吗
哈夫曼树不一定是二叉树,也有可能有度为m的哈弗曼树,度为m的哈弗曼树只有度为m的结点和度为0的结点。给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。...
哈夫曼树的构造规则是什么?
哈夫曼树如下:(24)(10) (14)(5) 5 6 8 2 3 带权路径长度为 2*3 + 3*3 +5*2 +6*2 +8*2 = 53
哈夫曼树的度只有2和0吗
只有2和0.哈夫曼树是一种二叉树,每个节点最多只能有两个子节点。,哈夫曼树还具有贪心的特点,每次选择权值最小的两个节点进行合并,最终形成一棵带权路径长度最小的二叉树。哈夫曼树的度只能是2或者0,不能取其他值。
习昂力可: 给定n个权值作为n的叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree).哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近. 哈夫曼树(霍夫曼树)又称为最...
疏附县15935273142: 到底什么是哈夫曼树啊,求例子 - ?
习昂力可: 哈夫曼树是给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree).哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近. 例子: 1、将w...
疏附县15935273142: 哈夫曼树与赫夫曼数一样吗? - ?
习昂力可: 不是,哈夫曼节点总数一定是奇数. 除叶子节点外,其他节点都有左右子节点,再加上根节点,所以是奇数
疏附县15935273142: Huffman树的应用 - ?
习昂力可: 哈夫曼树 在一般的数据结构的书中,树的那章后面,著者一般都会介绍一下哈夫曼(HUFFMAN)树和哈夫曼编码.哈夫曼编码是哈夫曼树的一个应用.哈夫曼编码应用广泛,如JPEG中就应用了哈夫曼编码.首先介绍什么是哈夫曼树.哈夫曼...
疏附县15935273142: 给定一组权值,可以唯一构造出一棵哈夫曼树ma? - ?
习昂力可: 不可以.因为没有限定左右子树,并且有权值重复时,可能树的高度都不唯一,唯一的只是 带权路径长度之和最小.哈夫曼树(霍夫曼树)又称为最优树. 1、路径和路径长度 在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径.通路中分支的数目称为路径长度.若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1. 2、结点的权及带权路径长度 若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权.结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积. 3、树的带权路径长度 树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为WPL.
疏附县15935273142: 霍夫曼树和霍夫曼编码trcpy怎么定义 - ?
习昂力可: 一、哈夫曼树的概念和定义什么是哈夫曼树?让我们先举一个例子.判定树: 在很多问题的处理过程中,需要进行大量的条件判断,这些判断结构的设计直接影响着程序的执行效率.例如,编制一个程序,将百分制转换成五个等级输出....
疏附县15935273142: 哈夫曼编码原理 - ?
习昂力可: 原发布者:a2420092945 Huffman树及其应用一、最优二叉树(霍夫曼树)预备知识:若干术语路d径:由一结点到另一结点间的分支所构成a→e的路径长度=2beacfg路径长度:路径上的分支数目树长度=10树的路径长度:从树根到每一结点的...
疏附县15935273142: 哈夫曼树!!与普通二叉树的区别是???
习昂力可: 首先,哈夫曼树是带权路径长度最小的二叉树,用途是平均查找信息的代价最小. 普通二叉树的用途也普通,比较通用,就是信息存储和查找. 普通二叉树可能有的只有一个子节点,而哈夫曼树一定有两个.
疏附县15935273142: 一组权值是不是可以构造很多种哈夫曼树? - ?
习昂力可: 一组权值对应一个吧. 对于你给出的题目树的样子应该是这样 27 / \ 11 16 / \ / \ 5 6 7 9 / \ 2 4 路经是2*3+3*2=12; 如果你认为左右互换不等的话,那么就是有很多种了,一般的霍夫曼树都有一种规定(隐性的啊),左边的数字比右边的小(对于...
疏附县15935273142: 权重值为4的叶结点的哈夫曼编码为 A.0001 B. 1110 C.001 D. 110 - ?
习昂力可: 至于哈夫曼树中的权值可以理解为:权值大表明出现概率大!哈夫曼树(霍夫曼树)又称为最优树. 1、路径和路径长度 在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径.通路中分支的数目称为路径长度.若规定...