设给定权值总数有n 个,则该哈夫曼树中度为2的结点总数为:
作者&投稿:白梦 (若有异议请与网页底部的电邮联系)
2n-1
因为哈夫曼树为满二叉树,满二叉树的叶子结点为总结点的加1后除以2
定权值即哈夫曼树的叶子结点数
某个叶子结点的权值是该结点乘以它的层数
给定权值总数有N个,则其哈夫曼树的结点总数为2*N-1;
给定n个权值作为n的叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
哈夫曼树只有叶子结点和度为2的结点,无度为1的结点。在只含度为2和叶子结点的树中度为2的结点数是叶子-1。权值点度为0的点n,则度为2的结点数为n-1。
扩展资料:
在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1。
若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积。
参考资料来源:百度百科-哈夫曼树
这不很明显~哈夫曼树无度为1的结点~权值点都为度为0的点~n-1
你给定哈夫曼树权值的总数有用么?连结点个数都无法确定,这就是一个无解的题,如果知道了结点总数,那么还可以得出度为2的结点个数的范围。
2*N-2
○
╱╲
○ ○
╱╲
○ ○
╱╲
○ ○
用先肺力:[答案] 算上N个叶子的话一共2N-1个.参见定理:0度结点(即叶子)数比2度结点数多1.另外Huffman树中没有1度结点.
淮上区13041618969: 最优二叉树中权值最小的两个节点一定互为兄弟节点吗 - ?
用先肺力: 给定权值总数有N个,则其哈夫曼树的结点总数为2*N-1;
淮上区13041618969: 有n个权值,建立哈夫曼树后,哈夫曼树的结点最多有多少个?
用先肺力: 最小的两个值合起来还是最小的情况,生成的结点最多. 每次合成,生成一个结点,即共有n-1+n=2n-1个.
淮上区13041618969: 怎样构造合适的哈夫曼树? - ?
用先肺力: 来自百度百科:哈夫曼树构造方法: 假设有n个权值,则构造出的哈夫曼树有n个叶子结点. n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为: (1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点); (2) 在森...
淮上区13041618969: 哈夫曼树怎样构造编码? - ?
用先肺力: 先编造哈夫曼树,哈夫曼树构造规则: 假设有n个权值,则构造出的哈夫曼树有n个叶子结点. n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为: (1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点); (2) ...
淮上区13041618969: 到底什么是哈夫曼树啊,求例子 - ?
用先肺力: 哈夫曼树是给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree).哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近. 例子: 1、将w...
淮上区13041618969: 有关构造哈夫曼树的问题 - ?
用先肺力: 1. 根据给定的n个权值{w1,w2,…wn}构成n棵二叉树的集合F={T1,T2,..,Tn},其中每棵二叉树Ti中只有一个带权wi的根结点,左右子树均空. 2. 在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值...