二叉排序树上左子树上所有结点的值均小于它的根结点的值。()
二叉排序树上左子树上所有结点的值均小于它的根结点的值。()
二叉排序树上左子树上所有结点的值均小于它的根结点的值。()
A.在二叉排序树上的查找过程与折半查找过程类似
B.二叉排序树中左子树上所有结点的关键字值均小于它的根结点
C.二叉排序树中右子树上所有结点的关键字值均大于它的根结点
D.对某棵二叉排序树进行中序遍历,一定能得到按关键字升序排列的有序序列
E.二叉排序树一定为一棵平衡二叉树
对于二叉查找树(Binary Search Tree),若其左子树非空,则左子树上所有结点的值均小于根结点的值;若其右子树非空,则右子树上所有结点的值均大于根结点的值;左、右子树本身就是两棵二叉查找树。因此,对任意一棵二叉查找树进行(63)遍历可以得到一个结点元素的递增序列。在具有n个结点的二叉查找树上进行查找运算,最坏情况下的算法复杂度为(64)。
A.先序
B.后序
C.层序
D.中序
对于二叉查找树(Binary Search Tree),若其左子树非空,则左子树上所有结点的值均小于根结点的值;若其右子树非空,则右子树上所有结点的值均大于根结点的值。左、右子树本身就是两棵二叉查找树。因此,对任意一棵二叉查找树进行(61)遍历可以得到一个结点元素的递增序列。在具有n个结点的二叉查找树上进行查找运算,最坏情况下的算法复杂度为(62)。
A.先序
B.中序
C.后序
D.层序
(61)
A. 先序
B. 中序
C. 后序
D. 层序
(62)
A. O(n2
B. O(nlog2n)
C. O(log2n)
D. O(n)
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).
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:
}
为了保护您的账号安全,请在“简答题”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!