设二叉树共有150个结点,其中度为1的结点有10个,则该二叉树中的叶子结点...

发布网友发布时间：2024-09-28 07:27

共2个回答

热心网友时间：2024-10-31 10:00

二叉树有如下性质：N0 = N2 + 1，即叶子节点等于度为2节点个数加1
证：结点总数n = n0 + n1 + n2。设B为分支总数，因为除根节点外，其余结点都有一个分支进入，所以n = B + 1。又因为分支是由度为1或2的结点射出，所以B = n1 + 2n2。综上：n = n0 + n1 + n2 = B + 1 = n1 + 2n2 + 1，得出：n0 = n2 + 1

本题，度为1的结点个数为10，所以度为2结点 + 叶子节点个数=n0 + n2 = 150 -10 =140
在根据上述n0 = n2 + 1公式，n2 = 69.5
所以不可能有这样的二叉树，答案选D

热心网友时间：2024-10-31 10:02

二叉树结点种类为三种：度为0的结点，即叶子结点；度为1的结点；度为2的结点。
所有二叉树共有的一个性质是：度为0的结点永远比度为2的结点多1个。
这题的解答如下：假设度为0的结点数为x个，则x＋10＋x－1＝150，则x＝70.5，不可能有小数的结点个数，所以选择D，不可能有这样的二叉树。