首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知在二叉树中,T为根结点,*p和*q为二叉树中两个结点,试编写求距离它们最近的共同祖先的算法。
已知在二叉树中,T为根结点,*p和*q为二叉树中两个结点,试编写求距离它们最近的共同祖先的算法。
admin
2013-07-12
27
问题
已知在二叉树中,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
学硕统考专业
相关试题推荐
利玛窦与李之藻合译的()一书,介绍了西方数学中的算术知识,尤为可贵的是,其传入了中国所没有的西洋笔算法。
唐代制瓷有“南青北白”之说,其所代表的产地分别是()。
在下列文章、文件中,为“文化大革命”的发动作了舆论准备的有()①《横扫一切牛鬼蛇神》②《评新编历史剧》③《五一六通知》④部队文艺座谈会《纪要》
简述布匿战争的过程。
下列会议中,讨论有关对日本法西斯问题的有()。①开罗会议②德黑兰会议③雅尔塔会议④波茨坦会议
在中国共产党的“西部大开发”战略中,提出要依托亚欧大陆桥、长江水道、西南出海通道等交通干线,逐步形成一些有特色的跨行政区域的经济带,以下不属于其中的是()
连续五期用全部或大部分的篇幅报道和评论了五四运动这一伟大运动的杂志是()。
下列有关俄国农奴制改革的表达,不正确的是()。
从“鲁尔危机”的发生到《道威斯计划》的实施,西方国际关系变化对当时有关国家的影响是()。①美国势力进一步向欧洲渗透②英国达到了限制法国、保持均势的目的③德国获得重建经济的有利时机④法国扩充实力争霸欧洲的计划遭重创
格拉古兄弟改革的内容和结果是什么?
随机试题
A、Travelwithherboyfriend.B、Stopusingthecreditcards.C、Stopshoppingwithherboyfriend.D、Buylessclothes.B对话最后,男士建议女士
NewspaperAnewspaperisaprintedperiodicalwhosepurposeistodelivernewsandotherinformationinanup-to-date,factua
马戏团n.c_____
下列哪项不是诱发慢性肾炎肾功能恶化的因素
票据更改的构成要件有哪些?
简述体育与健康课程教学中场地器材布置几点要求。
学习策略的核心是()
根据《中华人民共和国人民警察使用警械和武器条例》的规定,不属于人民警察使用警械和武器的基本原则的是:
某公司发行在外的普通股股票为50万股,市场价值为800万元,债务的市场价值为200万元。到目前为止,公司没有发放过任何现金股利,目前公司考虑两种政策:(1)继续原来的政策,不发放任何现金股利;(2)根据市场价格出售价值300万元的新股并立即将这300万
“思想从来也不能超出旧世界秩序的范围:在任何情况下它只能超出旧世界秩序的思想范围。思想根本不能实现什么东西。为了实现思想,就要有使用实践力量的人。”这段话说明
最新回复
(
0
)