题目内容
(请给出正确答案)
[主观题]
设二叉搜索树中的关键码互不相同,则其中的最小元素必无左子女,最大元素必无右子女,此命题是否正确?最小元素和最大元素一定是叶结点?一个新元素总是作为叶结点插入二叉搜索树吗?
查看答案
如果结果不匹配,请 联系老师 获取答案
为使二叉搜索树结构支持多个相等数据项的并存,需要增加一个BST::searchAll(e)接口,以查找出与指定目标e相等的所有节点(如果的确存在)。
a)试在BST模板类(教材185页代码7.2)的基础上,扩充接口BST::searchAll(e)。要求该接口的时间复杂度不超过o(k+h),其中h为二叉搜索树的高度,k为命中节点的总数;
b)同时,改进原有的BST::search(e)接口,使之总是返回最早插入的节点e—即先进先出。
设A、B是两个集合,若存在一个从A到B上的一一映射f,则称A与B等势(或有相同的基数),记作AB.证明:区间[0,1]与区间[a,b]等势,其中a、b∈R.
设二叉树根结点的层次为0,一棵高度为h的满二叉树中的结点个数是()
A.2h
B.2h-1
C.2h-1
D.2h+1-1