问题 单项选择题

结点数目为n的二叉查找树(二叉排序树)的最小高度为 (52)、最大高度为 (53)

(53)处填()。

A.n

B.

C.[log2n]

D.[log2(n+1)]

答案

参考答案:A

解析:

(52)、(53)

[分析]:

本题考查二叉排序树的基本构造特点。

若二叉树中有n个结点,则结点分布均匀、且高度最小的树的特点是除了最后一层,其余各层的结点数目都达到最大值(第i层上有2t-1个结点),此时树的高度为 [log2(n+1))。若每层只有一个结点,则树的高度为n。 具有三个结点的二叉树的所有形态如下所示,每层只有一个结点时称为单枝树。

 

二叉排序树是根据输入序列构造的,当序列呈现有序的特点时,就构造出一棵单枝树。

选择题
问答题