Question

设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为多少？

(13) 设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为______。()
A. 349
B. 350
C. 255
D. 351
要解答过程，我不会做

Answer 1

B：350
首先你得知道什么叫完全二叉树！
完全二叉树(Complete Binary Tree)
若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的节点都连续集中在最左边，这就是完全二叉树。 完全二叉树是由满二叉树而引出来的。对于深度为K的，有N个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
做这种题目你要知道二叉树的两个特点！第k层的节点个数最多2^(k-1)个，高度为k层的二叉树，最多2^k-1个节点！
则在本题目中，共699个节点，因为是完全二叉树，2^10-1>699>2^9-1，所以高度为10，可以确定1到9层全满，节点总算为511，剩下的188个肯定为叶子节点！第10层上的188个节点挂在第九层的188/2=94个节点上，则第九层剩下的2^（9-1）-94=162个也为叶子节点，最后总共188+162=350个叶子节点！

Answer 2

由完全二叉树的节点总数为2h－1（h为二叉树的高度），所以2h－1=699
可得出高度h=10.
又前九层有29－1=511，所有叶子节点数为699－511=188.

Answer 3

如果是做选择题记得公式（N+1） /2就行