问题 单项选择题

在任意一棵非空的二叉树中,终端结点(叶子)的数目总是比具有两个孩子的非终端结点的数目()。

A.多0个

B.多1个

C.多2个

D.多3个

答案

参考答案:B

解析:

[分析]: 本题考查数据结构基础知识。

设度为2的结点数为n2,度为0的结点(叶子结点)数为n0,度为1的结点数为 n1,则树中结点总数为n2+n1+n0,树中除根之外的结点有唯一的父结点(即度为1的结点或度为2的结点)。也就是说,除根之外的结点都是由度为1的结点或度为2的结点派生出来的,即树中结点总数为2×n2+1×n1+1。

综上,n2+n1+n0=2×n2+1×n1+1,所以n0=n2+1。

单项选择题
单项选择题