Question

一个完全二叉树,若编号为40的结点有右子结点,则这棵完全二叉书至少有多少结点?

Answer 1

因完全二叉树： 某一层的结点数据为2^n, n 代表从树根开始的层次编号, 树根层次为0.

2^5 = 32;

2^6 = 64;

40 > 32 && 40 < 64;

所以编号为40的结点一定在第6层次上, 又因其有右子结点.

至少要再增加一层, 这棵树至少有7层.

所以这棵的所有结点 = 2^0 + 2^1 +... + 2^7　= 2^8 - 1 =128 -1 = 127;