vlambda博客
学习文章列表

撰稿 | 康康哥

编辑 | 丽丽姐

本文由懂计算机、软件工程的博士师哥提供

已知一棵有2011个节点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是（     ）

A.  115

B.  116

C.  1895

D.  1896

本题考查：二叉树结点计算

设非空的左链域有XL个，非空的右链域有XR个，那么XL+XR+1=2011（总节点数为根节点加左右孩子数）

且因为二叉树是由树转化而来，因此节点在树中至少要有一个孩子才能在转化为二叉树后有左孩子（也就是非叶节点），有2011-116个节点在二叉树中有左孩子，因此XL=2011-116，代入上式可得2011-116+XR+1=2011， XR=115。

由此， 空的右链域=2011(右链域数)-XR=1896个，得解。

故选 D

软工博士带你飞
考软工 · 看CS优化狮