首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(10gn)的算法，确定树中第k个结点的位置。
在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(10gn)的算法，确定树中第k个结点的位置。
admin
2013-09-16
67
问题
在平衡二叉树中的每个结点上增设一个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题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
中华人民共和国恢复了在联合国合法席位的时间是()。
论述1840—1979年中国与英美的关系发展。(首都师范大学2015年历史学基础综合真题)
简述战后西欧经济的变化过程。
我国第一部系统的史学理论著作是()。
表明第一次国共合作全面破裂的事件是()。
西汉初年，反驳刘邦“马上治天下”的说法，并向汉帝国治国献策的是()。
明治维新时期的土地改革，说法不正确的是()。
德国发动二战以后，未进攻苏联先进攻英法的主要依据是()
三个进程P1、P2、P3互斥使用一个包含N(N＞O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用getev
假定某采用页式虚拟存储管理的计算机系统中，主存储器容量为1GB，被分为262144块物理块，物理块号为0，1，2，……，262143。某进程的地址空间占4页，逻辑页号为0，1，2，3，被分配到主存储器的第20，45，101，58号物理块中。回答：
随机试题
She______hisangerthoughhedidnotsayawordtoher.
生物膜的化学组成是什么?
隧道工程水害的防治措施不包括()。
2011年7月1日，人民法院裁定受理债权人甲公司的破产申请，并指定乙律师事务所担任管理人。在10月10日召开的第一次债权人会议上，管理人将甲公司的有关情况汇报如下：(1)全部财产的变现价值为2000万元。其中包括：①已作为丁银行贷款等值担保物财产价值为2
盖老师总是建议学生们在看课本和课外读物时，用不同颜色的笔画出重点并相应作出标记，以便于日后重新阅读，是利用知觉的()特征。
对二人以上共同实施违反治安管理行为的责任，《治安管理处罚法》规定()。
设α1,α2,α3,…,αn为n个n维线性无关的向量，A是n阶矩阵，证明：Aα1,Aα2,Aα3,…,Aαn线性无关的充分必要条件是A可逆。
相联存储器的访问方式是(59)。
在VisualFoxPro中，有如下内存变量赋值语句：X＝{^2001－07－2810：15：20PM}Y＝.F.M＝$123.45N＝123.45Z＝"123.24"执行上述赋值语句之后，内存变量X、Y、M、N和Z的
Pollutionhasbecomeaseriousprobleminalmostallthebigcitiesoftheworld.Citypeoplearebecomingmoreandmoreworried
最新回复
(
0
)
