首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知在二叉树中,T为根结点,*p和*q为二叉树中两个结点,试编写求距离它们最近的共同祖先的算法。
已知在二叉树中,T为根结点,*p和*q为二叉树中两个结点,试编写求距离它们最近的共同祖先的算法。
admin
2012-06-26
35
问题
已知在二叉树中,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
学硕统考专业
相关试题推荐
我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说,如炎帝和黄帝两个部落曾战于(),结果黄帝取得了胜利。
下列不是空想社会主义产生的历史背景的是()。
马克思第一次明确论述无产阶级历史使命和无产阶级必须与科学理论相结合思想的著作是()。
1949年6月,毛泽东发表了系统阐明中国共产党关于建立新中国主张的()。
关于明朝“缇骑”的叙述,不正确的是()
中国第一条自行设计修建的铁路是在()
根据材料,结合有关知识,回答问题:埃及的河流空了,人(可以)徒步涉过。人们找不到能行船的水。河床变成了沙滩。沙滩上没有水,河床上也没有水……一切好东西都不见了,这个地方枯竭了……土地缩小了,(但是)它的行政人员却很多。土地荒凉不毛;(但)税却很重,只有
Demandpaging算法是paging算法在虚拟存储空间管理的扩展。其主要的改进是:仅当需要访问某页面时,如果它不在内存,把它调入内存。按照这个思路,将segmentation算法(段式存储管理算法)扩展到虚拟存储空间管理,也可以产生类似的算法,不妨
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[0]=true;While(flag[1]);
拟建设一个光通信骨干网络连通BJ、CS、XA、QD、JN、NJ、TL和WH等8个城市,图中无向边上的权值表示两个城市间备选光纤的铺设费用。请回答下列问题。图可采用图的哪一种存储结构?给出求解计算总费用所使用的算法名称。
随机试题
A、 B、 C、 D、 C
下列各项中,除哪项外都是九味羌活汤的组成药物()
【背景资料】某卫生中心由五幢大楼(门诊楼、急诊楼、住院楼等)组成,卫生中心的机电工程内容有建筑给水排水、建筑电气、通风与空调、消防工程和电梯安装工程。卫生中心还建设一个变电所、水泵房和锅炉房,机电工程的冷水机组、锅炉、变配电设备和电梯等大型设备均由业主采
小学生的想象多属于()。
小河说,我在河里流淌得多么欢畅;堤岸说。那是因为有了我的束缚。小河说。如果没有你,我会流淌得更加欢畅。于是,小河离开了堤岸。不久。小河就不复存在了。谈谈你对这则寓言的看法。
误解性危机,是指企业自身的工作或产品质量等方面没有什么问题,没有出现任何损害公众的事件,但是由于种种原因,被公众误解怀疑,受到公众无端指责,企业由此而陷人危机之中。事故性危机是指由于企业自身的失职、失误,或者管理工作中出现问题.或者产品质量上出现问题,而引
根据以下资料,回答下列问题。截至2011年底,我国石油剩余技术可采储量32.4亿吨,天然气4.02万亿方;煤炭查明资源储量1.38万亿吨,铁矿743.9亿吨,铜矿8612万吨,铝土矿38.7亿吨,金矿7419吨。2011年我国矿产资源勘查投资1118.
联网的各个计算机共享一个公共通信信道,当一台计算机发送消息时,所有其他计算机都能“收听”到此消息。这种网络称为【】网络。
Friendshipisunconditionalanduncritical,basedonlyonmutualrespectandtheabilitytoenjoyeachother’scompany.Theseau
NaturallanguageinterfacesenabletheusertocommunicatewiththecomputerinFrench,English,German,orahuman【S1】______la
最新回复
(
0
)