问题
单项选择题
结点数目为n的二叉查找树(二叉排序树)的最小高度为 (52)、最大高度为 (53)。
(53)处填()。
A.n
B.
C.[log2n]
D.[log2(n+1)]
答案
参考答案:A
解析:
(52)、(53)
[分析]:
本题考查二叉排序树的基本构造特点。
若二叉树中有n个结点,则结点分布均匀、且高度最小的树的特点是除了最后一层,其余各层的结点数目都达到最大值(第i层上有2t-1个结点),此时树的高度为 [log2(n+1))。若每层只有一个结点,则树的高度为n。 具有三个结点的二叉树的所有形态如下所示,每层只有一个结点时称为单枝树。
二叉排序树是根据输入序列构造的,当序列呈现有序的特点时,就构造出一棵单枝树。