试题二（共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)；

｝

本题考查二叉查找树的基本性质和操作。

在二叉查找树中进行查找操作时，从根结点开始，若给定的关键字小于当前结点的关键字，则转向左子树进行查找；若大于，则转向右子树进行查找；若相等，则查找成功。这个过程沿着从根结点到目标结点的路径进行，需要比较的结点个数取决于该关键字对应结点在二叉查找树中的位置，或者说取决于从根结点到该关键字的路径长度。因此，答案中提到的“该关键字对应结点在该二叉查找树所在层次（数）或位置，或者该二叉树中从根结点到该关键字对应结点的路径长度”是正确的。