问答题 试题五（共15 分） 阅读以下说明和C 语言函数，将应填入 （n） 处的字句写在答题纸的对应栏内。 [说明] 二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：若它的左子树非空，则左子树上所有结点的值均小于根结点的值；若它的右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身就是两棵二叉排序树。 函数insert_BST (char *str)的功能是：对给定的字符序列按照ASCII 码值大小关系创建二叉排序树，并返回指向树根结点的指针。序列中重复出现的字符只建一个结点，并由结点中的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; root->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; }