题目内容
（请给出正确答案）
[主观题]
在二叉搜索树上删除一个有两个子女的结点时，可以采用以下方法：用左子树TL上具有最大关键码的
结点或者用右子树TR上具有最小关键码的结点顶替，再递归地删除适当的结点。可随机选择其中一个方案。试编写程序实现这个删除方法。
查看答案
如果结果不匹配，请 联系老师 获取答案
题目内容
（请给出正确答案）
如果结果不匹配，请 联系老师 获取答案
题目内容
（请给出正确答案）
如果结果不匹配，请 联系老师 获取答案
更多“在二叉搜索树上删除一个有两个子女的结点时，可以采用以下方法：…”相关的问题
（61）
A. 先序
B. 中序
C. 后序
D. 层序
（62）
A. O(n2
B. O(nlog2n)
C. O(log2n)
D. O(n)
(40)
A．从根结点到任何一个叶子结点的路径上，结点的关键码序列呈递增排列
B．从根结点到任何一个叶子结点的路径上，结点的关键码序列呈递减排列
C．同层次结点从左向右排列，结点的关键码序列呈递增排列
D．同层次结点从左向右排列，结点的关键码序列呈递减排列
阅读以下说明、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).
此题为判断题(对，错)。
在一非空二叉树的中序遍历序列中，根结点的右边(40)。
A．只有右子树上的所有结点
B．只有右子树上的部分结点
C．只有左子树上的部分结点
D．只有左子树上的所有结点最左子树
在非空二叉树的中序遍历序列中，二叉树的根结点的左边(43)。
A．只有左子树上的所有结点
B．只有左子树上的部分结点
C．只有右子树上的所有结点
D．只有右子树上的部分结点
此题为判断题(对，错)。
试题三（共15分）
阅读以下说明和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：
}
回指向该结点的指针。要求算法的平均时间复杂度为O(log2n)。二叉搜索树的每个结点中除data、ieftChild、rightChild等数据成员外、增加一个count成员，保存以该结点为根的子树上的结点个数。
