首页 > 试题广场 >

在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）

[单选题]

在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ） 

  • n
  • n+1
  • n-1
  • n/2
查看正确选项
添加回答
mmryziqi头像 mmryziqi
1>节点总数为2n, 无论n取何值. 总数都为偶数, 加上树为完全二叉树也就是说有1个节点是度为1的N1节点。
2>节点总数S=N0+N1+N2, N0=N2+1; => N0=S-N1-(N0-1);
3>因本题中N1=1, S=2N; 所以上式=> N0=S-1-N0+1 => N0=S/2 => N0=N;
发表于 2017-08-15 16:21:10 回复(0)
Payaso_hah头像 Payaso_hah
完全二叉树结点数N为奇数时,它有(N/2)+1个叶结点，当N为偶数时，它有N/2个结点，这里2n是偶数，所以选A
发表于 2017-08-07 17:45:15 回复(2)
牛客112头像 牛客112
这种题直接画一个具有4个结点的二叉树一看就清楚明白。简单直接
发表于 2018-03-31 10:42:36 回复(0)
牛100头像 牛100

完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。根据完全二叉树性质，如果共 2n 个结点，从根结点开始按层序用自然数 1 ， 2 ，…， 2n 给结点编号，则编号为 n 的结点左子结点编号为 2n ，因此叶子结点编号为 n+1,n+2, … ,2n 。故叶子结点个数为 n ，本题答案为 A 选项。

发表于 2017-02-13 00:36:06 回复(3)
灵少头像 灵少
首先完全二叉树的叶子节点个数（度为0，下称n0）比度为2的节点（下称n2）个数多一。所以有n0==n2+1。而总结点个数==叶子节点个数（n0)+度为2节点个数(n2)+度为1的节点个数(n1) ，而又因为完全二叉树的特性，度为1的节点个数要么为1要么为0.
所以有总结点==2n2+1+n1。题目中总结点个数为2n是偶数，而2n2+1是奇数，所以n1肯定为奇数，所以n1==1,故上式为：2n == 2n2+2   -->  n == n2+1。所以叶子结点数（n0) == n2+1 == n
发表于 2021-07-07 11:49:45 回复(0)
lilinl头像 lilinl
最后一个节点为2n,而且是完全二叉树，则最后一个父节点为n，叶节点为n+1,n+2 ..... 2n ,总共n个 ；
发表于 2018-07-22 21:43:23 回复(0)
提交观点

问题信息

树
上传者：牛100
难度：
6条回答 6690浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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