12、已知一棵完全二叉树的结点总数为9个,则最后一层的结点数为已知一棵完全二叉树的结点总数为9个,则最后一层的结点数为?为什么答案是2

Question

12、 已知一棵完全二叉树的结点总数为9个,则最后一层的结点数为
已知一棵完全二叉树的结点总数为9个,则最后一层的结点数为?
为什么答案是2

Answer 1

满二叉树：每一层上的节点数均达到最大值；
完全二叉树：除最后一层外,每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点.
按照定义,7个节点画出来的完全二叉树一定是长这样子的
1
2 3
4 5 6 7
8 9
所以最后一层有俩节点,按照公式算：
最后一层 = N - (2^(H - 1) - 1)= 9 - 7 = 2
H为高度,H=向上取整(log(N + 1))