首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(log n)的算法,确定树中第k个结点的位置。
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(log n)的算法,确定树中第k个结点的位置。
admin
2012-06-21
132
问题
在平衡二叉树中的每个结点上增设一个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年,中共在根据地建设中,为争取抗战胜利奠定物质基础的措施是()。
关于《新学伪经考》、《孔子改制考》的说法正确的是()。①都是利用古书古人宣传西方资产阶级政治的学说,向西方寻求救国真理②借用儒家学说和孔子的偶像进行宣传,可减少来自封建顽固势力的阻挠和压力③是维新变法的重要理论依据④动摇了封建统治的思想基
关于德意志宗教改革的说法不正确的是()
一个由高速缓冲存储器Cache与主存储器组成的二级存储系统。已知主存容量为1MB,按字节编址,缓存容量为32KB,采用组相联方式进行地址映射与变换,主存与缓存的每一块为64B,缓存共分8组。(1)写出主存与缓存的地址格式(标明各字段名称与位数)
相对于微程序控制器,硬布线控制器的特点是()。
采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突,在数列地址空间[0..12]中对关键字序列22,41,53,46,30,13,1,67,51;(1)构造散列表(画示意图);(2)装填因子;(3)等概
数据链路层采用选择重传协议(SR)传输数据,发送方已发送了0~3号数据帧,现已收到1号帧的确认,而0、2号帧依次超时,则此时需要重传的帧数是____。
随机试题
以下对破产管理人的权利和义务表述不正确的是()
氧离曲线
关于矫正型大动脉转位的叙述,不正确的是
A.紫杉醇B.顺铂C.氟尿嘧啶D.柔红霉素E.羟喜树碱属于破坏DNA的铂类化合物的是()。
图5-52所示等腰直角三角形单元体,已知两直角边表示的截面上只有切应力,且等于τ0,则底边表示的截面上的正应力σ和切应力τ分别为()。
由于人机系统中的可靠性的因素众多且随机变化,因此人的可靠性是不稳定的,则人机系统可靠度采用()来提高。
Somecompaniesaremorecreativeintheiruseofhistorythanothers.HSBC’sHistoryWall,astrikingartinstallationatthebank
建设社会主义文化强国,必须加快文化体制改革,推动社会主义文化大发展大繁荣。对此,我们必须坚持放在首位的是
有以下程序:#include<iostream>#include<string>usxngnamespacestd;intmain(){charp[]="abcdefgh";
WriteonANSWERSHEETTWOanoteofabout50460wordsbasedonthefollowingsituation:Youforgottoreturnthebooklastwe
最新回复
(
0
)