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

admin2013-09-16 29

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

选项

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

解析

转载请注明原文地址:https://jikaoti.com/ti/R2ajFFFM

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

保加利亚共产党于1990年4月改名为保社会党，它在政府中沦为少数派的时间是()。

简述苏联建立“东方战线”的过程及其影响。

五四运动是中国新民主主义革命的开端，最主要的依据是()。

到1869年为止，人类已发现了多少种化学元素()。

西汉初年，西域共有36国，其中以()人口最多。

()用铜制造了人体模型，并统一了人体的穴位。

世界天文史上最早实地测量子午线的记录是由谁进行的?()

一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。

虚拟存储器技术是基于程序的()特性。

车削细长轴时，产生变形和振动的原因有哪些?可采取哪些解决措施?

论他物权和自物权的联系与区别。

下列哪项属于非感染性发热的疾病

影响消费者行为的因素之一是()。

判别一项成本是否归属责任中心的原则有()。

2011年版《义务教育语文课程标准》与旧版课程标准相比有很大变化。请就其中一点谈谈你的看法。

一个善的行为，必须既有好的动机，又有好的效果。如果是有意伤害他人，或是无意伤害他人，并且这种伤害的可能性是可以预见的，在这两种情况下，对他人造成伤害的行为都是恶的行为。以下哪项叙述符合题干的断定?()

实践是对不可知论“最令人信服的驳斥”。（）

下列有关法系与法律体系含义的表述，哪项是不正确的?()

从一般意义而言,犯罪客观方面的选择要件包括了()。