题8

题8

题目

Q:设 是一个森林, 是由 变换来的二叉树. 若 中有 个非终端结点,则 中右指针域为空的结点有 ( ) 个.
A.
B.
C.
D.

分析

A:什么叫做树的终端结点和非终端结点
森林的二叉树是用二叉链表存储的
二叉链表又名左孩子右兄弟表示法

5.4-树、森林#3-孩子兄弟表示法

总结起来二叉树表示法就是，左指针指孩子，右指针指兄弟

解

C
根据森林与二叉树转换规则 “左孩子右兄弟”。二叉树 中右指针域为空代表该结点没有兄弟结点。
森林中每棵树的根结点从第二个开始依次连接到前一棵树的根的右孩子, 因此最后一棵树的根结点的右指针为空。
另外, 每个非终端结点, 其所有孩子结点在转换之后, 最后一个孩子的右指针也为空,所以树 中右指针域为空的结点有 个。