在结点树多于1的赫夫曼树中为什么不存在度为1的结点?
作者&投稿:柴宣 (若有异议请与网页底部的电邮联系)
赫夫曼树即为最优树,其定义为带权路径长度最短的树。当N>1时,可以假设存在度为1的节点,即该节点有一个子树。设该节点为A,其子节点为B。可将AB合并为一个节点,则B以下的叶子结点的路径长度减小,树的带权路径长度减小。显然合并后的树其带权路径长度之和小于原树,与原树是赫夫曼树的已知条件相悖。故假设是不成立的。得证。
不一定。一个满二叉树(完全二叉树)是指一个二叉树,其中每个层次除了最后一层可能不足最大容量外,其它层都是最大容量,而且最后一层从左到右所有节点都是满的。
对于你的问题,如果一个二叉树没有度为1的节点,它可能是满二叉树,也可能是完全二叉树,但不是所有的这种二叉树都是满二叉树。
一个节点如果只有一个子节点,那么它的度就是1。因此,如果一个二叉树没有度为1的节点,那么它的所有节点的度都只能是0或2。这意味着每个节点都有两个子节点(除了叶子节点,它们没有子节点)。然而,这并不意味着该树是满二叉树。
一个满二叉树的特征是,除了最后一层可能不足最大容量外,其它层都是最大容量,而且最后一层从左到右所有节点都是满的。对于一个给定的层数,满二叉树的节点数量可以通过公式2^i - 1(i是层数)计算得出。
因此,如果一个二叉树没有度为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的结点.