下列关于二叉排序树，描述错误的是（）

给定序列{3，5，7，9，11，13，15，17)，

(1)按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求在等概率情况下查找成功的平均查找长度。

(2)按表中元素的顺序构造一棵平衡二叉树，并求其在等概率情况下查找成功的平均查找长度。

阅读以下说明和C语言函数，将应填入(n)处。

[说明]

二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：若它的左子树非空，则左子树上所有结点的值均小于根结点的值；若它的右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身就是两棵二义排序树。

函数insert_BST(char *str)的功能是：对给定的字符序列按照ASCⅡ码值大小关系创建二叉排序树，并返回指向树根结点的指针。序列中重复出现的字符只建一个结点，并由结点中的Count域对字符的重复次数进行计数。

二叉排序树的链表结点类型定义如下：

typedef struct BSTNode{

char Elem; /*结点的字符数据*/

int Count; /*记录当前字符在序列中重复出现的次数*/

struct BSTNode *Lch,*Rch; /*接点的左、右子树指针*/

}*BiTree;

[函数]

BiTree insert_BST(char *str)

{ BiTree root,parent,p;

char (1); /*变量定义及初始化 */

root=(BiTree)malloc(sizeof(struct BSTNode));

if(!root||*s=='\0') return NULL;

root-＞Lch=root-＞Rch=NULL; foot-＞Count=1; root-＞Elem=*s++;

for(; *s!='\0';s++) {

(2); parent=NULL;

while (p){ /*p从树跟结点出发查找当前字符*s所在结点 */

parent = p;

if(*s==p-＞Elem)/*若树中已存在当前字符结点，则当前字符的计数值加1*/

{p-＞Count++; break;}

else /*否则根据字符*s与结点*p中字符的关系，进入*p的左子树或右子树*/

if (*s＞p-＞Elem) p=p-＞Rch;

else p=p-＞Lch;

}/*while*/

if( (3)) {/* 若树中不存在字符值为*s的结点，则申请结点并插入树中 */

p=(BiTree)malloc(sizeof(struct BSTNode));

if(!p)return NULL;

p-＞Lch=p-＞Rch=NULL; p-＞Count=1; p-＞Elem=*s;

/*根据当前字符与其父结点字符值的大小关系，将新结点作为左子树或右子树插入*/

if(p-＞Elem＞parent-＞Elem) (4)=p;

else (5)=p;

}

}/*for*/

return root；

}

给定表{19,14,22,01,66,21,83,27,56,13,10}，试按元素在表中的次序将它们插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树。

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

A．6

B．5

C．4

D．3

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

A．6

B．5

C．4

D．3

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

（39）

A. 6

B. 5

C. 4

D. 3

已知如下所示长度为12的关键字有序的表:

{Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec}

1)试按表中元素的顺序依次插入到一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

2)若对表中元素先进行排序构成有序表，求在等概率的情况下查找成功的平均查找长度。

3)按表中元素的顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

设一组初始记录关键字序列为(20，12，42，31，18，14，28)，则根据这些记录关键字构造的二叉排序树的平均查找长度是_______________________________。

根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为____________。