题目内容
（请给出正确答案）
（61）
A. 先序
B. 中序
C. 后序
D. 层序
（62）
A. O(n2
B. O(nlog2n)
C. O(log2n)
D. O(n)
如果结果不匹配，请 联系老师 获取答案
更多“● 对于二叉查找树（Binary Search Tree） …”相关的问题
阅读以下说明、C函数和问题，将解答填入答题纸的对应栏内。
【说明】
二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树：
●若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值;
●若它的右子树非空，则其右子树上所有结点的键值均大于根结点的键值;
●左、右子树本身就是二叉查找树。
设二叉查找树采用二叉链表存储结构，链表结点类型定义如下：
typedefstructBiTnode{
intkey_value;/*结点的键值，为非负整数*/
structBiTnode*left,*right;/*结点的左、右子树指针*/
}*BSTree;
函数find_key(root,key)的功能是用递归方式在给定的二叉查找树(root指向根结点)中查找键值为key的结点并返回结点的指针;若找不到，则返回空指针。
【函数】
BSTreefind_key(BSTreeroot,intkey)
{
if((1))
returnNULL;
else
if(key==root-＞key_value)
return(2);
elseif(keykey_value)
return(3);
else
return(4);
}
【问题1】
请将函数find_key中应填入(1)~(4)处的字句写在答题纸的对应栏内。
【问题2】
若某二叉查找树中有n个结点，则查找一个给定关键字时，需要比较的结点个数取决于(5).
阅读以下说明和C函数，填充函数中的空缺，将解答填入答题纸的对应栏内。
【说明】
函数Insert _key (*root,key)的功能是将键值key插入到*root指向根结点的二叉查找树中（二叉查找树为空时*root为空指针）。若给定的二叉查找树中已经包含键值为key的结点，则不进行插入操作并返回0；否则申请新结点、存入key的值并将新结点加入树中，返回l。
提示：
二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树：
●若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值；
●若它的右子树非空，则其右子树上所有结点的键值均大于根结点的键值；
●左、右子树本身就是二叉查找树。
设二叉查找树采用二叉链表存储结构，链表结点类型定义如下：
typedef struct BiTnode{
int key _value; ／*结点的键值，为非负整数*／
struct BiTnode *left,*right; ／*结点的左、右子树指针*／
}BiTnode, *BSTree；
【C函数】
int Insert _key(BSTree *root,int key)
{
BiTnode *father= NULL,*p=*root, *s;
while((1)＆＆key!=p-＞key_value){／*查找键值为key的结点*／
father=p；
if（key＜ p-＞key_value）p= (2) ； ／*进入左子树*／
else p= (3) ； ／木进入右子树*／
}
if (p) return 0； ／*二叉查找树中已存在键值为key的结点，无需再插入*／
s= (BiTnode *)malloc((4) )；／*根据结点类型生成新结点*／
if (!s) return -1;
s-＞key_value= key; s-＞left= NULL; s-＞right= NULL;
if(!father)
(5) ； ／*新结点作为二叉查找树的根结点*／
else ／*新结点插入二叉查找树的适当位置*／
if(key＜ father-＞key_value)father-＞left = s;
elsefather-＞right = s;
retum 1：
}
A．只有右子树上的所有结点
B．只有右子树上的部分结点
C．只有左子树上的部分结点
D．只有左子树上的所有结点最左子树
A．只有左子树上的所有结点
B．只有左子树上的部分结点
C．只有右子树上的所有结点
D．只有右子树上的部分结点
A．X的双亲
B．X的右子树中最左的结点
C．X的左子树中最右结点
D．X的左子树中最右叶结点
A.对二叉排序树进行先序、中序和后序遍历，都得到结点关键字的有序序列
B.含有N个结点的二叉排序树高度为【log2n】+1
C.从根到任意二个叶子结点的路径上，结点的关键字呈现有序排列的特点
D.从左到右排列同层次的结点，’其关键字呈现有序排列的特点
(40)
A．从根结点到任何一个叶子结点的路径上，结点的关键码序列呈递增排列
B．从根结点到任何一个叶子结点的路径上，结点的关键码序列呈递减排列
C．同层次结点从左向右排列，结点的关键码序列呈递增排列
D．同层次结点从左向右排列，结点的关键码序列呈递减排列
