首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(log n)的算法,确定树中第k个结点的位置。
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(log n)的算法,确定树中第k个结点的位置。
admin
2012-06-21
110
问题
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(log n)的算法,确定树中第k个结点的位置。
选项
答案
二叉排序树中第k个结点,即为二叉排序树中序序列中顺序号为k的结点,根结点的Lsize域中存放的是根结点的顺序号。要确定二叉排序树中第k个结点,先需将k与根结点的顺序号进行比较,若相等,则找到;若k小于根结点的顺序号,k继续与根的左孩子结点的顺序号比较,依次类推。(注意,右孩子结点的顺序号等于根结点的顺序号与右孩子结点的Lsize域值之和。)由于查找过程中不超过树的高度,故其算法复杂度为O(log n)。 typedef struct Node{ int key; struct Node*lchild, *rchild; int Lsize }BSNode; BSNode* Locate(BSNode*T,int k) { int j,i=0; BSNode*p=T; while(p) { j=i+p->Lsize; if(j==k)return p;//找到 if(j>k)p=p->lchild; else{ i+=p->Lsize; p=p->rchild; } } return NULL; }
解析
转载请注明原文地址:https://kaotiyun.com/show/bNxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
论述戊戌变法的影响。
试论述清朝前期是如何巩固统一的多民族国家的?
二战后的半个世纪中,资本主义各国经济史上的五个周期阶段。
我国第一部系统的史学理论著作是()。
中国历史上第一部资产阶级革命法典《临时约法》公布的时间是()。
帝国主义的基本特征是()。
汉灵帝中平元年(184),()在7州28郡同时俱起,这是中国历史上第一次组织、准备比较严密的农民起义。
洋务派创办军事工业的方式是()。
某32位机(机器字长32位)的一台外设通过32位总线与系统内存相连。CPU每秒执行100条指令,平均每条指令需要5个机器周期,其中3个周期必须访问内存,内存读写需一个机器周期,假定CPU在95%的时间内持续执行“背景程序”,且这段时间内不执行I/O指令。现
在一个长度为n(n>1)的带头结点的单链表h上,设有尾指针r(指向尾结点),则执行()操作与链表的长度有关。
随机试题
A.腹会阴联合直肠癌根治术B.经腹腔直肠癌切除术C.经腹腔直肠癌切除、近端造口、远端封闭手术D.乙状结肠造口术直肠癌块下缘距肛门10cm的患者,原则上适用
用硫酸镁缓解子痫惊厥时,给药途径应当是
正常分娩胎膜破裂的时间一般是在
企业采用购买通用会计软件方式配备会计软件时,软件安全保密性强,用户只能执行软件功能,不能访问和修改源程序。()
乙公司是一家上市公司,适用的企业所得税税率为25%,该公司要求的最低报酬率为10%。目前甲公司面临A、B两个投资方案的决策。资料如下:资料一:A、B两个方案有关投资的数据资料如下表所示:假设两个方案原始投资均是在0时点一次性投入,立即投产经营,均采用
关于注册会计师接受委托前的沟通,下列说法中正确的是()。
回忆材料的中间部分识记效果较差,其原因可能有()
下列不属于我国国家主席职权的是()。
HermanMelvillecalledhisfriendNathanielHawthorne______inAmericanLiterature.
A、TheUnitedStates.B、Iran.C、TheUnitedArabEmirates.D、Notmentioned.D推理题。eyshlisteninga结尾处说到,伊朗责怪是美国埋了地雷,可BBC驻该地区的eyshlist
最新回复
(
0
)