完全二叉树叶子节点个数计算问题

设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为______。
A. 349
B. 350
C. 255
D. 351




O.O!莫非是我算错了o.o?~~~~~为什么我算得结果是344呢~~~~~~~~~~这道题貌似没有直接公式，就算是有不好意思啊我不是太会记公式的人，但是题目的思路很简单，首先通过节点数求出完全二叉树的高度h，这个公式你知道的吧，计算出来结果应该是9，然后你再用节点总数减去前八层的节点数之和就是你所求的结果~~~~

嗯嗯，我又看了看，选b，这个题目没有现成的公式，考验的是你对二叉树的理解能力与数学的思想，首先求出树的高度h，h应该是10不是9，上面我算错了T.T，然后求出一到九层的节点总数，应该是2的9次方减去1，是511，再用节点总数减去255就是最后一层叶子节点的个数699-511=188，而最后一层有188个节点就说明上一层有94个非叶节点，你在用该层的节点总数减去这些非叶子节点就是这一层的叶子节点数，及256-94=162，最后两层的叶子节点数之和就是188+162=350个，所以选B~

----
link: http://zhidao.baidu.com/question/175277118.html?fr=qrl&index=0

评论

1 楼 Rannn 2013-08-28  

我只是偶尔路过的。
二叉树的深度为lg(n) 叶子为2^(L-1) L为深度
所以叶子数量为2^(lg(n)-1) = 2^lg(n)/2 = n/2
二叉树有699个结点那么699 ~= 700/2 = 350 可得答案B