设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有()个

本文主要是介绍设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有()个，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、问题

设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有( C )个

A.n-1
B.n
C.n+1
D.n+2

分析：
求解该问题时需要了解的概念规则：
1️⃣概念
终端结点：度为0的结点。（叶子结点）
非终端结点：度>0的结点。（非叶子结点）
2️⃣规则
森林与二叉树转换规则：左孩子右兄弟。
该规则的基本思想是：对于树中的每个结点，只保留它与第一个孩子结点的连线，将其他孩子结点看作第一个孩子结点的兄弟结点，用右指针连接起来。这样，每个结点就只有两个指针：左指针指向第一个孩子结点，右指针指向下一个兄弟结点。这种表示法可以保证树或森林的层次结构不变，同时利用二叉树的性质进行操作。

那么根据这些，首先我们可以拟定一个思路，就是先求总的空指针域数，减去左指针域为空的个数，最终得到的就是右指针域为空的结点数。

二、思路实现

第一步，求总的空指针域数（总的空指针域数 = 总的指针域数 - 已被占用的指针域数）
已知，森林F，二叉树B，F有n个非终端结点。

假设那么我们可以假设森林的终端结点数为m，那么森林的总结点数为m+n。
二叉树B每个结点有两个指针（二叉链表存储），故总的指针数就是2（m+n）；

根据左孩子右兄弟的方法，二叉树除了根节点，其它结点都是某个结点的孩子，即一定会有指针指向它，则此时已被使用的指针域数为m+n-1（-1是去掉了根节点的部分）。

因此总的空指针域数 = 2(m+n) - (m+n-1) = m+n+1 个 ①
第二步，求空的左指针域的个数

由于m个终端结点是没有孩子结点的，所以根据左孩子右兄弟，森林F转换成二叉树B后，这些结点的左指针一定为空（因为左指针域指向的是它第一个孩子，它没有孩子结点，故为空），所以空的左指针域个数为m个 ②。
第三步，根据二者关系求出B中右指针域为空的结点数（右指针域为空的结
联立①②，可得：
右指针域为空的结点数 = ① - ② = (m+n+1) - m = n+1个。
故本题选C，右指针域为空的结点数有n+1个。