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

Question

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

A．m-n-1

B．n+1

C．m-n+1

D．m-n

Answer 1

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