Question

设一棵完全二叉树共有700个结点,求该二叉树有几个叶子结点?

Answer 1

350个

如果是满二叉树,深度为m,则会有2^m-1个节点.

先判断二叉树的深度,700介于2^9-1和2^10-1之间,所以这个完全二叉树的深度为10.

第九层以上的二叉树为满二叉树,共有2^9-1=511个节点.

第十层上的叶子节点的个数为700-511=189,这些叶子节点的双亲个数为189div2=95.

第九层的节点个数为2^(9-1)=256,第九层上的叶子节点的个数为256-95=161.

所以共有叶子节点个数189+161=350