Question

关于完全二叉树

一棵具有n个结点的完全二叉树中，分支结点的最大编号为？。假定根节点编号为零。
最好有推到过程

Answer 1

假设你是按层从左向右编号，根结点编号为0，

结点总数 = N

层数L = UPPER(log(N)/log(2));
其中：upper(x)是指取不小于X的最小整数。

底层结点数M = N-2^(L-1)+1

底层的上一层结点数X = 2^(L-2)

分支结点的最大编号= 2^(L-1)-2-(X-UPPER(M/2))

因此，总的公式是：

分支结点的最大编号 =
2^(UPPER(log(N)/log(2))-1)-2
-(2^(UPPER(log(N)/log(2))-2)
-UPPER((N-
2^(UPPER(log(N)/log(2))-1)+1)/2))