首页 > 试题广场 >

用二叉链表法(link-rlink)存储包含 n 个结点的二

[单选题]
用二叉链表法(link-rlink)存储包含 n 个结点的二叉树,结点的 2n 个指针区域中有 n+1 个为空指针（）。
  • 正确
  • 错误
查看正确选项
添加回答
BugFree头像 BugFree
在n个结点的二叉链表中，有(n+1)个空指针域。
因为一共有2n个链域，除根结点外，每个结点有且仅有一个双亲，所以只会有n－1个结点的链域存放指针，指向非空子结点。所以空指针域个数为：2n-(n-1) = n+1
发表于 2017-08-21 16:10:23 回复(0)
孙华超头像 孙华超
问题转换为知道 性质一：no + n1 + n2 = n 和 性质二： n 0  = n 2  + 1(二叉树性质）
求取目标函数：2n0 + n1
目标函数代入性质二得：
2n 0  + n 1 = 2n2 + n1 + 2
性质二代入性质一得：
2n 2  + n 1  + 1 = n
所以：2n 0  + n 1 = n + 1
注：n0表示度为0的节点。


发表于 2017-06-20 17:33:57 回复(1)
树街猫o(=•ェ•=)m头像 树街猫o(=•ェ•=)m

n个节点的二叉树一共有2n个指针，非空指针数等于树的边数（n-1）,所以空指针数等于2n-(n-1)=n+1.

发表于 2019-08-15 10:41:18 回复(0)
Dreamer_Shen头像 Dreamer_Shen
n个节点每个节点有两个指针，即一共2n个指针（如题中所述），n个节点构成二叉树，一共有n-1条边即用去n-1个指针，剩余n+1个指针未用。
发表于 2018-07-26 13:52:32 回复(0)
盯裆猫头像 盯裆猫
知道二叉链表怎么画就容易了
另外：
二叉树是逻辑结构，二叉链表是二叉树的物理实现，是它的一种存储结构（链式存储结构）。
存储结构主要有：
  1. 顺序存储结构：逻辑相邻关系的物理也相邻
  2. 链式存储结构：逻辑相邻，物理不一定相邻
  3. 索引存储结构：增加索引表，提升查找速度的。
  4. 哈希（或散列）存储结构：只存储节点数据，不存储节点逻辑关系的。

编辑于 2018-07-24 13:42:19 回复(1)
Ryan266头像 Ryan266
非空二叉树的一个有趣的性质:n0 = n2 + 1 证明： （1）假设该二叉树有N 个节点，那么它会有N－1条边。【原因：因为除了根节点，其余的每个节点都有且只有一个父节点，那么这N 个节点恰好为树贡献了N - 1 条边。】 （2）每类节点的度数和 0*n0 + 1*n1 + 2*n2 即为边的个数。 （3）等式 N - 1 = n1 + 2*n2，把N 用n0 + n1 + n2 替换 （4）n0 + n1 + n2 - 1 = n1 + 2*n2，于是有 n0 = n2 + 1。命题得证。
编辑于 2018-01-31 10:40:59 回复(0)
侯卿头像 侯卿
😑无语，看成2n个节点。。
发表于 2017-12-22 01:15:49 回复(0)
提交观点

问题信息

链表
上传者：星辰大海的碎片
难度：
7条回答 5997浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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