首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知在二叉树中,T为根结点,*p和*q为二叉树中两个结点,试编写求距离它们最近的共同祖先的算法。
已知在二叉树中,T为根结点,*p和*q为二叉树中两个结点,试编写求距离它们最近的共同祖先的算法。
admin
2013-07-12
32
问题
已知在二叉树中,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://jikaoti.com/ti/nwajFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
郡县制度在春秋战国时代是政治变革中最显著的一个方面,下列选项中,对郡县制度表述错误的是()
林则徐的反英国侵略的策略思想不包括()。
对三国鼎立到隋朝重新统一全国这段历史时期的政局,叙述正确的是()。①只有西晋有过短暂的统一②大多数时间是多个政权分立、南北对峙的复杂政局③西晋、北魏、东晋都有过短暂的统一④除三国分立以外,其他时间基本上处于统
外国侵略者通过不平等条约取得的特权中,按时间先后顺序排列应是()。①外国商船和军舰可以在长江各口岸自由航行②外国人可以在通商口岸开设工厂③可在通商口岸建立教堂④领事裁判权和片面最惠国待遇
我国第一部系统的史学理论著作是()。
花剌子密不是()。
《道威斯计划》的实施所产生的直接结果是()。
唐顺宗时,以王叔文、王侄为首的朝臣与宦官之间发生的冲突,称为()。
给定单链表的结点结构typedefstructnode*link;structnode{intitem,linknext;);将两个升序单链表归并为一个升序单链表。
随机试题
车辆在冰雪路面紧急制动时,易产生侧滑,应降低车速,利用发动机制动进行减速。()
发动机液压挺柱具有哪些优点?
社会主义民主政治的本质和核心是()
腹股沟区的解剖中,联合肌腱的构成包括
A输血B脾切除C雄激素治疗D糖皮质激素治疗E免疫抑制剂治疗特发性血小板减少性紫癜患者治疗首选
“白如玉、明如镜、薄如纸、声如罄”所形容的是()瓷器。
教师的能力素质主要包括:______,语言表达能力,组织管理能力,自我调控能力。
中国社会中的个体首先是天然地生活在一个他自己不能选择的网络中。他的喜怒哀乐、他的成功与失败总是嵌入在他的社会网络中而难以独享。这就是说,他在没有打算拥有社会网络的时候,别人在道义上就是他的潜在资源,而无论他愿意与否,他本身也是别人的可利用者。这段
(2015年单选7)2011年,以缅甸人糯康为首的武装犯罪集团在湄公河流域劫持我国商船并杀害了13名中国船员。中国政府与泰国、缅甸和老挝三国联合采取抓捕行动,在境外将糯康等人抓捕归案。2013年,糯康等人被我国最高人民法院依法核准执行死刑。该案体现的法对人
ThenovelTheAdventuresofHuckleberryFinnwaswrittenby
最新回复
(
0
)