首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知在二叉树中,T为根结点,*p和*q为二叉树中两个结点,试编写求距离它们最近的共同祖先的算法。
已知在二叉树中,T为根结点,*p和*q为二叉树中两个结点,试编写求距离它们最近的共同祖先的算法。
admin
2012-06-26
30
问题
已知在二叉树中,T为根结点,*p和*q为二叉树中两个结点,试编写求距离它们最近的共同祖先的算法。
选项
答案
int.found=FALSE; Bitree*Find_Near_Ancient(Bitree T,Bitree p,Bitree q){ //求二叉树T中结点P和q的最近共同祖先 Bitree pathp[100],pathq[100]; //设立两个辅助数组暂存从根到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->lchild) Findpath(T->lchild,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/AlajFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
到19世纪蒸汽时代资本主义取得了具有决定意义的胜利,意思是说()。
京军三大营的成分不包括()。
明代中后期,随着工商业的发展和南北经济联系的加强,在江南地区,自宋元以来初露端倪的新的城市类型——()得到很快的发展。
第二国际与第一国际特点的比较。
从1939年春天起,国共双方军队在驻防结合部的摩擦冲突不断升级,不是这一时期惨案的是()
俄罗斯的私有化进程始于()年。
近代中国第一个系统介绍西方思想与文化名著的翻译家和启蒙思想家是()。
第三世界所共有的特征及崛起的标志是什么?
北宋在统一南方割据势力的过程中特设(),把征南所得的财富统一存放,以作日后恢复幽燕之费。
著名的网络OSI七层模型是由()组织提出来的。
随机试题
信息系统的开发过程一般包括系统规划、系统分析、系统设计、系统实施和系统_____五个步骤。
心绞痛诊断的最重要依据为
以下哪项试验室发现有助于鉴别缺铁和维生素B12缺乏
“备案号”栏:()。“标记唛码及备注”栏:()。
小偷张某在某购物商店窃得游客王某的钱包后逃逸,王某发现后急追。张某逃跑中撞上欲借用商店厕所的李某,因商店地板湿滑,李某摔成重伤。下列说法错误的是()。
220年,()废汉献帝自立,建立魏国。
东方市人民政府市政发(2014)067号东方市人民政府通报全市市民:今日本市部分地区出现一种人心惶惶的传说,称一种罕见的流感病毒已传入我市并造成几十人死亡。经本市安检部门证实,这是完全没有任何事实根据的,本市从未发生过一起此
太阳系的小行星带分布在()。
结合材料回答问题:材料1若夫美、法民政,英、德宪法,地远俗殊,变久迹绝,臣故请皇上以俄大彼得之心为心法,以日本明治之敢为政法也。然求其时地不远,教俗略同,成效已彰,推移即时,若名书佳画,墨迹尚存,而易于临摹,如宫室衣裳,裁量恰符,而立可
Overthelasttwoyears,inthePCbusinessMichaelDellhasbeenbeatenlikearentedmule.Hiscompanycontinuestolosemarke
最新回复
(
0
)