●在n个结点的线索二叉链表中,有 (49) 个线索指针。(49) A.n B.n－1 C.n＋1 D.n＋10

Question

●在n个结点的线索二叉链表中，有 (49) 个线索指针。

(49) A．n

B．n-1

C．n+1

D．n+10

Answer 1

正确答案：C
【解析】线索二叉树是利用空闲的子链域来存放某种遍历次序下的直接前驱结点或直接后继结点的地址的二叉树。因为二叉树的每个结点有且仅有两个链域，则n个结点的二叉树，有2n个子链域。又因为除根结点之外，其他每个结点都有且仅有一个进入支，这样就共有n-1进入支；而这n-1分支是由上一层的结点的子链域发出的，因此，2n个子链域中有，n-1个链域是指向子结点的，其他n+1个链域空闲看着。经过线索化以后，这些原来空闲着的n+1个链域被用来指向前驱或后继，即用来存放线索。所以在n个结点的线索二叉链表中，有n+1个线索指针。