最近公共祖先问题1.pptVIP

最近公共祖先问题 学号：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，表示要计算最近公共祖先的m个结点对。接下来的m行，每行2 个正整数，是要计算最近公共祖先的结点编号。　　?结果输出:　　将计算出的m个结点对的最近公共祖先结点编号输出到文件output.txt。每行3 个正整数，前2 个是结点对编号，第3 个是它们的最近公共祖先结点编号。 　 输入文件示例 input.txt 12 3 2 3 4 2 5 6 0 0 2 7 8 2 9 10 0 0 0 2 11 12 0 0 5 3 11 7 12 4 8 9 12 8 10　 输出文件示例 output.txt 3 11 1 7 12 2 4 8 1 9 12 6 8 10 2 基本算法思路 数据结构的选取 struct def{int f;int l;}; 树的建立 a[0].l=0;//根节点深度为0 for(i=0;in;i++) { scanf(%d,m); for(j=0;jm;j++) { scanf(%d,temp); a[temp-1].f=i;//存入父亲的编号 a[temp-1].l=a[i].l+1;//深度比父亲大一 } } 公共祖先的搜索 if(a[p].la[q].l){temp=p;p=q;q=temp;} //判断深度大的节点 temp=a[p].l-a[q].l;//求出深度差 for(j=0;jtemp;j++)p=a[p].f; //求出大深度节点与小深度节点同深度的祖先 while(1) { if(p==q){printf(%d\n,p+1);break;} p=a[p].f; q=a[q].f; }//搜索公共祖先 算法的优缺点分析和改进 复杂度平均O（logN） 算法优点：记录深度，为搜索提供方便，节省时间 算法缺点：记录深度，使得建树的空间翻倍 * * * * * * * * * * 总节点数 各节点的儿子数以及儿子节点 要求最近公共祖先节点对总数 各个节点对 1 2 3 4 5 6 7 8 11 12 9 10 0 1 1 1 2 2 5 5 8 8 6 6 父节点数 组表示法 深度 0 1 2 3 4 1.利用父节点数组表示法建树； 2.建树的过程中利用结构体将每个节点的深度存入节点中； 3.求出p（深度较大）、q（深度较小）两节点的深度差，利用深度差，找出与q同深度的p的祖先p’； 4.p的祖先p’和q一起往上搜索，直到搜索到相同的节点就停止搜索并输出。 搜索节点10和11的公共祖先 父亲编号f 节点深度l 00 11 11 11 22 22 53 53 84 84 63 63