问题
问答题
阅读以下说明、C函数和问题,将解答填入答题纸的对应栏内。
【说明】二叉查找树又称为二叉排序树,它或者是一棵空树,或者是具有如下性质的二叉树:?若它的左子树非空,则其左子树上所有结点的键值均小于根结点的键值;?若它的右子树非空,则其右子树上所有结点的键值均大于根结点的键值;?左、右子树本身就是二叉查找树。设二叉查找树采用二叉链表存储结构,链表结点类型定义如下:
函数find_key(root,key)的功能是用递归方式在给定的二叉查找树(root指向根结点)中查找键值为key的结点并返回结点的指针;若找不到,则返回空指针。【C函数】
若某二叉查找树中有n个结点,则查找一个给定关键字时,需要比较的结点个数取决于__(5)__。
答案
参考答案:
(5)该关键字对应结点在该二叉查找树所在层次(数)或位置,或者该二叉树中从根结点到该关键字对应结点的路径长度