首页 > 试题广场 >

对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。例如

[填空题]
对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。例如，图 1 有 5 个不同的独立集（1 个双点集合、3 个单点集合、1 个空集），图 2 有 14 个不同的独立集。那么，图 3 有___1______个不同的独立集。

查看正确选项
添加回答
iPlayForSG头像 iPlayForSG

初赛题要手动。。我傻了都。。

​设表示以的子树中独立集个数，表示选择节点，表示不选节点。

​独立集中的点两两不相邻，所以扩展时不能选两个子节点，扩展时直接左右儿子答案相乘（计数原理）即可。

​则得到递推式：，。

​按后序遍历编号，求出即可。

发表于 2019-10-13 22:15:48 回复(0)
提交观点

问题信息

提高 C++ Pascal 二叉树 问题求解
来自：NOIP2012初赛提高组
上传者：牛客309901号
难度：
1条回答 6653浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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