问题 单项选择题

设森林F对应的二叉树为B,它有m个节点,B的根为p,p的右子树上的节点个数为 n,森林F中第一棵树的节点个数是

A.m-n-1

B.n+1

C.m-n+1

D.m-n

答案

参考答案:D

解析:根据二叉树与森林的对应关系,将森林F转换成对应二叉树B的规则如下:若森林F为空,则二叉树B为空。若森林F非空,则F中的第一棵树的根为二叉树B的根;第一棵树的左子树所构成的森林按规则转换成一个二叉树成为B的左子树,森林F的其它树所构成的森林按本规则转换成一个二叉树成为 B的右子树。依此规则可知:二叉树B节点的个数减去其右子树的节点的个数就是森林F的第1棵树的节点的个数。

单项选择题 共用题干题
名词解释