首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(log n)的算法,确定树中第k个结点的位置。
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(log n)的算法,确定树中第k个结点的位置。
admin
2012-06-21
104
问题
在平衡二叉树中的每个结点上增设一个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
学硕统考专业
相关试题推荐
下面属于城市市民的文学作品的是()。
一条鞭法不同于两税法的最具有历史意义的特点是()。
下列选项中,不属于西汉农业发展状况的是()
1941年~1942年,中共在根据地建设中,为争取抗战胜利奠定物质基础的措施是()。
中共十六届五中全会提出,建设社会主义新农村的要求是生产发展和()。
下列内容,与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展,在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张,从经济上瓜分世界
()的设置是清王朝实行满汉联合、以汉制汉统治方式在军事上的具体体现
以北宋三大发明为例简述北宋科学技术的特征。
魏晋南北朝的手工业技术有所进步,下列各项能反映这一特点的是()。①培育出“三熟之稻”②“灌钢”技术的发明③吴培育出八辈之蚕④纸成为最主要的书写材料
下面哪项条约没有涉及德国的赔款问题?()
随机试题
小腿头面部反射区需要用关节强刺激。()
外侧裂周围性失语综合征包括
孕妇在使用非处方药时应注意
中国人民银行为执行货币政策,可以运用下列哪些货币政策工具?()
阅读下面材料,回答问题。与2008年相比,2009年城镇非私营单位在岗职工各行业年平均工资鄙有不同幅度的增长,绝大部分行业增长超过2000元。年平均工资最高的行业是金融业70265元.是全国平均水平的2.1倍;年平均工资最低的行业是农、林、牧、渔业149
A.IwonderwhyyouwanttochangeB.IgiveittoyouforareasonC.comeonitStudent:CanIspeakwithyouforamoment?
分析地理大发现在世界历史上的作用与地位。
在SQL中,SELECT语句的“SELECTDISTINCT”表示查询结果中(19)。
A.railwaystationB.MondayC.busstopD.airportE.rainF.planePeopletravelbyitanditcanflyinthesky.
TheArtofFriendshipA)OneeveningafewyearsagoIfoundmyselfinananxiety.Nothingwasreallywrong—myfamilyandIwere
最新回复
(
0
)