为什么 哈夫曼树的度只能为0或者2 不能为1?
作者&投稿:关咱 (若有异议请与网页底部的电邮联系)
哈夫曼树的构造总是以两棵值最小的树合并,每次合并都是两棵子树,怎么会有1的节点呢?
哈夫曼树只有叶子结点和度为2的结点,无度为1的结点。在只含度为2和叶子结点的树中度为2的结点数是叶子-1。权值点度为0的点n,则度为2的结点数为n-1
因为哈夫曼树的定义是构造一棵最短的带权路径树,所以这种树为最优二叉树。最优二叉树的度只有0或者2。
给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
扩展资料:
历史
1951年,哈夫曼在麻省理工学院(MIT)攻读博士学位,他和修读信息论课程的同学得选择是完成学期报告还是期末考试。
导师罗伯特·法诺(Robert Fano)出的学期报告题目是:查找最有效的二进制编码。由于无法证明哪个已有编码是最有效的,哈夫曼放弃对已有编码的研究,转向新的探索,最终发现了基于有序频率二叉树编码的想法,并很快证明了这个方法是最有效的。
哈夫曼使用自底向上的方法构建二叉树,避免了次优算法香农-范诺编码(Shannon–Fano coding)的最大弊端──自顶向下构建树。
1952年,于论文《一种构建极小多余编码的方法》(A Method for the Construction of Minimum-Redundancy Codes)中发表了这个编码方法。
参考资料:百度百科-哈夫曼树
对啊,楼主说的对。哈夫曼树的度不能为0或2,绝对不可能为1的。这和度的定义及哈夫曼树的定义有关。结点的度是指该结点所具有的非空子树数。一棵树的度是指该树中结点的最大度树。例如:A B C则A结点度为2.而哈夫曼树是最优二叉数,二叉数的度数且每个结点必有二个度除根结点外。楼主把哈夫曼树的定义认真读一下就知道了。
朱申十维: 哈夫曼树不一定是二叉树,也有可能有度为m的哈弗曼树,度为m的哈弗曼树只有度为m的结点和度为0的结点.
金乡县13547138774: 赫夫曼树每个结点的度要么是0要么是2? - ?
朱申十维: 可以这么说,因为每次都是从所有节点中选两个最小的来组成一个新的节点,所以肯定是0,或2
金乡县13547138774: 请问一棵哈夫曼树结点的度要么是0,要么是2,对吗? - ?
朱申十维: 对啊,不过不是1
金乡县13547138774: 哈夫曼树的总结点数与叶节点数的关系? - ?
朱申十维: 由于哈夫曼树中没有度为1得结点. 只有度为0和度为2得结点. 则一棵有n个叶子结点得哈夫曼树共有2n-1个结点
金乡县13547138774: 为什么说哈夫曼树中不存在度有1的结点 - ?
朱申十维: 在构造哈夫曼树时,是从叶子节点向根节点的方向进行的,每次都是两个两个成对来形成一个新的分支节点,所以不存在度为1的节点
金乡县13547138774: 哈夫曼树和二叉树的问题~?
朱申十维: 问题1:这个题只能描述,而不能画出.若非空树它有三种情况:只有根结点;只有左子树;只有右子树.问题2:哈夫曼树,N个叶子结点有2N-1个结点也比较好理解,因为它只有度为0或度为2的结点,而叶子结点就是度为0结点,即为N;在二叉树中度为0的结点是度为2的结点数目加1(这点是可以证明的),所以度为2的结点数目为N-1,两者加起来就是2N-1啦.
金乡县13547138774: 哈夫曼树问题,第27题,难道哈夫曼树的度数不是2? - ?
朱申十维: 一般的Huffman树肯定指的是度为2的正则二叉树,这里指的是正则m叉树(只有度为m和度为0的结点)
金乡县13547138774: 哈夫曼树编码一定是左边为0,右边为1吗? - ?
朱申十维: 注:0和1表示左子树还是右子树没有明确规定.因此左右节点的顺序是任意的,所以构造出的哈夫曼树并不唯一,但是各个哈夫曼树的带权路径长度相同且为最优.
金乡县13547138774: 一棵哈夫曼树的节点的度是?要有原因 - ?
朱申十维: 假设结点数大于1的哈夫曼树存在节点A度为1,那么A的孩子lchild的权值和A相同... (叙述叙述)=>此树的WPL并非最小... 那么此树就不是哈夫曼树... =>假设错误...=>结点数大于1的哈夫曼树不存在度为1的结点