Question

有谁知道为什么n个元素的三叉链表的空指针域是n+2？

想不通为什么...

Answer 1

三叉链表的结点数为
n，那么指针域一共有
3*n
个。我们知道，n
个结点的二叉树一共有
n-1
条边（除了根节点外，每个节点都有一条边指向它，所以是
n-1
条边）。根据这一规律，在三叉链表中，不难知道指向子节点的指针域有
n-1
个，指向父节点的指针域也有
n-1
个。
3*n
-
2*(n-1)
=
n+2。
所以答案就是
n+2。