假设根结点的层数为1,并设具有n(n≥3)个结点的二叉树的最大高度为h,设达到最大高度h时,不同的二叉

Question

假设根结点的层数为1，并设具有n(n≥3)个结点的二叉树的最大高度为h，设达到最大高度h时，不同的二叉树的数目为m。有以下说法： ①h≤n ②h=[log2n]+1 ③m=1 ④m=2 ⑤m=2n-1其中正确的个数有______个。

A．1

B．2

C．3

D．4

Answer 1

正确答案：B
解析：显然，当二叉树的每一层只有一个结点时，它最高，因此有h=n，于是①正确。注意，“≤”是小于或等于的意思，只要其中一个成立便可使用，如2≤2是成立的。②显然不正确，它求出的是有n个结点的完全二叉树的高度。当二叉树的每一层只有一个结点时达到最大高度，这时，除根结点外，每一层的结点可以放在左边也可以放在右边，根据乘法原理，可得m=2n-1。注意到n3，所以m≠1、m≠2，事实上，当不管是否n3，都可以用m=2n-1来统一表达。