参考答案:
(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作了比较。因此,在树中查找一个关键字时,需要比较的结点个数取决于该关键字对应结点在该二叉查找树所在层次(数)或位置。