首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(log n)的算法,确定树中第k个结点的位置。
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(log n)的算法,确定树中第k个结点的位置。
admin
2012-06-21
105
问题
在平衡二叉树中的每个结点上增设一个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
学硕统考专业
相关试题推荐
19世纪末的中国成为列强争夺的焦点,列强掀起了瓜分中国的狂潮。其中法国把()变成了自己的势力范围
西班牙内战演变为反法西斯的民族革命战争,主要是由于()。
汉武帝时期设立的司隶校尉所掌纠的范围不包括()。
李大钊是在中国传播马克思主义最早的革命先驱者,下列李大钊的著作中,不属于揭开了我国马克思主义宣传的第一页的是()。
在《资政新篇》中,洪仁轩提出的政治主张实际是要()。
蒙古军西征之后,罗斯处于()的控制之下。
第三次科技革命初期,苏联领先于美国的新兴科学技术成就是()。
在新民主主义革命中,工人阶级、农民阶级和城市小资产阶级的政治代表是()。
在阿拉伯()统治时期,阿拉伯军队曾与当时中国的唐朝军队发生冲突。
序列的“中值记录”指的是:如果将此序列排序后,它是第n/2个记录。试写出一个求中值记录的算法。
随机试题
关于见证取样和送检次数的说法,正确的有()。
试述幽门螺杆菌(HeIicobactorPyIori,Hp)对胃十二指肠粘膜的致病作用。
下列哪一项病理变化与脾胃虚弱有关
深昏迷患者不能将痰液咳出的主要原因是
股东享有的权利包括()。Ⅰ.收益分配权Ⅱ.知情权Ⅲ.监督权Ⅳ.表决权
某公司从银行获得贷款2亿元,期限3年,贷款年利率为6.5%,约定每年付息一次,到期一次性还本。假设筹资费用率为0.5%,公司所得税率为25%,则该公司该笔贷款的资本成本率是()。
有网友发帖称,8月28从湖北襄樊到陕西安康的某次列车,其有效座位为978个.实际售票数却高达3633张。铁道部要求,普快列车超员率不得超过50%,这次列车却超过了370%.属于严重超员。如果以下陈述为真,哪一项对该网友的论断构成严重质疑?
贫困的要素不仅包括物质和收入水平指标,还包括能力指标,即人类基本能力和权利的剥夺。权利贫困就是缺乏政治、经济、文化和社会基本人权的一种贫困状态。权利贫困是贫困的核心,物质贫困是贫困的具体表现,权利贫困是造成物质贫困的根本原因。下列选项不属于权利贫困的是:
Salt,shellsormetalsarestillusedasmoneyinout-the-waypartsoftheworldtoday.Saltmayseemratherastrange【B1】_
一个完整的程序必须完成3个层次的过程,它们分别是编码、测试和______。
最新回复
(
0
)