首页 > 试题广场 >

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

[问答题]
证明：在结点数多于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条回答 4692浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号