问答题

试题五
阅读以下说明和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；
}