由关键字序列(12，7，36，25，18，2)构造一棵二叉排序树(初始为空，第一个关键字作为根结点插入，此后对于任意关键字，若小于根结点的关键字，则插入左子树中；若大于根结点的关键字，则插入右子树中，且左、右子树均为二叉排序树)，该二叉排序树的高度(层数)

admin2019-01-10 43

问题由关键字序列(12，7，36，25，18，2)构造一棵二叉排序树(初始为空，第一个关键字作为根结点插入，此后对于任意关键字，若小于根结点的关键字，则插入左子树中；若大于根结点的关键字，则插入右子树中，且左、右子树均为二叉排序树)，该二叉排序树的高度(层数)为 (39)。

选项 A、6
B、5
C、4
D、3

答案C

解析本题考查数据结构基础知识。二叉排序树(Binary Son Tree)或者是一棵空树，或者满足以下递归条件。①二叉排序树的左、右子树各是一棵二叉排序树。②若二叉排序树的左子树非空，则其左子树上的各结点值均小于根结点的值。③若二叉排序树的右子树非空，则其右子树上的各结点值均大于根结点的值。根据该定义，由关键字序列(12，7，36，25，18，2)构造的二叉排序树如下图所示。