Question

100个结点的二叉树采用三叉链表存储时,空指针域NULL有__________个.

求详解

Answer 1

100个结点的二叉树用三叉链表存储共有101+ 1 = 102个空指针域
1代表双亲指针，只有根没有双亲
101：每个结点有两个孩子域，因此一共100*2= 100个指针域，但100个结点中间的连接边一定是100-1=99个，所以空的指针域有200-99=101，也就是n个结点有n+1个空的指针域
这样加上双亲域，n个结点的三叉链表共有n+2个空指针域

Answer 2

引用chiconysun的回答：
100个结点的二叉树用三叉链表存储共有101+ 1 = 102个空指针域
1代表双亲指针，只有根没有双亲
101：每个结点有两个孩子域，因此一共100*2= 100个指针域，但100个结点中间的连接边一定是100-1=99个，所以空的指针域有200-99=101，也就是n个结点有n+1个空的指针域
这样加上双亲域，n个结点的三叉链表共有n+2个空指针域

100个结点的二叉树用三叉链表存储共有101+ 1 = 102个空指针域
1代表双亲指针，只有根没有双亲
101：每个结点有两个孩子域，因此一共100*2=200个指针域，但100个结点中间的连接边一定是100-1=99个，所以空的指针域有200-99=101，也就是n个结点有n+1个空的指针域
这样加上双亲域，n个结点的三叉链表共有n+2个空指针域