已知一棵有2011个结点的树,其叶结点个数为116,该树对应的二叉树中无右孩子的结点个数是( )。
A. 115
B. 116
C. 1895
D. 1896
方法一:性质
树转换为二叉树...
用户登录可进行刷题及查看答案
树转换为二叉树,用的是“左孩子右兄弟”表示法。
树的根结点一定没有兄弟结点,在对应的二叉树中的结点无右孩子。根结点数量为 1 。
树中每一个分支结点(非叶结点)的所有孩子结点中最右孩子结点在对应的二叉树中的结点无右孩子。分支结点数为 2011−116=1895 。
总计 1+1895=1896 。
本题选D。
方法二:举例
构造一棵树,叶结点全部在最后一层。
所有蓝色的非叶结点在对应的二叉树中的结点都没有右孩子,最右边一个叶结点在对应的二叉树中的结点没有右孩子。
总计 1895+1=1896 。
登录后提交答案
暂无评论,来抢沙发