首页 > 试题广场 >

在有n个结点的二叉链表中，值为非空的链域的个数为？

[单选题]
在有n个结点的二叉链表中，值为非空的链域的个数为（ ）。 
  • n-1
  • 2n-1
  • n+1
  • 2n+1
添加回答
推荐
Amy_sh头像 Amy_sh
A. 值为空的链域个数为n+1个，为非空的个数为n-1。
编辑于 2015-02-05 16:25:22 回复(0)
牛客319693号头像 牛客319693号
在有N个结点的二叉链表中必定有2N个链域。
除根结点外，其余N-1个结点都有一个父结点。
所以，一共有N-1个非空链域，其余2N-（N-1）=N+1个为空链域。
发表于 2015-09-24 16:58:14 回复(0)
小鸟依窗看海头像 小鸟依窗看海
每一个结点都会有一个左右指针，所以n个结点有2n个链域。n个结点n-1个指针就可以互连，所以还剩2n-(n-1)=n+1
发表于 2016-07-13 15:09:25 回复(0)
bjty头像 bjty
n个节点则有2n个链域,除了根节点没有被lchild和rchild指向,其余的节点必然会被指到.所以
空链域公有2n-(n-1)=n+1;
非空链域有2n-(n+1)=n-1；
发表于 2015-06-09 14:40:50 回复(0)
StrongYoung头像 StrongYoung
有N个结点，根没人指向它，其它的都有结点指向它，因此，N-1个结点都需要指针，从而有N-1个非空指针。
发表于 2015-09-30 21:56:42 回复(0)
已注销头像 已注销
搞错了 算成空的了
发表于 2022-03-13 17:50:44 回复(0)
枯木大师头像 枯木大师
问的是非空，醉了
发表于 2020-06-16 22:26:16 回复(0)
叹息之墙头像 叹息之墙
n个节点2n个链域，除根节点外，每个节点必然对应一个链域，所以非空链域为 n-1，空链域为 n + 1
发表于 2015-09-10 21:47:35 回复(0)
karaysn头像 karaysn
看成了空的个数了，哎
发表于 2017-10-12 19:36:02 回复(0)
ShinyGirlHailin头像 ShinyGirlHailin
叶子结点不属于非空链域
发表于 2020-05-25 17:43:15 回复(0)
养猪糕手头像 养猪糕手
把n＝1带入，当然理解更重要
发表于 2023-08-26 09:34:29 回复(0)
凸透少付头像 凸透少付
n个节点，共有（n-1）/2个非叶子结点，非叶子结点的都是非空炼狱，所以有n-1个非空炼狱
发表于 2022-08-27 13:17:24 回复(0)
辉小歌头像 辉小歌
n-1条边，n-1个指针
发表于 2022-08-22 13:36:43 回复(0)
内向且正义头像 内向且正义
有二叉树性质可知 总分支数（路径数）=n-1
所以占用n-1个指针域
二叉链表一共有 2n个指针域

发表于 2022-05-03 16:42:35 回复(0)
XInobukiki头像 XInobukiki
画出来就行了
发表于 2022-03-31 18:46:31 回复(0)
学术废物头像 学术废物
前面考了一道空的题555 搞混了
发表于 2022-03-07 11:06:27 回复(0)
DJH5520头像 DJH5520
每一个结点都会有一个左右指针，所以n个结点有2n个链域。n个结点n-1个指针就可以互连，所以还剩2n-(n-1)=n+1

发表于 2019-07-09 23:13:10 回复(0)
lhy19932018头像 lhy19932018
注意是非空，空域则是n+1，否则是n-1
发表于 2018-06-09 16:52:23 回复(0)
我是小黄人多好头像 我是小黄人多好 
含有n个结点的二叉链表中，链域一共有2*n个（每个点有两个链域）。
对于除了根结点以外的每个点都是有一个父亲结点，所以一共有n-1个指针指向某个结点，
于是形成n-1个有内容的链域（减1即是父亲结点）所以一共有2*n-(n-1)=n+1个链域没有指向任何东西。
发表于 2018-05-03 20:56:05 回复(0)
夜长梦中歌头像 夜长梦中歌
二叉链表特点: 每个节点都有两个域。 除末尾外，每个节点的左域都指向下一个节点(孩子节点)。 所有节点的右域都为空。 so，n个节点有n+1个空域，有n-1个非空域。
发表于 2018-01-28 20:17:16 回复(1)
侯卿头像 侯卿
二楼的方法不错。在此提供另一种方法，特例法。假设为满二叉链。那么明显看出，非空链域即为除了根节点的所有节点数之和:n-1。空链域就是最后一层的链域，也就是最后一层的下一层节点数:n+1。
发表于 2017-12-20 01:08:04 回复(0)
提交观点

问题信息

链表 阿里巴巴
上传者：骑蜗牛的豌豆
难度：
30条回答 21115浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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