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

admin2013-09-16 91

问题在平衡二叉树中的每个结点上增设一个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

学硕统考专业

提出行星绕太阳运行为椭圆形轨道的天文学家是()。

下列会议中，讨论有关对日本法西斯问题的有()。①开罗会议②德黑兰会议③雅尔塔会议④波茨坦会议

土地革命战争时期，中国社会最基本的政治特征是()。

简要分析在蒸汽时代资本主义的决定性的胜利。

试析东汉豪强地主田庄经济的特点及其历史地位。

系统阐明社会主义初级阶段理论是在()。

《凡尔赛和约》中，战胜国以何种方式处置德国的全部海外殖民地?()。

中共十六届五中全会提出，建设社会主义新农村的要求是生产发展和()。

我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说，如炎帝和黄帝两个部落曾战于()，结果黄帝取得了胜利。

编写判定给定的二叉树是否是二叉排序树的函数。

邓小平在我国改革开放全面展开的历史进程中，反复强调中国实现社会主义现代化发展战略的必要前提，中国的最高利益，中国的问题，压倒一切的是()。

A、青B、赤C、黄D、白E、黑寒证、痛证、瘀血证、惊风证可见上述何种面色

规范性法律文件根据其在法律渊源体系中所处的效力位置和等级的不同，可以分为(　　)。

某网球场2013—2017年利润实现情况如下表所示。请根据上述资料从下列备选答案中选出正确答案。该利润序列的均值为301．5，其变异程度()。

设x≥－1，则(1－｜t｜)dt=___________．

Someabnormalhumanbehaviormaybecausedbyeatingsubstancesthatupsetdelicatechemicalbalancesinthebrain.

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

计算机408

学硕统考专业

提出行星绕太阳运行为椭圆形轨道的天文学家是()。

下列会议中，讨论有关对日本法西斯问题的有()。①开罗会议②德黑兰会议③雅尔塔会议④波茨坦会议

土地革命战争时期，中国社会最基本的政治特征是()。

简要分析在蒸汽时代资本主义的决定性的胜利。

试析东汉豪强地主田庄经济的特点及其历史地位。

系统阐明社会主义初级阶段理论是在()。

《凡尔赛和约》中，战胜国以何种方式处置德国的全部海外殖民地?()。

中共十六届五中全会提出，建设社会主义新农村的要求是生产发展和()。

我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说，如炎帝和黄帝两个部落曾战于()，结果黄帝取得了胜利。

编写判定给定的二叉树是否是二叉排序树的函数。

邓小平在我国改革开放全面展开的历史进程中，反复强调中国实现社会主义现代化发展战略的必要前提，中国的最高利益，中国的问题，压倒一切的是()。

A、青B、赤C、黄D、白E、黑寒证、痛证、瘀血证、惊风证可见上述何种面色

规范性法律文件根据其在法律渊源体系中所处的效力位置和等级的不同，可以分为( )。

某网球场2013—2017年利润实现情况如下表所示。请根据上述资料从下列备选答案中选出正确答案。该利润序列的均值为301．5，其变异程度()。

设x≥－1，则(1－｜t｜)dt=___________．

Someabnormalhumanbehaviormaybecausedbyeatingsubstancesthatupsetdelicatechemicalbalancesinthebrain.

规范性法律文件根据其在法律渊源体系中所处的效力位置和等级的不同，可以分为(　　)。