我要招人

去企业版

首页 > 试题广场 >

用三叉链表作二叉树的存储结构，当二叉树中有n个结点时，有()

[单选题]

用三叉链表作二叉树的存储结构，当二叉树中有n个结点时，有()个空指针。

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

查看正确选项

Pandora

三叉链表每个节点有三个指针域（左、亲、右），共3n个指针。

其中非空指针=亲（n-1个，因为根节点没有双亲）+左右（n-1，因为n个节点的二叉树有n-1条边）=2n-2；

所以空指针=3n-(2n-2)=n+2。

发表于 2015-10-30 16:27:35 回复(2)

神说

三叉链表，每个节点有三个指针，左孩子，右孩子，父节点。

对于有n个节点的树结构，有n-1条边，每条边是孩子节点指向父节点的指针，也是父节点指向孩子节点的孩子指针，所以一共是2(n-1)个指针，总的指针就是3n-2(n-1)=n+2

发表于 2015-11-02 11:09:24 回复(4)

心静

三叉链表是二叉树的另一种主要的链式存储结构。三叉链表与二叉链表的主要区别在于，它的结点比二叉链表的结点多一个指针域，该域用于存储一个指向本结点双亲的指针。三叉链表的结点形式如下：

发表于 2015-10-31 21:43:57 回复(0)

thfeng

n=1 时，只有根节点，空指针的个数为3 C正确

发表于 2016-07-27 11:17:52 回复(1)

main方法栈帧

根据个人理解画了一张图

发表于 2021-11-20 10:31:30 回复(0)

fudanyuan

二叉树总的节点个数为n = n0 + n1 + n2; 其中 n0 = n2 + 1;

而空指针的个数来源🈶️3个：叶子节点 * 2 + 只有一个孩子的节点 + 根节点（根节点中无父节点）

即 m = 2 * n0 + n1 + 1; 综上可得 m = n + 2.

发表于 2018-10-10 13:35:23 回复(0)

静默成诗.

普通二叉链表的有n个结点的二叉树，将当前二叉树中的空指针看做叶子结点，则树中原有的所有结点都成了双分支结构。因此由n0=n2+1可得空指针个数为n+1个，而三叉链表中只有根结点没有双亲结点指针为空，故空指针为n+2。

发表于 2018-08-24 01:33:06 回复(0)

恶寒轻轻

三叉链表结点：左孩子，右孩子，父节点，n个结点的二叉树有n-1条边，即对应2(n-1)个指针域（即一条边对应一个孩子指针和一个父亲指针），总指针域数量为3n，故空域为n+2

编辑于 2021-12-03 12:16:18 回复(0)

Blizard223

高中时的特值法应该立马见效！如，3个结点的例子。

发表于 2016-09-16 18:26:03 回复(1)

李思考考考考

中间指针是用来指向父节点的，就解释通了。

发表于 2015-10-30 19:40:04 回复(0)

救赎i_

这题的错因是忘了三叉链表就是加了一个指向双亲的指针，我还以为是用三叉树的结点存储二叉树，算到最后结果每一个对的，我就乱选了一个。所以解法应该是，只有根结点的双亲指针为NULL，故双亲指针非空数目为n-1，左右孩子指针非空数目=孩子的个数=树的度=n-1，因此总空指针域=3n-(n-1)-(n-1)=n+2

发表于 2022-07-25 20:32:29 回复(0)