试题二（共15分，每空3分）

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

【说明】

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

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

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

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

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

typedef struct BiTnode｛

｝*BSTree；

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

【C函数】

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)！root，或root＝＝0，或root＝＝NULL

(2)root

(3) find_key(root-＞left,key)

(4)find_key(root-＞right,key)

本题考查二叉查找树的基本操作和指针的使用。

对于函数find_key中的填空，根据二叉查找树的性质进行填写：

(1) 首先判断根节点是否为空，即是否到达了树的末端，所以填写root == NULL。

(2) 如果找到了键值为key的节点，则返回该节点的指针，所以填写root。

(3) 如果key小于当前节点的键值，则继续在左子树中查找，因此填写find_key(root->left, key)。

(4) 如果key大于当前节点的键值，则继续在右子树中查找，因此填写find_key(root->right, key)。

这个函数的目的是在二叉查找树中递归地查找键值为key的节点，并返回节点的指针；如果找不到，则返回空指针。