首页 > 职业资格考试
题目内容 (请给出正确答案)
[主观题]

编写一个递归算法,在一棵有n个结点的随机建立起来的二叉搜索树上搜索第k(1≤k≤n)小的元素,并返

编写一个递归算法,在一棵有n个结点的随机建立起来的二叉搜索树上搜索第k(1≤k≤n)小的元素,并返

回指向该结点的指针。要求算法的平均时间复杂度为O(log2n)。二叉搜索树的每个结点中除data、ieftChild、rightChild等数据成员外、增加一个count成员,保存以该结点为根的子树上的结点个数。

查看答案
答案
收藏
如果结果不匹配,请 联系老师 获取答案
您可能会需要:
您的账号:,可能还需要:
您的账号:
发送账号密码至手机
发送
安装优题宝APP,拍照搜题省时又省心!
更多“编写一个递归算法,在一棵有n个结点的随机建立起来的二叉搜索树…”相关的问题
第1题
设一棵二叉树的存储表示是二叉链表,编写一个用逆转链方法实现二叉树前序遍历的算法。这个方法
的思想是在遍历过程中沿着结点的左子女或右子女方向“下降”时,临时改变其leftChild或rightChild的值,使之指向该结点的父结点,从商为以后的“上升”提供路径;在上升的过程中将结点的leftChild或rightChild的值恢复原来的值。为了在上升的过程中区分是从该结点的左子树上升的还是从右子树上升的,在结点中设置一个tag标志。进人算法时,所有结点的tag设为0,当遍历过程中进入结点的左子树时,将该结点的tag置为l、从左子树退出进人右子树时再将该结点的tag置为0.

点击查看答案
第2题
二叉排序树的类型定义如下: typedef struet BSTNode{//二叉排序树的结点结构 int data; //数据

二叉排序树的类型定义如下:

typedef struet BSTNode{//二叉排序树的结点结构

int data; //数据域

struct BSTNode*lchild,*rchild;//左、右孩子指针

}BSTNode,*BSTree;

设计递归算法,统计一棵二叉排序树T中值小于a的结点个数。

点击查看答案
第3题
在二叉搜索树上删除一个有两个子女的结点时,可以采用以下方法:用左子树TL上具有最大关键码的
结点或者用右子树TR上具有最小关键码的结点顶替,再递归地删除适当的结点。可随机选择其中一个方案。试编写程序实现这个删除方法。

点击查看答案
第4题
假设在表示一棵二叉树的二叉链表上增加两个域,双亲域用于指示其双亲结点,标志域flag(可取,0…2)的

假设在表示一棵二叉树的二叉链表上增加两个域,双亲域用于指示其双亲结点,标志域flag(可取,0…2)的值,用以区分在遍历过程中到达该结点时继续向左或向右或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。

点击查看答案
第5题
在一棵高度为h的B树中插入一个新关键码时,为搜索插入位置需读取()个结点。
在一棵高度为h的B树中插入一个新关键码时,为搜索插入位置需读取()个结点。

A、h-1

B、h

C、h+1

D、h+2

点击查看答案
第6题
试编写一个非递归算法,输出广义表中所有原子项及其所在层次。

点击查看答案
第7题
给定一棵二叉树的后序历序列post[low1..highl]和中仔遍历序列in[low2..high2],试以二叉链表为存储表示,编写一个算法构造这棵二叉树.

点击查看答案
第8题
有一棵具有n个结点的满二叉树。请问:该满二叉树的叶子结点数目是多少,并写出分析推理过程。

点击查看答案
第9题
给定一棵二叉树的前序遍历序列prel[lowl..highl]和中序遍历序列in[low2..high2]。试以二叉链表为存储表示,编写一个算法构造这棵二叉树。

点击查看答案
第10题
设二叉树共含n个节点,且各节点数据项的类型支持线性累加(类似于整数或浮点数),试设计并实现一个递归算法,按照如下规则,在o(n)时间内为每个节点设适当的数值:树根为0;对于数值为k的节点,其左孩子数值为2k+1,右孩子为2k+2。

点击查看答案
退出 登录/注册
发送账号至手机
密码将被重置
获取验证码
发送
温馨提示
该问题答案仅针对搜题卡用户开放,请点击购买搜题卡。
马上购买搜题卡
我已购买搜题卡, 登录账号 继续查看答案
重置密码
确认修改