niusouti.com
阅读以下说明和C语言函数，将应填入(n)处。[说明]二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：若它的左子树非空，则左子树上所有结点的值均小于根结点的值；若它的右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身就是两棵二义排序树。函数insert_BST(char *str)的功能是：对给定的字符序列按照ASCⅡ码值大小关系创建二叉排序树，并返回指向树根结点的指针。序列中重复出现的字符只建一个结点，并由结点中的Count域对字符的重复次数进行计数。二叉排序树的链表结点类型定义如下
题目
阅读以下说明和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；
}
相似考题
更多“阅读以下说明和C语言函数,将应填入(n)处。[说明] 二叉排序树或者是一棵空树,或者是具有如下性质的 ”相关问题
-
第1题：
阅读以下说明、C函数和问题，将解答填入答题纸的对应栏内。
【说明】
二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树：
●若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值;
●若它的右子树非空，则其右子树上所有结点的键值均大于根结点的键值;
●左、右子树本身就是二叉查找树。
设二叉查找树采用二叉链表存储结构，链表结点类型定义如下：
typedefstructBiTnode{
intkey_value;/*结点的键值，为非负整数*/
structBiTnode*left,*right;/*结点的左、右子树指针*/
}*BSTree;
函数find_key(root,key)的功能是用递归方式在给定的二叉查找树(root指向根结点)中查找键值为key的结点并返回结点的指针;若找不到，则返回空指针。
【函数】
BSTreefind_key(BSTreeroot,intkey)
{
if((1))
returnNULL;
else
if(key==root->key_value)
return(2);
elseif(keykey_value)
return(3);
else
return(4);
}
【问题1】
请将函数find_key中应填入(1)~(4)处的字句写在答题纸的对应栏内。
【问题2】
若某二叉查找树中有n个结点，则查找一个给定关键字时，需要比较的结点个数取决于(5).
答案：
(1)!root,或root=0,或root==NULL
(2)root
(3)find_key(root→left,key)
(4)find_key(root→right,key)
(5)该关键字对应结点在该二叉查找树所在层次(数)或位置，或者该二叉树中从根结点到该关键字对应结点的路径长度
解析：
本题考查数据结构的应用、指针和递归程序设计。
根据二叉查找树的定义，在一棵二叉查找树上进行查找时，首先用给定的关键字与树根结点的关键字比较，若相等，则查找成功;若给定的关键字小于树根结点的关键字，则接下来到左子树上进行查找，否则接下来到右子树上进行查找。如果在给定的二叉查找树上不存在与给定关键字相同的结点，则必然进入某结点的空的子树时结束查找。因此，空(1)处填入"!root"表明进入了空树;空(2)处填入"root"表明返回结点的指针;空(3)处填入"find_key(root→left,key)"表明下一步到左子树上继续查找;空(4)处填入"find_key(root→right,key)"表明下一步到右子树上继续查找。
显然，在二叉排序树上进行查找时，若成功，则查找过程是走了一条从根结点到达所找结点的路径。例如，在下图所示的二叉排序树中查找62,则依次与46、54、101和62作了比较。因此，在树中查找一个关键字时，需要比较的结点个数取决于该关键字对应结点在该二叉查找树所在层次(数)或位置。
-
第2题：
试题三（共15分）
阅读以下说明和C函数，填充函数中的空缺，将解答填入答题纸的对应栏内。
【说明】
函数Insert _key (*root,key)的功能是将键值key插入到*root指向根结点的二叉查找树中（二叉查找树为空时*root为空指针）。若给定的二叉查找树中已经包含键值为key的结点，则不进行插入操作并返回0；否则申请新结点、存入key的值并将新结点加入树中，返回l。
提示：
二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树：
●若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值；
●若它的右子树非空，则其右子树上所有结点的键值均大于根结点的键值；
●左、右子树本身就是二叉查找树。
设二叉查找树采用二叉链表存储结构，链表结点类型定义如下：
typedef struct BiTnode{
int key _value; ／*结点的键值，为非负整数*／
struct BiTnode *left,*right; ／*结点的左、右子树指针*／
}BiTnode, *BSTree；
【C函数】
int Insert _key( BSTree *root,int key)
{
BiTnode *father= NULL,*p=*root, *s;
while( (1)＆＆key!=p->key_value){／*查找键值为key的结点*／
father=p；
if（key< p->key_value）p= (2) ； ／*进入左子树*／
else p= (3) ； ／木进入右子树*／
}
if (p) return 0； ／*二叉查找树中已存在键值为key的结点，无需再插入*／
s= (BiTnode *)malloc( (4) )；／*根据结点类型生成新结点*／
if (!s) return -1;
s->key_value= key; s->left= NULL; s->right= NULL;
if( !father)
(5) ； ／*新结点作为二叉查找树的根结点*／
else ／*新结点插入二叉查找树的适当位置*／
if( key< father->key_value)father->left = s;
elsefather->right = s;
retum 1：
}
正确答案：
(1)p
(2)p->left
(3) p->right
(4) sizeof(BiTnode)
(5) *root=s
-
第3题：
二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值。（）
最先插入的结点一定是根结点 -
第4题：
试题三（共 15 分）
阅读以下说明和 C 程序，将应填入 （n） 处的字句写在答题纸的对应栏内。
正确答案：
-
第5题：
二叉排序树或者是一棵空树，或者是具有下列性质的一棵二叉树：（1）若左子数不空，则左子树所有结点的值（）；（2）若右子数不空，则右子树所有结点的值（）； （3）左右子树又分别是（）。
均小于根结点的值；均大于根结点的值；二叉排序树
略