我要招人

去企业版

首页 > 试题广场 >

若一棵完全二叉树有768 个结点，则该二叉树中叶结点的个数是

[单选题]

若一棵完全二叉树有768 个结点，则该二叉树中叶结点的个数是（）。

```
257
```
```
258
```
```
384
```
```
385
```

查看正确选项

Ticker

（敲黑板）重点：

节点数n=n0+n1+n2；

当节点数n为奇数，无度为1的节点；节点n为偶数，有一个度为1的节点；

非空二叉树，n0=n2+1；

综上所述：

768=n0+n1+n2；

n2=n0-1；

所以n0=384

发表于 2016-12-10 09:09:28 回复(2)

catfate

完全二叉树记得以下几个公式：

$n = n_0 + n_1 + n_2$
$n_2 = n_0 - 1$
$\begin{cases} n_1 = 1,\ if\ n\ is\ even \\ n_1 = 0,\ if\ n\ is\ odd \end{cases}$

由题知： $n = 768, n_1 = 1$ ，因此：

$\begin{cases} 768 = n_0 + 1 + n_2 \\ n_2 = n_0 - 1 \end{cases}$

两式相加得 $768 = 2n_0$ ，即 $n_0 = 768/2 = 384$ 。

发表于 2020-03-31 11:13:02 回复(0)

大龙201805111621618

首先理解什么而是完全二叉树，完全二叉树从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。

有768个结点，则树的高度为10。前9层结点数为511，则第10层有768-511=257个叶子结点。257个叶子结点在第9层有129个根结点。则第九层剩下256-129=127个叶子结点。所以共有127+257=384

发表于 2018-06-01 15:22:55 回复(0)

紫旋

一棵树的结点总数为：n = n0+n1+n1；
而一棵完全二叉树中，当节点数n为奇数，无度为1的节点；节点n为偶数，有一个度为1的节点；
题中的n为偶数，即只包含n0和n2，又n2=n0-1；
所以2*n0+1-1=768；
得：n0=384。

编辑于 2016-12-16 12:38:47 回复(0)

Forrestcloud

768-511=257(最后一层的叶子节点数）

257/2=129

256-129=127（倒数第二层叶子节点数）

127+257=384

发表于 2017-06-03 15:14:30 回复(0)

🔥Mr.王🔥

完全二叉树，只有在第一层和叶节点层上节点个数可能是奇数个，根节点本来就是奇数的，所以总数为偶数时应该先减一得到叶节点是否包含无兄弟的叶子。显然此题包含一个只有左子节点的节点，既n1等于1。n=n0+n1+n2。768-1-1=2n2。n2=383所以n0=n2+1=384

发表于 2018-05-05 12:02:40 回复(0)

B、晚上好_朱明永

当完全二叉树为满二叉树时,则可得知二叉树总节点数为2^10 - 1 = 1023,前九行总结点数为2^9-1 = 511，
    因为完全二叉树中总结点为768。因此可知完全二叉树第十层全为叶节点，叶节点数为：768-511 = 257。
    因此由第十层的叶节点数可知第九层也存在一定数量的叶节点。由第十层叶节点数可求得第九层的父节点数为（257+1（第九层存在一个父节     点有一个子节点））/2 = 129，
    则第九层节点数-第九层父节点数 = 第九层叶节点数 = 256-129 = 127。
二叉树中叶节点数的个数 = 第十层叶节点数+第九层叶节点数，即257+127 = 374

发表于 2018-04-23 23:51:58 回复(0)

laymond

2^9 = 512，2^10 = 1024，层数介于9 ~ 10 层，叶子结点在9层和10层都存在。

第9层 2^8= 256 有这么多结点，部分为叶子结点

第10层有 768 - 512 = 256 结点，全为叶子结点

由于是二叉树，第9层 256/2 = 128 个有孩子，第9层叶子结点为 256 - 128 = 128。

总共128+256 = 384

编辑于 2018-02-22 09:40:06 回复(0)

梦境迷离

以后遇到偶数直接除以2秒得答案奇数向上取整

编辑于 2018-02-04 18:51:12 回复(0)

StoneHui

完全二叉树的叶子节点数 = (总节点数+1)/2，结果向下取整。(768+1)/2 = 384。

发表于 2018-01-09 10:37:37 回复(0)

xingshanxie

二叉树的度是指子节点的个数, 只有0, 1, 2三种情况
结点数 = 度为0的节点数 + 度为1的节点数 + 度为2的节点数
当节点数为偶数是,有一个度为1的结点数.
度为2的节点数 = 度为0节点数-1
叶节点的度为0

编辑于 2017-03-04 21:48:02 回复(0)

提交观点

问题信息

树

上传者：城市里的养猫者

难度：

11条回答 175收藏 12981浏览

若一棵完全二叉树有768 个结点，则该二叉树中叶结点的个数是

问题信息

热门推荐

相关试题