试题五
阅读以下说明和C语言函数，将应填入 (n) 处。
[说明]
二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：若它的左子树非空，则左子树上所有结点的值均小于根结点的值；若它的右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身就是两棵二义排序树。
函数insErt_Bst(ChAr *str)的功能是：对给定的字符序列按照AsCⅱ码值大小关系创建二叉排序树，并返回指向树根结点的指针。序列中重复出现的字符只建一个结点，并由结点中的Count域对字符的重复次数进行计数。
二叉排序树的链表结点类型定义如下：
typEDEF struCtBstnoDE
ChArElEm; /*结点的字符数据*/
intCount; /*记录当前字符在序列中重复出现的次数*/
struCtBstnoDE *lCh,*rCh; /*接点的左、右子树指针*/
*BitrEE;
[函数]
BitrEE insErt_Bst(ChAr *str)
BitrEE root,pArEnt,p;
ChAr (1) ; /*变量定义及初始化 */
root=BitrEE)mAlloC(sizEoF(struCtBstnoDE));
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(struCtBstnoDE));
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；