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

Question

想不通为什么...

Answer 1

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

参考资料：http://baike.baidu.com/view/2192687.htm

Answer 2

1、A 删除链表结点，直接为p->next=p->next->next;
2、B 用链表的话，可以动态分配空间，因此只要考虑是否为空，不会出现满的情况。
3、A 此题目是求子串的问题，意思是求主串第5个开始长度为9的子串
4、B 其实B答案包括了C和D答案，搞清先序、后序的概念应该不难。
5、B 此题相当一个等比数列，1+3+9+27=40 和完全三叉树的概念

1、2n, n+1 此题考的是线索二叉树部分，其中除根结点外所有的结点都必须用指针域连接，应该用到n-1所以当然有N+1个没有被用到。
2、CBA 其实这个题目和前面的那个选择题相似，画出二叉树就只有右孩子的二叉树
3、i=i+1, j=0; 就是子符串的朴素算法
4、ABCDE为层序，画链式很简单，先序：ABDEC,中序：DBEAC后序：DEBCA
5、方程1：n0+n1+n2=n 方程2：n1+2*n2=n-1 得n2=n0-1, 这一问和上面一样同样是n-1个，但是此处应该写成：2*n0+n1-1
6、最少为深度k-1的树再加一个 即：2^(k-1)
7、和前面一样
8、以2为底的log128求整数就行，第二问，三个方程解三个未知数，
方程1：n0+n1+n2=128 方程2：n1+2*n2=128-1 方程3：n1=1 (对于完全二叉树且128为偶数)
9、先画出来，再写，答案：DEBCA
追问

你脑子没病吧，兄弟...