【数据结构】设F是一个森林,B是由F变换得的二叉树。若F中有n个非终端结点,则B中右指针域为空的结点有多少个
在森林的每一颗子树中,转化二叉树后右指针域为空代表着这个节点是兄弟组的最后一个,再往右没有兄弟了。所以有多少个兄弟组就有多少右指针域为空。每个兄弟组都有自己的父亲,父亲就是非终端结点(分支结点)。
所以每棵子树转化后右指针域为空的结点树等于非终端结点(分支结点)。
又因为所有根结点转化后,最右边的根结点右指针域也为空。
所以最终转化后右指针域为空的结点总数为:
非终端结点数+1。