62二叉树 4、具有n个结点的完全二叉树的深度为og2n+1 证明:设所有完全二又树的深度为k,由完全二叉树的定义可知,它 的前k1层是深度为k-1的满二叉树,一共有2k1-1个结点。由 于完全二叉树深度为k,故第k层上还有若干个结点,因此, 该完全二叉树的结点个数n>2k1-1。 另一方面,由性质2可知n≤2k-1,即: 2k-1-1<n≤2k1 由此可推出:2k1≤n<2<1 取对数后有:k1≤log2n<k 因为k为整数,故有k1=log2n由此可得 k= log2n +16.2 二叉树 4、具有n个结点的完全二叉树的深度为log2n +1 证明：设所有完全二叉树的深度为k，由完全二叉树的定义可知，它 的前k-1层是深度为k-1的满二叉树，一共有2 k-1-1个结点。由 于完全二叉树深度为k，故第k层上还有若干个结点，因此， 该完全二叉树的结点个数n>2k-1-1。 另一方面，由性质2可知n≤2k-1，即： 2 k-1-1< n ≤2k-1 由此可推出： 2 k-1 ≤ n < 2k-1 取对数后有: k-1 ≤ log2n < k 因为k为整数，故有 k-1= log2n ,由此可得： k= log2n +1