证明：在结点数多于1的哈夫曼树中不存在度为1的结点。

[问答题]

推荐

赞花婆

用归纳法证明。
当n=2时，要使其成为最优二叉树，必须使两个结点都成为叶子结点。
设n=k时成立，则当n=k+1时，要使其成为最优，必须用k个结点的哈夫曼树与第k+1个结点组成一个新的最优二叉树，所以n=k+1时也成立。

发表于 2018-03-25 10:05:06 回复(0)

每一根头发都有姓名

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

发表于 2020-07-23 20:41:39 回复(0)

提交观点

问题信息

树

上传者：赞花婆

难度：

2条回答 4收藏 4842浏览

扫一扫，把题目装进口袋