首页 > 试题广场 > 判断下列说法是否正确:在结点数多于1的哈夫曼树中不存在度为1
[单选题]
判断下列说法是否正确:在结点数多于1的哈夫曼树中不存在度为1的结点。()

  • 正确
  • 错误
推荐
A。考察的是对哈夫曼树的概念。
霍夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。

哈夫曼树的构造:

  1. 根据给定的n个权值,选取权值最小的树作为左右子树,构造一个新的二叉树,左右子树的和为新二叉树的根节点。
  2. 在给定的n个权值中删除这两个左右子树,将新得到的二叉树根节点加入到给定的权值中,继续重复上述操作。
  3. 直到只含一棵树为止。
由此可见构成的哈夫曼树都是两个节点构成的左右子树,所以没有度为1的节点。
编辑于 2019-09-12 14:13:09 回复(0)
更多回答
A、正确

哈夫曼树的构造:

  1. 根据给定的n个权值,选取权值最小的树作为左右子树,构造一个新的二叉树,左右子树的和为新二叉树的根节点。
  2. 在给定的n个权值中删除这两个左右子树,将新得到的二叉树根节点加入到给定的权值中,继续重复上述操作。
  3. 直到只含一棵树为止。
由此可见构成的哈夫曼树都是两个节点构成的左右子树,所以没有度为1的节点
可以用数学归纳法证明:

发表于 2019-09-11 22:57:42 回复(0)
由赫夫曼树的构造过程可知,赫夫曼树的每一分支结点都是由两棵子树合并产生的新结点,其度必为2,所以赫夫曼树中不存在度为1的结点。
发表于 2019-09-11 17:51:43 回复(0)