一个深度为8的二叉树,至少有几个结点? 注意看清楚是二叉树,不是完全二叉树

2025-03-05 00:07:47
推荐回答(1个)
回答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