判断下列说法是否正确：在哈夫曼树中没有度为1的结点。（）

[单选题]

查看答案及解析

编辑于 2019-11-07 14:21:45 回复(0)

L2020

A.正确

从哈夫曼树的构造过程中不难知道，哈夫曼树的每一个结点都是由它的两棵子树合并产生的新结点。

因此，它的度一定为2。

所以哈夫曼树中没有度为1的结点。

故答案为:A.正确

发表于 2019-11-06 16:17:51 回复(0)

Jino.

选A。

由哈夫曼树的构造过程可知，哈夫曼树的每一非叶结点都是由两棵子树合并产生的新结点，其度必为2，叶子结点度为0，所以哈夫曼树中不存在度为1的结点，题中表述正确。

发表于 2019-11-06 16:03:03 回复(0)

dragonlogin

哈夫曼树：最优二叉树，霍夫曼树
构造过程：
- 1 每次从当前未构造的结点集合S中，找出权值最小的A结点与次小的B结点，将A+B的和作为C结点，构造出一颗二叉树（A，B作为C的孩子），然后将C添加入集合中
- 2 重复步骤1，知道集合S为空
度为1，表示一个父节点只有一个孩子，根据上面构造过程，显然没有一个孩子的父节点，都是2个孩子的，所以答案选A

编辑于 2019-11-07 13:03:10 回复(0)