首页 > 试题广场 >

若某完全二叉树结点个数为100，则第60个结点的度为（）

[单选题]
若某完全二叉树结点个数为100，则第60个结点的度为（） 
  • 0
  • 1
  • 2
  • 不确定
添加回答
clear_rain头像 clear_rain
选A
【分析】

二叉树中的结点的度，有可能为0，1和2。结点总数n=n0+n1+n2。
根据完全二叉树的定义，在完全二叉树中度为1的结点n1只能取两种情况,要么为0,要么为1。
并且当结点总数为偶数时，最后一个结点为左孩子，因此n1=1；并且n0 = n2 + 1，则n0=50，n2=49。即有50个叶子结点和50个非叶子节点。
因此第60个节点为叶子结点，所以度为0。
编辑于 2019-03-26 20:10:03 回复(0)
更多回答
推荐
白驹之过隙头像 白驹之过隙
选A。
完全二叉树：若在一棵满二叉树中，在最下层从最右侧起去掉相邻的若干叶子结点，得到的二叉树即为完全二叉树。
将树类比一个等比数列：1 2 4.... n  由于等比数列求和Sn<100，n作为高度，最多取值5（从根节点0开始计数），Sn=63，还剩余37个节点需要以高度的5节点为父节点（19个，其中第19个只有左孩子）从左至右依次排列。根据等比数列通项公式高度为5共有an=32个节点，而整个二叉树的第60个节点位于高度5一列的第29处，所以没有子结点，度为0
编辑于 2019-03-27 14:08:48 回复(0)
傻不拉几的小傻瓜头像 傻不拉几的小傻瓜
根据公式 节点为n时，左孩子节点为2n，右孩子节点为2n+1
第60个节点 左孩子为2*60=120
120大于100，总结点才100个，所以60节点肯定没有孩子，所以度为0
发表于 2019-03-26 15:36:24 回复(0)
sanfenl头像 sanfenl
深度为2^n-1=100,树深度n为7；
当深度为6时的完全二叉树，结点总数是63，而一颗二叉树的第6层总数只能是2^(n-1)=32。
由此在第7层中还有100-63=37个是叶子结点，但是度为2的结点数是有两个叶子结点的，所以37/2+1=14最多第6层中有14个度为2的，剩下的都是度为0的叶子结点，故第60个结点是度为0的叶子结点
发表于 2023-01-10 00:01:26 回复(0)
天尊墨宇头像 天尊墨宇
选A
完全二叉树：若在一棵满二叉树中，在最下层从最右侧起去掉相邻的若干叶子结点，得到的二叉树即为完全二叉树。
将树类比一个等比数列：1 2 4.... n  由于等比数列求和Sn<100，n作为高度，最多取值5（从根节点0开始计数），Sn=63，还剩余37个节点需要以高度的5节点为父节点（19个，其中第19个只有左孩子）从左至右依次排列。根据等比数列通项公式高度为5共有an=32个节点，而整个二叉树的第60个节点位于高度5一列的第29处，所以没有子结点，度为0

编辑于 2020-07-05 08:44:20 回复(0)
你的offer对我打了烊头像 你的offer对我打了烊
这是公式，若有左子节点，序号为2*父节点序号，即2*60=120，总共才100个，所以无左子节点
发表于 2020-03-21 20:53:19 回复(0)
提交观点

问题信息

树
上传者：阿奻_
难度：
6条回答 5213浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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