试题五
阅读以下说明和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的左子树或右
对于二叉查找树(Binary Search Tree)，若其左子树非空，则左子树上所有节点的值均小于根节点的值：若其右子树非空，则右子树上所有节点的值均大于根节点的值；左、右子树本身就是两棵二叉查找树。因此，对任意一棵二叉查找树进行 (58) 遍历可以得到一个节点元素的递增序列。在具有n个节点的二叉查找树上进行查找运算，最坏情况下的算法复杂度为 (59) 。
（58）处填（）。对于二叉查找树（Binary Search Tree），若其左子树非空，则左子树上所有结点的值均小于根结点的值；若其右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身就是两棵二叉查找树。因此，对任意一棵二叉查找树进行 （61） 遍历可以得到一个结点元素的递增序列。在具有n 个结点的二叉查找树上进行查找运算，最坏情况下的算法复杂度为（62） 。
（61）处填（）。我来回答:
