首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知在二叉树中,T为根结点,*p和*q为二叉树中两个结点,试编写求距离它们最近的共同祖先的算法。
已知在二叉树中,T为根结点,*p和*q为二叉树中两个结点,试编写求距离它们最近的共同祖先的算法。
admin
2013-07-12
30
问题
已知在二叉树中,T为根结点,*p和*q为二叉树中两个结点,试编写求距离它们最近的共同祖先的算法。
选项
答案
int.found=FALSEI Bitree*Find_Near_Ancient(Bitree T,Bitree P,Bitree q){ //求二叉树T中结点P和q的最近共同祖先 Bitree pathp[100],pathq[i00]; //设立两个辅助数组暂存从根到P,q的路径 Findpath(T,P,pathp,0); found=FALSE; Findpath(T,q,pathq,0); //求从根到p,q的路径放在pathp和pathq中 for(i=0;pathp[i]==pathq[i]&&pathp[i];i++);, //查找两条路径上最后一个相同结点 return pathp[--i]; } void Findpath(Bitree T,Bitree P,Bitree path[],int i){ //求从T到P路径的递归算法 if(T==p) { found=TRUE; //找到 return; } path[i]=T; //当前结点存入路径 if(T->ichild) Findpath(T->ichild,P,path,i+1); //在左子树中继续寻找 if(T->rchild&&!found) Findpath(T->rchild,P,path,i+1); //在右子树中继续寻找 if(!found) path[i]=NULL; //回溯
解析
本题也可叙述为求,*p和*q两个结点的最小子树。
遍历访问到*p时,将*p结点的祖先保存到数组pathp中,再遍历访问到*q时,将*q结点的祖先保存到数组pathq中,将数组pathp与数组pathq的结点依次(从0开始)比较,找到最近的共同祖先。
转载请注明原文地址:https://kaotiyun.com/show/Juxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
巴黎和会讨论的中心问题是()。
巴黎和会讨论的中心问题是()。
第一国际开展了哪些活动?其内部经历了哪些主要斗争?
第一国际成立于下面的哪个城市?()
下列叙述正确的是()。
阅读下列材料,回答问题:材料一:我们与希特勒或他们的匪帮永不会谈,永不斡旋,我们将在陆地上、海洋上、天空中与他们作战。直到把笼罩阴云于大地的一切敌人消灭为止……任何为反对纳粹主义而战斗的国家或人民,我们都支援。任何与希特勒为伍的人或国家都是我们的敌人。我
1947年英国通过《蒙巴顿方案》,随后印度和巴基斯坦独立,形成印巴分治局面,在克里米尔地区冲突埋下隐患,《蒙巴顿方案》中印巴分治的依据
分页存储管理中,页表的功能是什么?当系统中的地址空间变得非常大时(如32位地址空间),会给页表的设计带来什么样的新问题?请给出一种解决方法,分析它的优点和缺点。
串行接口是指()。
随机试题
下述子宫输卵管结核最多见的x线表现是
在双管流程中,处理采油树生产管线一侧套管外卡箍刺漏的方法是:()。
杀死芽胞的方法不包括
北达公司(增值税一般纳税人)2010年5月从小规模纳税人处购进一批原材料,取得增值税普通发票,发票上注明价款:117000元,货款通过银行转账支付,其正确的账务处理为()。
增值税暂行条例中规定,不属于应视同销售货物行为征收增值税的是()。
下列属于所有者权益特征的有()。
某具有进出口经营权的外贸公司,2012年5月发生以下经营业务:(1)经有关部门批准从境外进口小轿车30辆,每辆小轿车货价15万元。运抵我国海关前发生的运输费用、保险费分别为9万元、1.38万元,向海关缴纳了相关税款,并取得了海关进口增值税专用缴款
A、B、C、D、E是5个不同的整数,两两相加的和共有8个不同的数值,分别是17、25、28、31、34、39、42、45,则这5个数中能被6整除的有几个?
设有数组定义:intMyIntArray[]={10,20,30,40,50,60,70};则执行下面几个语句后的输出结果是【】。ints=0;for(inti=0;i<MyIntArray.length;i++)s+=My
CalledbymanycriticsthegreatestachievementofEnglishlyricalpoetry,thiselegywaswrittenuponthedeathofafellowalu
最新回复
(
0
)