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

admin2013-09-16 54

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

学硕统考专业

结合史实，分析华北事变前后国民党对日本政策的变化及其主要原因。(华东师范大学2004年中国通史真题)

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

简评“雅尔塔会议”。(东北师范大学2001年世界史综合卷真题)

下列关于第三次科技革命的说法，不正确的是()。

试析凡尔赛一华盛顿体系的实质及其对一战后国际关系的影响。

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

1988年起，苏联民族矛盾激化，民族分离运动加剧，第二次较大规模的民族冲突是()。

下列事件：①上党战役②九三学社成立③“一二·一”惨案④《双十协定》签订，按照时间顺序排列正确的是()。

阅读下面史料，回答问题：材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下：合众国525000吨；英帝国525000吨；法国175000吨；意大利175000吨；日本315000吨。

(1)所有事件的最早发生时间如下：Ve(1)=0Ve(2)==5Ve(3)=6Ve(4)=max{ve(2)+3，ve(3)+6}=12Ve(5)=max{ve(3)+3，ve(4)+3}=15Ve(6)=ve(4)+4=16Ve(7)=ve

我国《专利法》将“发明”定义为()

代表沈从文艺术创作高峰的一部中篇小说是()

中共中央提出，“十二五”时期构建便捷、安全、高效的综合运输体系的原则是（）。

保险监督管理部门对各保险公司和各保险中介人必须采用同样的标准，这体现了保险监督管理原则中的(　　)原则。

秦朝是我国第一个多民族的中央集权制国家，于公元前221年统一六国，定都咸阳。()

()主管全国教育工作，统筹规划、协调管理全国的教育事业。

Althoughhispeopledidnot______hisefforts,hekepttrying.

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

计算机408

学硕统考专业

结合史实，分析华北事变前后国民党对日本政策的变化及其主要原因。(华东师范大学2004年中国通史真题)

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

简评“雅尔塔会议”。(东北师范大学2001年世界史综合卷真题)

下列关于第三次科技革命的说法，不正确的是()。

试析凡尔赛一华盛顿体系的实质及其对一战后国际关系的影响。

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

1988年起，苏联民族矛盾激化，民族分离运动加剧，第二次较大规模的民族冲突是()。

下列事件：①上党战役②九三学社成立③“一二·一”惨案④《双十协定》签订，按照时间顺序排列正确的是()。

阅读下面史料，回答问题：材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下：合众国525000吨；英帝国525000吨；法国175000吨；意大利175000吨；日本315000吨。

(1)所有事件的最早发生时间如下：Ve(1)=0Ve(2)==5Ve(3)=6Ve(4)=max{ve(2)+3，ve(3)+6}=12Ve(5)=max{ve(3)+3，ve(4)+3}=15Ve(6)=ve(4)+4=16Ve(7)=ve

我国《专利法》将“发明”定义为()

代表沈从文艺术创作高峰的一部中篇小说是()

中共中央提出，“十二五”时期构建便捷、安全、高效的综合运输体系的原则是（）。

保险监督管理部门对各保险公司和各保险中介人必须采用同样的标准，这体现了保险监督管理原则中的( )原则。

秦朝是我国第一个多民族的中央集权制国家，于公元前221年统一六国，定都咸阳。()

()主管全国教育工作，统筹规划、协调管理全国的教育事业。

Althoughhispeopledidnot______hisefforts,hekepttrying.

保险监督管理部门对各保险公司和各保险中介人必须采用同样的标准，这体现了保险监督管理原则中的(　　)原则。