我要招人

去企业版

首页 > 试题广场 >

一个具有767个节点的完全二叉树，其叶子节点个数为（）

[单选题]

```
383
```
```
384
```
```
385
```
```
386
```

查看正确选项

女子无才

假设所有结点总数为n，度为0的结点(叶子节点)为n0，度为1的结点n1，度为2的结点为n2。

我们考虑分支线总数的关系，n - 1 = n1 + 2 * n2; //①

而结点总数的数据关系很容易得：n = n0 + n1 + n2;//②

也就是(n0 + n1 + n2) - 1 = n1 + 2 * n2 → n0 = n2 + 1

然后 n = n0 + n1 + (n0 - 1) = 2n0 + n1 - 1;

即no = (n + 1 - n1) / 2，又因为在完全二叉树中，n1不是为0就是为1。而且n0必须是整数，也就是n1 = 0时

n0 = (767+ 1) / 2 = 384个

发表于 2017-01-04 11:46:40 回复(5)

美团到店招聘

一棵树含有n个结点，则最后一个结点的编号必为n，它的父结点则为n/2，且为上一层最右边的一个结点。所以根结点的个数就为：n-n/2。

此题中，n = 767,n-n/2 = 767 - 767/2 = 384。选B

发表于 2017-02-17 13:05:53 回复(7)

凌梦初辰

现在共有节点767个，而且说明二叉树是完全二叉树。根据完全二叉树的特点：只有最高层和次高层存在叶子节点。而且从次高层到树根都是满二叉树。

那么离767最近的应该是512，那么上面的满二叉树（从次高层到树根）应该有511个节点，次高层应该有256个节点。

那么计算最高层应该有 767-511 = 256 个叶子节点。然后256 / 2 = 128,意思就是说最高层只是把次高层128个节点划分了，那么次高层还有

256 - 128 = 128个节点没有被划分，即就是叶子节点。

那么叶子节点的个数应该是：256 + 128 = 384。即就是答案的B

发表于 2017-09-08 08:54:28 回复(0)

这个昵称不太火

完全二叉树叶子节点总是比度为2的节点多一个，n0=n2+1；没有度为1的节点，所以总结点数是n0+n2=2n0-1=767，n0=384.

发表于 2019-03-23 09:23:16 回复(1)

Fcq11

完全二叉树总结点数为偶数则度为1的结点数为1 总节点数为奇数则度为1的结点数为0

发表于 2020-03-22 10:38:43 回复(0)

小辣鸡阿伟

n为奇数 n1=0 n0=（n+1）/2 n为偶数 n1=1 n0=n/2

发表于 2022-06-08 09:02:51 回复(0)

牛客8334409号

我是直接根据其规律通过公式来计算的，总的节点数为2^n-1=767;所以2^n=768,又因为每次的叶子节点的个数为2^(n-1),所以2^(n-1)=2^n/2=768/2=384.

发表于 2017-05-04 20:53:43 回复(1)

黄家三少

已知完全二叉树共767节点，介于 2⁹和2¹⁰之间。故1到9层可以看作为满二叉树，该满二叉树的总结点数为2⁹-1=511，并且它最后一层节点数为2⁸=256。

可以计算出完全二叉树10层剩余叶节点为767- 511 =256。10层叶节点占9层父节点为256/2= 128。前文已知第9层共256个节点，256减去被10层占去的128个节点则表示第9层剩余128个叶节点。

故叶节点 = 第9层的128+第10层的256 = 384

发表于 2024-04-10 19:18:37 回复(0)

XInobukiki

n0=n2+1，n0+n2=767，2n2+1=767，n2=767-1，n0=n2+1，n0=384

发表于 2022-03-23 18:04:34 回复(0)

牛客836955971号

二叉树节点数满足n=n0+n1+n2，这是个完全二叉树，完全二叉树的话n1不是0就是1。节点总数是767个是个奇数，说明这棵树最后一层上节点数必然是偶数，也就是没有那种上一层某个父节点只有一个孩子的情况，所以n1=0.任意二叉树又满足n0=n2+1，就可以接出来n1和n2.

发表于 2020-08-06 21:04:14 回复(0)

winfang

层数：2^n-1≈767，n=9,2^9=512，不足767，所以层数是10层。

假设这个是满二叉，2^10-1=1023结点，需要多少个才能补到满二叉树的节点数：1023-767=256，倒数第二层的叶子节点数：256÷2=128。

最后一层叶子节点数（总 - 除了最后层的）：767-（2^9-1）=256。

所有叶子节点数（倒数第二层的叶子节点数+最后一层叶子节点数）：128+256=384

发表于 2023-09-10 09:45:44 回复(0)

三木丶

为什么n1会为零呢，因为n1只可能出现在末尾，又因为是完全二叉树，所以度数为1的节点，只能是0或1

发表于 2022-08-26 21:47:48 回复(0)

我努力了，剩下的由上天了

完全二叉树总结点数为偶数则度为1的结点数为1 总节点数为奇数则度为1的结点数为0，确定度为1的节点为0，度为0的比度为2多一个，相加求解

发表于 2020-04-25 16:00:53 回复(0)

choice240701

二叉树存在度数为0的节点个数=度数为2的节点个数+1

但又因为是完全二叉树度数为1的节点个数不是0就是1

发表于 2020-04-21 12:51:23 回复(0)

mmm_mmm

若完全二叉树的节点为n,则其叶子节点个数为: n/2向上取整

发表于 2018-10-29 19:23:58 回复(0)

莞尔508

n0=(n+1）/2；n0=n2+1；易得n0=(767+1)/2=384.

发表于 2018-03-25 17:04:37 回复(0)

游文武

给个例题

：

叶子结点

叶子结点就是度为0的结点就是没有子结点的结点

叶子结点

n₀：度为0的结点数，n₁:度为1的结点 n₂：度为2的结点数。 N是总结点

在二叉树中：

n₀=n₂+1；

N=n₀+n₁+n₂

例题

一棵树度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1，则这棵树的叶子节点个数为多少？

解：因为任一棵树中，结点总数=度数+1，所以：

n0+4+2+1+1 = （n0*0 + 1*4 + 2*2 + 3*1 + 4*1）+1

则：n0=8

其中：n0表示叶子结点。

发表于 2017-11-30 08:47:44 回复(0)

提交观点

问题信息

树

来自：2025年秋招-中国移...

上传者：牛100

难度：

17条回答 199收藏 8090浏览

一个具有767个节点的完全二叉树，其叶子节点个数为（）

叶子结点

例题

问题信息

热门推荐

相关试题