计算⼆叉树中叶⼦结点个数的⽅法
基础知识:
1.⼆叉树第i层最多有2^(i-1)个结点。
2.深度为k的⼆叉树⾄多有2^k-1个结点。
⼀个完全⼆叉树有七百个结点,问该⼆叉树有多少个叶⼦结点
根据“的第i层⾄多有2^(i − 1)个;深度为k的⾄多有2^k − 1个(的深度为1)”这个性质:
因为2^9-1 < 700 < 2^10-1 ,所以这个的深度是10,前9层是⼀个,完全二叉树算法
这样的话,前九层的就有2^9-1=511个;⽽第九层的结点数是2^(9-1)=256
所以第⼗层的数是700-511=189个;
现在来算第九层的个数。
由于第⼗层的是从第九层延伸的,所以应该去掉第九层中还有⼦树的结点。因为第⼗层有189个,所以应该去掉第九层中的(189+1)/2=95个;
所以,第九层的叶⼦结点个数是256-95=161,加上第⼗层有189个,最后结果是350个。
⼀个有 800 个结点的完全⼆叉树,问有_____个叶⼦结点?
答案:400