首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(log n)的算法,确定树中第k个结点的位置。
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(log n)的算法,确定树中第k个结点的位置。
admin
2012-06-21
84
问题
在平衡二叉树中的每个结点上增设一个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
学硕统考专业
相关试题推荐
论述华盛顿会议召开的背景及结果
下列各项内容和王羲之的书法成就有关的是()。①开始把字体由隶书转化为楷书②书法代表作有《兰亭序》、《黄庭经》等③他博采众长,世称“书圣”④其子王献之书法造诣也极高,父子合称“二王”
下列哪一项不是我国实行的关于农业生产的有利措施?()
在第二次世界大战后英属印度的各派政治力量中影响最大的是()。
以下选项中中原王朝对西藏管辖设置机构对应有误的一项是()。
简述苏联高度集中的经济政治体制的主要特征。
最早测量子午线的长度,并主持修订了当时最先进历法《大衍历》的是僧人()。
魏晋南北朝的手工业技术有所进步,下列各项能反映这一特点的是()。①培育出“三熟之稻”②“灌钢”技术的发明③吴培育出八辈之蚕④纸成为最主要的书写材料
西欧早期资产阶级反封建斗争以反天主教会的方式进行,主要原因是()①天主教会是最有势力的封建主集团②天主教会是封建的精神工具③天主教会日益腐败④近代自然科学的兴起
某机字长32位,它的存储容量为256MB,按字节编址,则它的寻址范围大小为()。
随机试题
We______togetwhatwewant,anyway.
其辨证为其选方为
胸腔、腹腔、盆腔内脏器官病变引起的腰背痛主要是由哪项所致
二母宁嗽丸为棕褐色的水蜜丸或大蜜丸。药物组成:川贝母225g、知母225g、石膏300g、炒栀子180g、黄芩180g、蜜桑白皮150g、茯苓150g、炒瓜蒌子150g、陈皮150g、麸炒枳实150g、炙甘草30g、五味子(蒸)30g。
Myprevioushomehadastandofwoodsbehinditandmanyanimalsinthebackyard.Thatfirstyear,I【C1】______feedingpeanutsto
给定材料【材料1】《中国互联网发展趋势报告2016》指出,十年间,中国的互联网市场发生巨变。移动应用快速增长。在社交、视频、新闻、工具和购物等领域,移动应用渗透率已超过50%;在团购、旅游和零售业,移动端收入规模已经超越PC端。中国互联
【《推思令》】2007年历史学统考真题;江西师范大学2013年中国通史真题;扬州大学2014年中国史真题;中山大学2014年历史学基础(A)真题;陕西师范大学2017年中国史真题
Ararepieceofgoodnewsfromtheworldofconservation:theglobalextinctioncrisismayhavebeenoverstated.Theworldisun
A、Toget200millionchildrentoschoolby2015.B、Toget57millionchildrentoschoolby2015.C、ToprovideyoungpeopleinAs
A、Atabank.B、Ataninn.C、Ontheriverside.D、Onabasketballfield.C信息明示题,男士说他们用野餐篮带午饭,然后在河边用餐,故选C,考点bank除意为“银行”外,还有“堤,岸”
最新回复
(
0
)