为什么 哈夫曼树的度只能为0或者2 不能为1？

为什么哈夫曼树种没有度为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.而哈夫曼树是最优二叉数，二叉数的度数且每个结点必有二个度除根结点外。楼主把哈夫曼树的定义认真读一下就知道了。

---

金乡县13547138774： 哈夫曼树是二叉树吗? - ？
朱申十维： 哈夫曼树不一定是二叉树,也有可能有度为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的结点