最近公共祖先问题

《最近公共祖先问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最近公共祖先问题学号：030602312姓名：张玺霖报告时间：(2008-4-21)«问题描述：设计一个算法，对于给定的树中2结点返回它们的最近公共祖先。«实验任务：对于给定的树，和树中结点对，计算结点对的最近公共祖先。«数据输入：由文件input.txt给出输入数据。第一行有1个正整数n，表示给定的树有n个顶点，编号为1，2，…，n。编号为1的顶点是树根。接下来的n行中，第i+1行描述与i个顶点相关联的子结点的信息。每行的第一个正整数k表示该顶点的儿子结点数。其后k个数中，每1个数表示1个儿子结点的编号。当k=0时表示相应的结点是叶结点。　　文件的第n+2行是1个正整数m，表示要计

2、算最近公共祖先的m个结点对。接下来的m行，每行2个正整数，是要计算最近公共祖先的结点编号。«结果输出:将计算出的m个结点对的最近公共祖先结点编号输出到文件output.txt。每行3个正整数，前2个是结点对编号，第3个是它们的最近公共祖先结点编号。输入文件示例input.txt1232342560027829100002111200531171248912810输出文件示例output.txt3111712248191268102总节点数各节点的儿子数以及儿子节点要求最近公共祖先节点对总数各个节点对基本算法思路123456781112910011122558866父节点数组表示法深度0

3、12341.利用父节点数组表示法建树；2.建树的过程中利用结构体将每个节点的深度存入节点中；3.求出p（深度较大）、q（深度较小）两节点的深度差，利用深度差，找出与q同深度的p的祖先p’；4.p的祖先p’和q一起往上搜索，直到搜索到相同的节点就停止搜索并输出。搜索节点10和11的公共祖先数据结构的选取structdef{intf;intl;};父亲编号f节点深度l001111112222535384846363树的建立a[0].l=0;//根节点深度为0for(i=0;i

4、a[temp-1].f=i;//存入父亲的编号a[temp-1].l=a[i].l+1;//深度比父亲大一}}公共祖先的搜索if(a[p].l

5、节省时间算法缺点：记录深度，使得建树的空间翻倍