违法和不良信息举报 联系客服
免费注册 登录

请教:计算机等级考试二级公共基础知识练习题(1)第2大题第11小题如何解答? 【题目描述】 (11)设一棵完全二叉树共有 500 个结点，则在该二叉树中有______个叶子结点。

题目
请教:计算机等级考试二级公共基础知识练习题(1)第2大题第11小题如何解答?

【题目描述】

 (11) 设一棵完全二叉树共有 500 个结点，则在该二叉树中有______个叶子结点。

 

参考答案和解析

【参考答案分析】：

答：250

设no为度为0的节点数
  n1为度为1的节点数
  n2为度为2的节点数
n=n0+n1+n2  (1)
根据二叉树定义
n=n1+2*n2+1  (2)
由(1)(2)得
n2=n0-1      (3)
(3)代入(1)
n=2n0+n1-1
500=2n0+n1-1
n1只可能为1或0这里显然为1
n0=250
根据二叉树的性质:对于一棵非空的二叉树,如果叶子节点数为n0,度为2的结点数为n2,则n0=n2+1. 
根据完全二叉树的定义可得:在完全二叉树中度为1的结点n1只能取两种情况,要么为0,要么为1. 
所以:n0+n1+n2=500 
n0=n2+1; 
2n0=501-n1; 
因为结点数为整数，所以n1=1,n0=250 
更多“请教:计算机等级考试二级公共基础知识练习题(1)第2大题第11小题如何解答? 【题目描述】 (11)设一棵完全二叉树共有 500 个结点，则在该二叉树中有______个叶子结点。”相关问题
相关内容