Question

已知一棵完整的二叉树的第六层(设跟结点为第一层)有8个叶子结点，则该完全二叉树的结点个数最多是多少

已知一棵完整的二叉树的第六层(设跟结点为第一层)有8个叶子结点，则该完全二叉树的结点个数最多是多少？最少是多少？

Answer 1

第6层有8个叶子，因此可知，最少时就是第6层有而且只有8个叶子结点，此时到第5层为满二叉树，最多就是第6层除了8个叶子外，都是度为2的结点，该层度为2结点个数为2^(6-1) - 8 = 24，也就是说除了到第6层是满二叉树外，还有7层，而且第7层有24*2 = 48个结点
最少：(2^5 - 1)+ 8= 31 + 8 = 39
最多：(2^6 - 1) + 48= 63 + 48 = 111