题2
题目
Q:利用二叉链表存储森林时, 根结点的右指针是 ( ).
A. 指向最左兄弟
B. 指向最右兄弟
C. 一定为空
D. 不一定为空
分析
A:什么叫做用二叉链表存储森林，是怎么存储的
也就是说，先把森林转成二叉树树，然后把转成的二叉树用二叉链表进行存储，二叉链表表示法就是孩子兄弟表示法
孩子兄弟表示法使每个结点包括三部分内容:
结点值、指向结点第一个孩子结点的指针, 以及指向结点下一个兄弟结点的指针 (沿此域可以找到结点的所有兄弟结点)
解
D
森林与二叉树具有对应关系, 因此, 我们存储森林时应先将森林转换成二叉树, 转换的方法就是 “左孩子右兄弟”, 与树不同的是, 若存在第二棵树, 则二叉链表的根结点的右指针指向的是森林中的第二棵树的根结点。
若此森林只有一棵树, 则根结点的右指针为空。
因此, 右指针可能为空也可能不为空。