首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(log n)的算法,确定树中第k个结点的位置。
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(log n)的算法,确定树中第k个结点的位置。
admin
2012-06-21
107
问题
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(log n)的算法,确定树中第k个结点的位置。
选项
答案
二叉排序树中第k个结点,即为二叉排序树中序序列中顺序号为k的结点,根结点的Lsize域中存放的是根结点的顺序号。要确定二叉排序树中第k个结点,先需将k与根结点的顺序号进行比较,若相等,则找到;若k小于根结点的顺序号,k继续与根的左孩子结点的顺序号比较,依次类推。(注意,右孩子结点的顺序号等于根结点的顺序号与右孩子结点的Lsize域值之和。)由于查找过程中不超过树的高度,故其算法复杂度为O(log n)。 typedef struct Node{ int key; struct Node*lchild, *rchild; int Lsize }BSNode; BSNode* Locate(BSNode*T,int k) { int j,i=0; BSNode*p=T; while(p) { j=i+p->Lsize; if(j==k)return p;//找到 if(j>k)p=p->lchild; else{ i+=p->Lsize; p=p->rchild; } } return NULL; }
解析
转载请注明原文地址:https://kaotiyun.com/show/bNxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
1933年美国通过的《工业复兴法》规定:“雇主不得工人参加何种工会为雇佣条件;必须遵守工时……工资限额。”这一法令说明()
揭批“四人帮”运动,在全国范围内开展了()。
《国策基准》
下列关于第三次科技革命的说法,不正确的是()。
从“鲁尔危机”的发生到《道威斯计划》的实施,西方国际关系变化对当时有关国家的影响是()。①美国势力进一步向欧洲渗透②英国达到了限制法国、保持均势的目的③德国获得重建经济的有利时机④法国扩充实力争霸欧洲的计划遭重创
论述斯巴达的阶级结构、政治制度和社会风尚
简述苏联和南斯拉夫之间的冲突。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[0]=true;While(flag[1]);
某中央处理器的数据通路如图所示。MDR为内存数据寄存器,PC为程序计数器,IR为指令寄存器。所有的单线箭头为控制微命令。(1)请说明图中部件X的名称和功能、寄存器Y的名称和功能。(2)请解释:为什么要设置T暂存器?(3)假定指令格式为RS型指令,其中“sU
随机试题
Theoverseasfoundthecityhas______greatchangessincetheyvisitedlastyear.
A、微球B、pH敏感脂质体C、磷脂和胆固醇D、毫微粒E、单室脂质体()为提高脂质体的靶向性而加以修饰的脂质体。
重建成本是指采用当前的建筑材料、建筑技术和工艺水平等,重新建造与原有建筑物功能效用相等的新建筑物所需支付的成本。
已知反应A+2B→2C的速率方程为r=kc(A)c(B),则该反应是()。
依据《中华人民共和国水污染防治法》,()根据本行政区域重点水污染物排放总量控制指标的要求,将重点水污染物排放总量控制指标分解落实到排污单位。
WhenItoldmyfamilythatIwasthinkingoftakingacookingjob,theroarsoflaughterwereratherdiscouraging.Noonebeliev
一个女孩毫无道理地被老板炒了鱿鱼。中午,她坐在单位喷泉旁边的一条长椅上黯然伤神,她感到她的生活失去了颜色,变得黯淡无光。这时她发现不远处一个小男孩站在她的身后咯咯地笑,她好奇地问小男孩,你笑什么?“这条长椅的椅背是早晨刚刚漆过的,我想看看你站起来时背是
蒙台梭利创办的幼教机构的名称是()。
下面关于S3C2410中断控制器的叙述中,错误的是()。
下列属于通知或警告用户的命令是
最新回复
(
0
)