我要招人

去企业版

首页 > 试题广场 >

在有n个节点的二叉链表中，值为空的链域的个数为（）

[单选题]

```
n-1
```
```
n+1
```
```
2n-1
```
```
2n+1
```

查看答案及解析

鹿鹿鹿

n个结点的二叉链表共有2n个链域，除了根节点以外，其他每个节点都被一个链域所指向，因此用到的链域为n-1个，

即空链域个数为：2n - ( n-1) = n+1个

编辑于 2016-12-08 11:59:51 回复(1)

西瓜爱offer

n个结点的二叉链表共有2n个链域，n-1条边，即用到的链域为n-1，所以空链域为2n-（n-1)=n+1

发表于 2018-08-08 11:33:52 回复(3)

cquptli

发表于 2017-05-23 00:44:08 回复(2)

lilinl

n个节点的二叉链表共有2n个链域，除了根节点以外，其他每个节点都被一个链域所直向，因此用到的链域为n-1个，即空链域的个数为2n-(n-1)

发表于 2018-08-30 21:26:40 回复(0)

彤彤是个大美女

1.假设有n个节点，n1为度为1的节点数，n2为度为2的节点数，n0为度为0的节点数，那么有n0=n2+1，其中每个度为1的结点的空链域为1，每个度为0的结点的空链域为2，因此根据n1+n2+n0=n；即n1+n0+n0-1=n；那么空域的节点数恰好是n1+2*n0=n+1;

发表于 2017-08-04 14:47:45 回复(0)

HI_YONGGE

1.本题考查二叉树的链式存储，每个节点包含数据域和两个指针，如果指针域非空，则分别指向该节点的左孩子和右孩子

2.在一个节点数为n的二叉树中，指针域包含2n个链域，n个元素除了没有指向根节点的链域，均存在一个且只存在一个指向其他节点的链域，工n-1个，所以值为空的链域个数为n+1，不理解的话画个图即可

发表于 2020-05-21 22:08:50 回复(0)

学术废物

指向的是节点

发表于 2022-03-07 11:01:49 回复(0)

王仲

n个节点有2n个链域，题中为二叉链表，可知是单向非循环链表，2n-（n-1）=n+1

发表于 2019-08-02 13:16:51 回复(0)

lhy19932018

解法：n个节点时，叶子节点有(n+1)/2个，每个叶子节点中没有指向其他节点的指针，因此每个节点有2个空指针域，因此，空的指针域一共2*（n+1）/2= n+1个

编辑于 2018-06-09 15:52:58 回复(0)

blackwidow

考虑一个极端情况：在这个二叉链表所表示的二叉树中，所有除叶子节点外的其他（n-1）个节点均只有左孩子，则此时这（n-1）个节点各有一个空的链域，再加上叶子节点的两个空链域，共有(n-1)+2=n+1个空链域。

发表于 2017-03-15 01:33:14 回复(0)

达文西的猫

每个节点有左孩子和右孩子两个链域，最下面的叶节点肯定有两个空的链域，下来就是有的只有左孩子和右孩子，空出了一个链域

发表于 2017-08-13 21:52:32 回复(0)

提交观点

问题信息

链表

上传者：城市里的养猫者

难度：

11条回答 858收藏 6422浏览

在有n个节点的二叉链表中，值为空的链域的个数为（）

问题信息

热门推荐

相关试题