在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(10gn)的算法，确定树中第k个结点的位置。

admin2013-09-16 21

问题在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(10gn)的算法，确定树中第k个结点的位置。

选项

答案二叉排序树中第k个结点，即为二叉排序树中序序列中顺序号为k的结点，根结点的Lsize域中存放的是根结点的顺序号。要确定二叉排序树中第k个结点，先需将k与根结点的顺序号进行比较，若相等，则找到；若k小于根结点的顺序号，k继续与根的左孩子结点的顺序号比较，依次类推。(注意，右孩子结点的顺序号等于根结点的顺序号与右孩子结点的Lsize域值之和。)由于查找过程中不超过树的高度，故其算法复杂度为O(10gn)。 typedef struct Node{ int key： struct Node*l

解析

转载请注明原文地址:https://kaotiyun.com/show/4gxi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(10gn)的算法，确定树中第k个结点的位置。

计算机408

学硕统考专业

中共十四届六中全会《关于加强社会主义精神文明建设若干重要问题的决议》，强调要()。

第一次世界大战后。《凡尔赛条约》规定了国际联盟管理15年的德国地区是（）。

简述近代香港问题的形成。

蒙古军西征之后，罗斯处于()的控制之下。

波兰三次被瓜分的时间是()

毛泽东从事了大量理论研究工作，系统阐述了新民主主义的理论，下列选项中，不属于这一范围的是()

1901年6月，发表《立宪法议》，首先提出君主立宪要求的是()。

最晚到汉武帝时期，出现了我国第一部算学著作()，它记载了用竿标测日影以求日高的方法，从而认识了勾股定理。

下列现象均属于明朝手工业进步的表现的是()①嘉万年间民营手工业渐居主要地位②匠役制度瓦解③出现了雇佣劳动、组织手工工场的经营方式④加强了对工匠的剥削，工匠的人身依附关系加强

被《文心雕龙》评为“七子之冠冕”的是()。

某患者男性，发作性软瘫2个月，休息后可缓解。昨日晚餐饮酒，今晨再次发作，伴乏力来诊。查体：BP140／70mmHg，神清语利，双肺无异常，心率98次／min，双下肢肌力3级。进一步检测尿钾，若为失钾性肾病表现为

患者，女，33岁，已婚。经血非时而下，淋沥不净，色紫暗、有块。小腹胀痛，舌紫苔薄白，脉涩。治疗应首选()

破产企业中的下列哪些财产属于破产财产?()

在中国境外投资的建设项目财务基准收益率的测定，首先考虑(　　)因素。

核心流动资产是始终存在于资产负债表上的那一部分流动资产，其主要来源是()。

加强事业单位机构编制宏观管理，要()。

下列选项中，劳动人事争议仲裁委员会组成人员中不包括()。

在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(10gn)的算法，确定树中第k个结点的位置。

计算机408

学硕统考专业

中共十四届六中全会《关于加强社会主义精神文明建设若干重要问题的决议》，强调要()。

第一次世界大战后。《凡尔赛条约》规定了国际联盟管理15年的德国地区是（）。

简述近代香港问题的形成。

蒙古军西征之后，罗斯处于()的控制之下。

波兰三次被瓜分的时间是()

毛泽东从事了大量理论研究工作，系统阐述了新民主主义的理论，下列选项中，不属于这一范围的是()

1901年6月，发表《立宪法议》，首先提出君主立宪要求的是()。

最晚到汉武帝时期，出现了我国第一部算学著作()，它记载了用竿标测日影以求日高的方法，从而认识了勾股定理。

下列现象均属于明朝手工业进步的表现的是()①嘉万年间民营手工业渐居主要地位②匠役制度瓦解③出现了雇佣劳动、组织手工工场的经营方式④加强了对工匠的剥削，工匠的人身依附关系加强

被《文心雕龙》评为“七子之冠冕”的是()。

某患者男性，发作性软瘫2个月，休息后可缓解。昨日晚餐饮酒，今晨再次发作，伴乏力来诊。查体：BP140／70mmHg，神清语利，双肺无异常，心率98次／min，双下肢肌力3级。进一步检测尿钾，若为失钾性肾病表现为

患者，女，33岁，已婚。经血非时而下，淋沥不净，色紫暗、有块。小腹胀痛，舌紫苔薄白，脉涩。治疗应首选()

破产企业中的下列哪些财产属于破产财产?()

在中国境外投资的建设项目财务基准收益率的测定，首先考虑( )因素。

核心流动资产是始终存在于资产负债表上的那一部分流动资产，其主要来源是()。

加强事业单位机构编制宏观管理，要()。

下列选项中，劳动人事争议仲裁委员会组成人员中不包括()。

在中国境外投资的建设项目财务基准收益率的测定，首先考虑(　　)因素。