首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(log n)的算法,确定树中第k个结点的位置。
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(log n)的算法,确定树中第k个结点的位置。
admin
2012-06-21
68
问题
在平衡二叉树中的每个结点上增设一个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
学硕统考专业
相关试题推荐
玄奘和义静曾经到达求法的大乘佛教中心是()。
列宁在()中阐明了用暴力打碎旧的国家机器、建立无产阶级专政的必要性。
1945年2月的雅尔塔会议决定以()方式处理战败的德国。
1516年,法国国王同教皇签订了协约,规定法王有权任命本国教会的高级神职,有权向教士征税,该协约是()。
下列关于《大明律》的叙述,不正确的是()
中世纪西欧行会经济政策的最大特征是()。
下面条约没有涉及德国的赔款问题的是()。
最早测量子午线的长度,并主持修订了当时最先进历法《大衍历》的是僧人()。
对巴黎公社的评述,正确的有()。①是无产阶级建立政权的第一次伟大尝试②主要的经验是废除旧的国家机器,建立新的国家机器③其实践和经验,丰富了马克思主义理论④由于无产阶级的不成熟,其失败是不可避免的
1628年出版了《心血运动论》一书,论证了血液在全身的循环运动,使生理学发展为科学的是()。
随机试题
患者,女性,39岁。入院前半个月发热、咽痛,热退5天后感乏力、恶心、呕吐、少尿。查体:血压168/100mmHg,贫血貌,双下肢水肿,呼吸深长,心脏临界大小。实验室检查:血红蛋白60g/L,尿蛋白(++),血尿素氮41mmol/L,肌酐1002μmol/L
项目监理机构可设置总监理工程师代表的情形包括()。
按照现代质量管理理念,建设工程项目功能性质量必须以()为焦点。
下列各项中,属于应承担违反支付结算法律制度的行政责任的行为有()。
案例:李老师在进行Flash综合复习课教学时,以“制作北京风景名胜电子相册”为学习总任务,将学生4人分为一组进行小组合作,任务完成后将小组作品上传到教学平台上,由其他小组评价、赏析,然后进行投票,知图16、图17所示。最后,李老师分别远取票数最高的、最低
事物发展的源泉和动力是矛盾双方的互相排斥、互相否定。()
关于马铃薯,下列说法正确的是()。
ShehasaverygoodcommandofbothGermanandFrench,andisnowlearning______foreignlanguage.
A、Heatethehoney.B、Hedrankthebeer.C、Hechasedthepeopleaway.D、Heturnedthingsupsidedown.D
Theparentsstaredattheirchildangrily,______(等着他来解释事情的原委).
最新回复
(
0
)