题目
15、二叉树共有150个结点,其中度为1的结点有10个,则该二叉树中的叶子结点数为()。A. 不可能有这样的二叉树B. 69C. 71D. 70
15、二叉树共有150个结点,其中度为1的结点有10个,则该二叉树中的叶子结点数为()。
A. 不可能有这样的二叉树
B. 69
C. 71
D. 70
题目解答
答案
A. 不可能有这样的二叉树
解析
本题考查二叉树的性质,解题思路是根据二叉树中结点度数与结点总数的关系来判断是否存在这样的二叉树。
在二叉树中,结点的度指的是该结点拥有的子树的数目。设二叉树中度为 0 的结点数(即叶子结点数)为 $n_0$,度为 1 的结点数为 $n_1$,度为 2 的结点数为 $n_2$,则二叉树的结点总数 $n=n_0 + n_1 + n_2$。
同时,根据二叉树的性质,有 $n_0=n_2 + 1$,将其代入到结点总数公式中可得 $n=n_0 + n_1 + n_0 - 1=2n_0 + n_1 - 1$。
已知该二叉树共有 $n = 150$ 个结点,其中度为 1 的结点有 $n_1 = 10$ 个,将这些值代入到 $n=2n_0 + n_1 - 1$ 中,可得:
$\begin{align*}150&=2n_0 + 10 - 1\\150&=2n_0 + 9\\2n_0&=150 - 9\\2n_0&=141\\n_0&=\frac{141}{2}=70.5\end{align*}$
由于结点数必须是整数,而计算得到的叶子结点数 $n_0 = 70.5$ 不是整数,所以不可能有这样的二叉树。