某棵完全二叉树上有698个节点,则该二叉树的叶子节点数为
A.349
B.350
C.255
D.351
正确答案是 A
首先明确完全二叉树的概念:最下面两层有度数小于2的节点,且最下面一层的叶节点集中在最左边的若干位置上。因为2^9 - 1 < 698 < 2^10 - 1,所以共有10层,前九层的节点数为2^9 - 1 = 511,第十层为689 - 511 = 187。187/2 = 93余1,所以第九层有93个度为2的节点,一个度为1的节点。
第九层叶节点为 256 - 94 = 162; 第十层叶节点为 187; 叶节点总数为 187 + 162 = 349.
帖子还没人回复快来抢沙发
从浏览器输入URL到展示页面的全流程是怎么样的?
使用js实现数组的快速排序
叉树前序遍历的递归和非递归实现?
B2C网站上促销价格出错了,如何做危机公关?
帖子还没人回复快来抢沙发