一颗哈夫曼树有20个度为2的节点,则它共有多少个叶节点
哈夫曼树:给定n个权值作为n的叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
一个哈夫曼树有19个节点,其叶子节点有十个叶子节点。
具体计算公式如下:(n+1)/2
在哈夫曼树(也叫最优树)中,只有两种类型的结点:度为0或N,即最优二叉树中只有度为0或2的结点,最优三叉树中只有度为0或3的结点,所以有2N-1个节点 。
霍夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。
树的路径长度是从树根到每一结点的路径长度之和,记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln),N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明霍夫曼树的WPL是最小的。
扩展资料:
假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:
(1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);
(2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;
(3)从森林中删除选取的两棵树,并将新树加入森林;
(4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。
1、路径和路径长度
在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1。
2、结点的权及带权路径长度
若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积。
3、树的带权路径长度
树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为WPL。
参考资料:百度百科---哈夫曼树
二叉树有如下性质:
N0 = N2 +1;即叶子节点数等于度为2的节点数+1,相关证明网上很多
所以本题 叶子节点数为21
一颗哈夫曼树有20个度为2的节点,则它共有多少个叶节点
哈夫曼树是二叉树的一种 二叉树有如下性质:N0 = N2 +1;即叶子节点数等于度为2的节点数+1,相关证明网上很多 所以本题 叶子节点数为21
哈夫曼树如何构成?
哈夫曼树的构造规则为:(1) 将16 ,5 ,9,3,20,1看成是有n 棵树的森林(每棵树仅有一个结点);(2) 在16 ,5 ,9,3,20,1森林中选出两个根结点的权值最小的树合并,(即1,3)作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;(3)从森林中删除选...
“哈夫曼树”的构造是什么?
第一步:排序 2 4 5 9 第二步:挑出2个最小的 2 4 为叶子构造出 6 2 4 第三步:判断 6 不大于 5或9(剩余叶子中最小的2个)=》 同方向生长,得出:11 6 5 2 4 第四步:继续生长 20 11 9 6 5 2 4 权值为 2*3+4*3+5*2+9*1=37 也可以20+11+...
同样的权 所构造出的不同的哈夫曼树 的代权路径是唯一的么? 求15...
摘自百度百科:给定n个权值作为n的叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树,哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。从这个角度来说,带权路径最短才是哈夫曼树,那就是唯一的。从严格数学逻辑推理没有证明过,所以这个...
画出哈夫曼树,并求出每个字符的哈夫曼编码
哈夫曼树 74 \/ \\ 42 32 \/ \\ \/ \\ 23 19 12 20 \/ \\ \/ \\ 15 8 9 10 \/ \\ 8 7 \/ \\ 3 5 编码:A(010)B(00000)C(00001)D(001)E(10)F(11)G(0001)H(011)带权路径长度值为:(3+5)*5+7*4+(8+9+10)...
权值序列为:10,16,20,6,30,24,如何构造出一棵哈夫曼树?
哈夫曼树构造规则是先从序列中选取两个最小的权值的点来构造树,新的树根的权值是两个左右子节点的权值和,该新的权值然后放回到权值序列中。迭代这个过程直到只有一棵树为止。所以该哈夫曼树是:106 \/ \\ 44 62 \/ \\ \/ \\ 20 24 30 32 \/ \\ 16 16 \/ \\ 6...
哈夫曼树的路径和路径长度区别
定义:在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1。例子:100和80的路径长度是1,50和30的路径长度是2,20和10的路径长度是3。(02) 结点的权及带权路径长度 ...
...10, 8, 9, 14, 20, 3, 11},请画出相应的哈夫曼树,并计算其带权路径...
先从小到大排序:2,3,8,9,10,11,14,20 然后两个结为一个
用权值2, 3, 7, 8构造一棵哈夫曼树,并求其带权路径长度
哈夫曼树:20 \/ \\ 8 12 \/ \\ 5 7 \/ \\ 2 3 树带权路径长度是: 2 * 3 + 3*3 + 7*2 + 8*1 = 37
Python算法之哈夫曼编码
首先将这五个数字按照从小到大的顺序排列:10, 14,16,20, 40。构建哈夫曼树:1.首先选取10,14 2.重新排序:16,20,24,40 3.重新排序24,36,40,60 4.按照二叉树左0右1,构建哈夫曼树 所以最终得到数字10的编码为100,数字14的编码为101,数字16的编码为110,数字20的编码为111,数字40的...
袁恒尤力: 哈夫曼树是二叉树的一种 二叉树有如下性质: N0 = N2 +1;即叶子节点数等于度为2的节点数+1,相关证明网上很多 所以本题 叶子节点数为21
武进区15836907763: 请问一棵哈夫曼树结点的度要么是0,要么是2,对吗? - ?
袁恒尤力: 对啊,不过不是1
武进区15836907763: 具有10001个结点的哈夫曼树有多少个度为2的结点 - ?
袁恒尤力: 哈夫曼树没有度为1的结点 根据N = N0 + N1 + N2 =10001 =》 N0+N2 = 10001 叶子节点个数等于度为2结点个数+1 => N2+1 = N0 所以N2 = 5000
武进区15836907763: 设哈夫曼树中共有n个结点,则该树中共有几个度数为1的结点 - ?
袁恒尤力: (n+1)/2个叶子节点(度为1) 可以这样考虑,一开始只有一个叶子节点,每加入一个叶子节点,就增加一个度为2的节点,当叶子节点有k时,增加了k-1个度为2的节点n=2k-1;
武进区15836907763: 一个哈夫曼树有19个节点,其叶子节点有多少? - ?
袁恒尤力: 哈夫曼树:给定n个权值作为n的叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman tree).哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近. 一个哈夫曼树有19个节点,其叶子节点有十个叶子节点. 具体计算公式如下:(n+1)/2
武进区15836907763: 设有13个值,用他们组成一棵哈夫曼数,那么该哈夫曼数共有几个结点 - ?
袁恒尤力: 哈夫曼树没有度为1的结点.且权值所在结点都是叶子. 二叉树中度为2的结点数比叶结点少1 结点数=度为2的结点数 + 叶结点数=n-1+n=2n-1所以,答案时=2*13-1=25
武进区15836907763: 哈夫曼树的总结点数与叶节点数的关系? - ?
袁恒尤力: 由于哈夫曼树中没有度为1得结点. 只有度为0和度为2得结点. 则一棵有n个叶子结点得哈夫曼树共有2n-1个结点
武进区15836907763: 具有m个叶子结点的哈夫曼树共有多少个结点 - ?
袁恒尤力: 叶子节点:度为0的节点 哈夫曼树没有度为1的节点 二叉树的性质:度为0的结点个数比度为2的多一个 所以度为2的节点个数为m-1 节点的总数=m+m-1=2m-1
武进区15836907763: 哈夫曼树问题,第27题,难道哈夫曼树的度数不是2? - ?
袁恒尤力: 一般的Huffman树肯定指的是度为2的正则二叉树,这里指的是正则m叉树(只有度为m和度为0的结点)
武进区15836907763: 具有m个叶结点的哈夫曼树共有多少个结点? - ?
袁恒尤力: 因为哈夫曼树除了m个叶子结点就是二度结点,边数=结点个数-1=n0+n2-1 边的个数=2*n2,联立方程可知n2=n0-1,故n2=m-1,所以总结点个数为2m-1