一个完全二叉树上有101个结点,其中叶子结点的个数应该是多少,为什么?用下面公式,公式：2的（k-1）次方-1101我已推出K=7,后面的就不会了.应该是第6层+第7层

Question

一个完全二叉树上有101个结点,其中叶子结点的个数应该是多少,为什么?用下面公式,
公式：2的（k-1）次方-1101
我已推出K=7,后面的就不会了.应该是第6层+第7层

Answer 1

K = 7层,完全二叉树就是满二叉去掉或者不去掉右边底层的一些东西.所以你能确定的就是这棵树高度7并且前6层是满二叉树.前6层结点个数应该是2的（K）次方-1 即63个结点.剩余结点个数为 38个结点.也就是说这38个结点处在第七层.当前这叶子结点包含这38个.对于第七层应该具有的结点数目为 2的（k-1）也即是 2的6次方64个结点.那么剩余64-38 = 26个结点就是空结点（假想）.这26个结点对应第六层的13个结点.那么 13+38 = 51个结点.就是所求的叶子结点.不知道这么算有道理不.