首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(log n)的算法,确定树中第k个结点的位置。
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(log n)的算法,确定树中第k个结点的位置。
admin
2012-06-21
144
问题
在平衡二叉树中的每个结点上增设一个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
学硕统考专业
相关试题推荐
第一个提出人类起源问题的著名学者是()。
武昌起义爆发后,控制大部分地方政权的是()。
“(辽与宋)和好年深;蕃汉人户休养生息,人人安居,不乐战斗”,描述了()之后宋辽关系的图景。
概括指出新民主主义革命各个阶段中国社会的主要矛盾及其表现形式的演变,说明中共根据上述变化对政策的调整及其结果。
苏美尔城邦的特征。
关于德国工业革命,说法不正确的是()。
下面有关兵制的内容,与唐玄宗有关的是()
在请求页式系统中,一程序的页面走向(访问串或引用串)为2,3,4,5,2,3,6,2,3,4,5,6,设分配给该程序的存储块数为m。试分别计算m=3和m=4时,FIFO和LRU两种替换算法的缺页(页故障)数,并给出:结果说明了什么?
某计算机采用微程序控制方式,微指令字长32位,采用字段直接编码的控制方式,共有55个微命令,可分为6个互斥组,分别包含1、3、7、8、12、24个微命令。另外,该机共有5个可判定的外部条件,采用断定方式形成后续微指令地址。(1)设计该机微指令的格式,
有两部计算机M1和M2,指令系统相同。它们的操作频率频率分别是400MHz和200MHz。指令分成A、B和C三类,在M1上执行分别需4、6和8个周期;在M2上执行分别需2、4和3个周期。现有一程序在两机器上执行,其中A、B和C三类指令依次占30%、50
随机试题
A.相须B.相使C.相反D.相畏人参配五灵脂属于药物七情中的
晶体三极管工作在放大状态的条件是发射结加(),集电结加()。
Wecanmakemistakesatanyage.Somemistakeswemakeareaboutmoney.Butmostmistakesareaboutpeople."DidJerryreallycare
建设项目合同的签订应满足的条件是()。
下列不得取得或重新取得会计从业资格证书的有()。
到了青年期,__________和自我提高的内驱力成为学生学习的主要动机。
按照当前我国法律规定,地方各级人民政府每届任期几年?
A、 B、 C、 C本题听力材料很短,考生只要听清了dancing(跳舞)这一关键词即可选出正确答案。
OnSeptember7,2001,a68-year-oldwomaninStrasbourg,France,hadhergallbladder(胆囊)removedbysurgeonsoperating,viacomp
Isitdifficultforyoutogetupinthemorning?Yes?ThenHiroyukiofJapanhasaspecialbedforyou.Hiroyuki’sbedwillget
最新回复
(
0
)