己知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是_______。

admin2015-12-30 45

问题己知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是_______。

选项 A、115
B、116
C、1895
D、1896

答案D

解析树转换为二叉树时，树中每一个分支结点的所有子结点中的最右子结点无右孩子，根结点转换后也没有右孩子，因此，对应的二叉树中无右孩子的结点个数=分支结点数+1=2011-116+1=1896。通常本题应采用特殊法解，设题意中的树是如下图所示的结构，则对应的二叉树中仅有前115个叶结点有右孩子，故无右孩子的结点个数=2011-115=1896。