首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(10gn)的算法,确定树中第k个结点的位置。
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(10gn)的算法,确定树中第k个结点的位置。
admin
2013-09-16
24
问题
在平衡二叉树中的每个结点上增设一个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题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
氏族公社形成的条件和基本标志是()。
下列不属于19世纪三四十年代欧洲三大工人运动事件的是()。
略论中国近现代历史上的“军阀”问题。(北京大学2003年中国通史真题)
论述英国都铎王朝加强专制统治的过程及措施
二战期间,下列四次战役的时间先后顺序是()①莫斯科战役②诺曼底登陆③不列颠之战④阿拉曼战役
“二战”爆发的原因是多种因素综合作用的结果,其中最根本的因素是()。
格拉古兄弟改革的内容和结果是什么?
1905年至1907年间,围绕中国究竟是采用革命手段还是改良方式这个问题,革命派与改良派进行论战的舆论阵地是()。
以下()协议完成了从网卡到IP地址的映射。
设将n(n>1)个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0
随机试题
下列句子中,没有语病的一项是()。
与精神分析理论关于心理、行为障碍的论述有关与行为主义理论关于心理、行为障碍的论述有关
砌体结构建筑依照墙体与上部水平承重构件的传力关系,会产生不同的承重方案,主要有()
在公路行业称为公路工程投资总额,由()等两大部分组成。
设置防水混凝土变形缝需要考虑的因素中不包括:(2013年第89题)
单位负责人应支持并督促会计人员遵守会计职业道德,依法开展会计工作。()
某企业集团中,母公司对子公司的控股比例为80%,母公司年初未分配利润为20万元,子公司年初未分配利润为10万元,子公司年末盈余公积为5万元,当期新提盈余公积为1万元,母公司年初内部应收账款为3万元,坏账提取比例为3‰,则合并会计报表中的年初未分配利润为(
下列哪些属于法律禁止的证券交易行为?()
下列事件按时间先后顺序排列正确的是:①中国女排获得里约奥运会女排比赛冠军②中国(上海)自由贸易实验区正式设立③第九届金砖国家领导人会晤在厦门举行④我国举行纪念中国人民抗日战争暨世界反法西斯战争胜利70周年阅兵式
设二维随机变量(X,Y)的概率密度为f(x,y)=则对x>0,fY|X(y|x)=_________.
最新回复
(
0
)