设只有根结点的二叉树高度为0,那么所有含16个结点的二叉树中,最小高度是多少?

Question

设只有根结点的二叉树高度为0,那么所有含16个结点的二叉树中,最小高度是多少?

Answer 1

首先：
结点数相同的二叉树中高度最小的是：完全二叉树
你可以这样算：
1) 第0层结点（即根结点）编号为2^0=1,
2) 第1层第一个结点编号为2^1=2
……
3) 第4层第一个结点编号为2^4=16.那么前0-3层总的结点数为16-1=15个.
所以这棵二叉树最小的高度,即二叉树的层数,为4.