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

admin2013-09-16 89

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

近代中国第一个系统介绍西方思想与文化名著的翻译家和启蒙思想家是()。

根据《国际联盟盟约》的内容分析其实质。

在19世纪“实业救国”运动中，中国并没有因此变得富强，根本原因是()。

试析英法绥靖政策和美国中立政策的原因。(南京大学2013年国际关系史真题)

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

1956年，苏共二十大后，匈牙利大党员和群众强烈要求克服个人崇拜，扩大民主，实行经济改革，一些由知识分子、大学生和干部组成的社团组织纷纷成立，其中最有影响者是()。

毛泽东认为，社会主义这个阶段可分为两个阶段，包括()。

晚清时期清帝年号的正确排序是()

第一国际成立前，各国无产阶级强烈要求加强国际团结的直接原因是()。

詹天佑自主设计修建了中国第一条铁路是在()。

Aswellasbeingusedfortakingphotographs,X-raysarealsousedfortreatingdiseasedpartsofthebodyinordertokillthe

TheAmericanideaofcustomerserviceistomakeeachcustomerthecenterofattention.PeoplegoingshoppinginAmericacanexp

支配眼球外肌的神经是、和。支配舌肌的神经是。

A、在217～220nm处呈最大吸收B、在270nm处有强吸收C、在295～300nm处有特征吸收D、在300～400nm之间有最大吸收E、＞400nm有强吸收UV中乙型强心苷元（）

某国有企业发生了如下几种纠纷，其中哪一项不是《企业劳动争议处理条例》所规定的劳动争议?()

文丘里流量计喉管断面的压强减小，从能量观点来看，主要是(　　)。

某产品的供给弹性系数为1／4，在其他因素不变的情况下，若该产品的价格上升40％，则其供给量将()。

(09年)设an为曲线y=xn与y=xn+1(n=1，2，…)所围成区域的面积，记．求S1与S2的值．

Youarewhatyoueat,orsothesayinggoes.ButRichardWrangham,ofHarvardUniversity,believesthatthisistrueinamorep

ToliveintheUnitedStatestodayistogainanappreciationforDahrendorf’sassertion(主张)thatsocialchangeexistseverywher

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

计算机408

学硕统考专业

近代中国第一个系统介绍西方思想与文化名著的翻译家和启蒙思想家是()。

根据《国际联盟盟约》的内容分析其实质。

在19世纪“实业救国”运动中，中国并没有因此变得富强，根本原因是()。

试析英法绥靖政策和美国中立政策的原因。(南京大学2013年国际关系史真题)

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

1956年，苏共二十大后，匈牙利大党员和群众强烈要求克服个人崇拜，扩大民主，实行经济改革，一些由知识分子、大学生和干部组成的社团组织纷纷成立，其中最有影响者是()。

毛泽东认为，社会主义这个阶段可分为两个阶段，包括()。

晚清时期清帝年号的正确排序是()

第一国际成立前，各国无产阶级强烈要求加强国际团结的直接原因是()。

詹天佑自主设计修建了中国第一条铁路是在()。

Aswellasbeingusedfortakingphotographs,X-raysarealsousedfortreatingdiseasedpartsofthebodyinordertokillthe

TheAmericanideaofcustomerserviceistomakeeachcustomerthecenterofattention.PeoplegoingshoppinginAmericacanexp

支配眼球外肌的神经是______、______和______。支配舌肌的神经是______。

A、在217～220nm处呈最大吸收B、在270nm处有强吸收C、在295～300nm处有特征吸收D、在300～400nm之间有最大吸收E、＞400nm有强吸收UV中乙型强心苷元（）

某国有企业发生了如下几种纠纷，其中哪一项不是《企业劳动争议处理条例》所规定的劳动争议?()

文丘里流量计喉管断面的压强减小，从能量观点来看，主要是( )。

某产品的供给弹性系数为1／4，在其他因素不变的情况下，若该产品的价格上升40％，则其供给量将()。

(09年)设an为曲线y=xn与y=xn+1(n=1，2，…)所围成区域的面积，记．求S1与S2的值．

Youarewhatyoueat,orsothesayinggoes.ButRichardWrangham,ofHarvardUniversity,believesthatthisistrueinamorep

ToliveintheUnitedStatestodayistogainanappreciationforDahrendorf’sassertion(主张)thatsocialchangeexistseverywher

支配眼球外肌的神经是、和。支配舌肌的神经是。

文丘里流量计喉管断面的压强减小，从能量观点来看，主要是(　　)。