一个深度为k的，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依此对结点编号，则编号最小的叶子的序号

Question

18.一个深度为k的，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依此对结点编号，则编号最小的叶子的序号是（ ）。
2^(​k−2)+1
这个编号最小的叶子，想知道为什么是k-2次方，不是k-1次方吗，

Answer 1

先看定义：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
符合题意的完全二叉树最后一层（第k层）只有一个节点，它的编号是2^(k-1)-1+1=2^(k-1)。但是，最小编号的叶子结点在倒数第二层，因为倒数第二层有大量的结点没有子树，它们也是叶子结点。因此最小的叶子结点就是倒数第二层的第二个结点，它的编号是2^(k-2)-1+2=2^(k-2)+1。
如果我的回答对你有帮助，还望采纳。