设一棵完全二叉树具有1000个结点，则此完全二叉树有（）叶子

[问答题]

设一棵完全二叉树具有1000个结点，则此完全二叉树有（）叶子结点，有（）个度为2的结点，有（）个结点只有非空左子树。（说明：多项填空填写格式：分号+空格或其他明显的分割标识，区分开即可）

agjsytt

500,499,1 题1.叶子节点+非叶子节点=1000.将节点编号a1,...,a1000.那么a1000的父亲节点也就是最后一个非叶子节点，即a500。说明有500个非叶子节点(编号1-500) //题2. 节点总数为偶数，说明最后的非叶子节点缺少右孩子，所以度为2的节点数500-1=499。 // 题3.由2可知，最后非叶子节点缺少右孩子，只有左子树 //用到的理论 * 节点总数为偶数，则最后一个非叶子节点缺少右孩子 * 节点从1开始编号，节点an的父亲节点是a/2向下去整。节点ai的左孩子，右孩子分别为a2i,a2i+1

编辑于 2017-03-17 23:20:07 回复(0)

更多回答

推荐

JaxHIn

500 499 1

解析：每一层的结点个数公式为2的n次方，所以由等比数列求和公式有10层的完全二叉树结点个数为2的10次方-1等于1023个，超出1000个，所以第10层的结点没有排满，只有2的9次方再减去多出来的23个，即只有489个，所以第10层有489个叶子结点，而用489除以2得244余1，即第9层有244+1个结点有后代，所以第八层有2的8次方减去245即11个叶子结点，故共有489+11=500个叶子结点，而非叶子结点就有1000-500=500个，而刚刚的余数1就是那个只有一个后代的结点，所以有1个结点只有非空左子树，同时得到有500-1=499个度为2的结点。

编辑于 2017-03-18 08:53:18 回复(2)

默默考研人

500,499,1

遇到此类题目，可以这样考虑，因为是完全二叉树，就只存在度为0,1,2的点，又因为度为2的加一即为度为0的，而度为1的要么没有，要么只有一个，这样，1000/2=500,500-1=499，多出来那个就是度为1的

发表于 2021-11-19 14:50:29 回复(0)

若只如初见201803011505196

直接1000除以2向上取整就是叶子节点的数目。再根据n0+n1+n2-1=n1+2n2算出n1和n2即可

发表于 2018-08-24 10:08:14 回复(0)

一片枫叶林

完全二叉树存在数组里面，有1000个节点，就是相当于a[10001];编号从1开始。从a[1]开始计算。编号为1000的父节点为编号为500的节点，那么从501开始，到1000 共500个叶子节点。

由公式：n=n0+n1+n2; n0=n2+1;

n0=500;

n2=499

有499个度为2 的节点

有一个节点只有非空左子树

编辑于 2017-08-11 14:28:17 回复(0)

爱学习的猪

500 500 0

发表于 2017-03-08 11:22:27 回复(0)

提交观点

问题信息

树

来自：凤凰网2017秋招研发...

上传者：牛100

难度：

6条回答 36收藏 15358浏览

设一棵完全二叉树具有1000个结点，则此完全二叉树有（）叶子

问题信息

热门推荐

相关试题