软考程序员下午试题每日一练（三）

阅读以下说明、C 函数和问题，将解答填入答题纸的对应栏内。

【说明】

二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树：

若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值；

若它的右子树非空，则其右子树上所有结点的键值均大于根结点的键值；

左、右子树本身就是二叉查找树。

设二叉查找树采用二叉链表存储结构，链表结点类型定义如下：

typedef struct BiTnode{

int  key_value; /*结点的键值，为非负整数*/

struct BiTnode *left，*right;  /*结点的左、右子树指针*/

}*BSTree;

函数find_key(root， key)的功能是用递归方式在给定的二叉查找树（root指向根结点）中查找键值为key的结点并返回结点的指针；若找不到，则返回空指针。

【函数】

BSTree find_key(BSTree root， int key)

{

if (   （1）  )

return NULL;

else

if (key == root-> key_value)

return （2）  ;

else if (key < root -> key_value)

return （3）  ;

else

return （4）  ;

}

【问题1】

请将函数find_key中应填入（1）～（4）处的字句写在答题纸的对应栏内。

【问题2】

若某二叉查找树中有n个结点，则查找一个给定关键字时，需要比较的结点个数取决于（5）。

点击注册会员>>>即可获取程序员免费在线真题、观看免费公开课！

真题自测：软考各科目历年真题及答案解析

更多资讯可关注希赛网软考频道，问题咨询请拨打客服电话400-111-9811。