在结点树多于1的赫夫曼树中为什么不存在度为1的结点?

大家看看这道题：数据结构：试证明：有n（n>1）个权值所构造的HUFFMAN树中不存在度为1的节点。~

赫夫曼树即为最优树，其定义为带权路径长度最短的树。当N>1时，可以假设存在度为1的节点，即该节点有一个子树。设该节点为A，其子节点为B。可将AB合并为一个节点，则B以下的叶子结点的路径长度减小，树的带权路径长度减小。显然合并后的树其带权路径长度之和小于原树，与原树是赫夫曼树的已知条件相悖。故假设是不成立的。得证。

不一定。一个满二叉树（完全二叉树）是指一个二叉树，其中每个层次除了最后一层可能不足最大容量外，其它层都是最大容量，而且最后一层从左到右所有节点都是满的。
对于你的问题，如果一个二叉树没有度为1的节点，它可能是满二叉树，也可能是完全二叉树，但不是所有的这种二叉树都是满二叉树。
一个节点如果只有一个子节点，那么它的度就是1。因此，如果一个二叉树没有度为1的节点，那么它的所有节点的度都只能是0或2。这意味着每个节点都有两个子节点（除了叶子节点，它们没有子节点）。然而，这并不意味着该树是满二叉树。
一个满二叉树的特征是，除了最后一层可能不足最大容量外，其它层都是最大容量，而且最后一层从左到右所有节点都是满的。对于一个给定的层数，满二叉树的节点数量可以通过公式2^i - 1（i是层数）计算得出。
因此，如果一个二叉树没有度为1的节点，它可能是满二叉树（如果所有节点都处于最大容量），也可能不是（如果最后一层有节点但没有满）。所以，你的说法不完全正确。

由赫夫曼树的构造过程可知，赫夫曼树的每一分支结点都是由两棵子树合并产生的新结点，其度必为2，所以赫夫曼树中不存在度为1的结点。

---

阿鲁科尔沁旗17746819703： 为什么说哈夫曼树中不存在度有1的结点 - ？
刘凤艾格： 在构造哈夫曼树时,是从叶子节点向根节点的方向进行的,每次都是两个两个成对来形成一个新的分支节点,所以不存在度为1的节点

阿鲁科尔沁旗17746819703： 证明:在节点数多于1的哈夫曼树中不存在度数为一的结点 - ？
刘凤艾格： 由赫夫曼树的构造过程可知,赫夫曼树的每一分支结点都是由两棵子树合并产生的新结点,其度必为2,所以赫夫曼树中不存在度为1的结点.

阿鲁科尔沁旗17746819703： 数据结构,结点数多于1的哈夫曼树中不存在度为1的结点么? - ？
刘凤艾格： 叶子节点不算么

阿鲁科尔沁旗17746819703： 一棵哈夫曼树的节点的度是?要有原因 - ？
刘凤艾格： 假设结点数大于1的哈夫曼树存在节点A度为1,那么A的孩子lchild的权值和A相同... (叙述叙述)=>此树的WPL并非最小... 那么此树就不是哈夫曼树... =>假设错误...=>结点数大于1的哈夫曼树不存在度为1的结点

阿鲁科尔沁旗17746819703： 大家看看这道题:数据结构:试证明:有n(n>1)个权值所构造的HUFFMAN树中不存在度为1的节点. - ？
刘凤艾格： 反证法:若存在度为1的节点,那么该节点有一个子树.设该节点为A,子节点为B.因为A是由B与另一个节点相加而得,而现在只有一个节点,那么A=B.将AB合并为一个节点,则B以下的叶子结点路径长度减少,树的带权路径长度减少,合并后其带权路径之和小于原树,而哈夫曼树已经是带权路径长度最短的树,所以与原树是哈夫曼树相悖,所以假设不成立.

阿鲁科尔沁旗17746819703： 设哈夫曼树中共有n个结点,则该树中共有几个度数为1的结点 - ？
刘凤艾格： (n+1)/2个叶子节点(度为1) 可以这样考虑,一开始只有一个叶子节点,每加入一个叶子节点,就增加一个度为2的节点,当叶子节点有k时,增加了k-1个度为2的节点n=2k-1;

阿鲁科尔沁旗17746819703： 哈夫曼树的总结点数与叶节点数的关系? - ？
刘凤艾格： 由于哈夫曼树中没有度为1得结点. 只有度为0和度为2得结点. 则一棵有n个叶子结点得哈夫曼树共有2n-1个结点

阿鲁科尔沁旗17746819703： 赫夫曼树是否唯一 - ？
刘凤艾格： 不唯一,因为没有限定左右子树,并且有权值重复时,可能树的高度都不唯一,唯一的只是带权路径长度之和最小. 给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为...

阿鲁科尔沁旗17746819703： 16、下面关于赫夫曼树的叙述中,正确的是 - 上学吧普法考试？
刘凤艾格： 哈夫曼树不一定是二叉树,也有可能有度为m的哈弗曼树,度为m的哈弗曼树只有度为m的结点和度为0的结点.