《最近公共祖先问题教案》由会员分享，可在线阅读，更多相关《最近公共祖先问题教案（9页珍藏版）》请在金锄头文库上搜索。
1、最近公共祖先问题Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望问题描述：问题描述：设计一个算法，对于给定的树中2 结点返回它们的最近公共祖先。实验任务：实验任务：对于给定的树，和树中结点对，计算结点对的最近公共祖先。数据输入：数据输入：由文件input.txt给出输入数据。第一行有1 个正整数n，表示给定的树有n个顶点，编号为1，2，n。编号为1 的顶点是树根。接下来的n 行中，第i+1 行描述与i 个顶点相关联的子结点的信息。每行的第一个正整数k表示该顶点的儿子结点数。其后k个数
2、中，每1 个数表示1个儿子结点的编号。当k=0 时表示相应的结点是叶结点。文件的第n+2 行是1 个正整数m，表示要计算最近公共祖先的m个结点对。接下来的m行，每行2 个正整数，是要计算最近公共祖先的结点编号。结果输出结果输出:将计算出的m个结点对的最近公共祖先结点编号输出到文件output.txt。每行3 个正整数，前2 个是结点对编号，第3 个是它们的最近公共祖先结点编号。输入文件示例输入文件示例input.txt123 2 3 42 5 6002 7 82 9 100002 11 120053 117 124 89 128 10输出文件示例输出文件示例output.txt3 11 17
3、12 24 8 19 12 68 10 2总节点数各节点的儿子数以及儿子节点要求最近公共祖先节点对总数各个节点对基本算法思路1234567811 12910011122558866父节点数组表示法深度012341.利用父节点数组表示法建树；2.建树的过程中利用结构体将每个节点的深度存入节点中；3.求出p（深度较大）、q（深度较小）两节点的深度差，利用深度差，找出与q同深度的p的祖先p；4.p的祖先p和q一起往上搜索，直到搜索到相同的节点就停止搜索并输出。搜索节点10和11的公共祖先数据结构的选取struct defint f;int l;父亲编号f 节点深度l0011 11 112222535
4、3848463 63树的建立树的建立n na0.l=0;/a0.l=0;/根节点深度为根节点深度为0 0n nfor(i=0;in;i+)for(i=0;in;i+)n n n nscanf(%d,&m);scanf(%d,&m);n nfor(j=0;jm;j+)for(j=0;jm;j+)n n n nscanf(%d,&temp);scanf(%d,&temp);n natemp-1.f=i;/atemp-1.f=i;/存入父亲的编号存入父亲的编号n natemp-1.l=ai.l+1;/atemp-1.l=ai.l+1;/深度比父亲大一深度比父亲大一n n n n 公共祖先的搜索公共祖
5、先的搜索n nif(ap.laq.l)temp=p;p=q;q=temp;if(ap.laq.l)temp=p;p=q;q=temp;n n/ /判断深度大的节点判断深度大的节点n ntemp=ap.l-aq.l;/temp=ap.l-aq.l;/求出深度差求出深度差n nfor(j=0;jtemp;j+)p=ap.f;for(j=0;jtemp;j+)p=ap.f;n n/ /求出大深度节点与小深度节点同深度的祖先求出大深度节点与小深度节点同深度的祖先n nwhile(1)while(1)n n n nif(p=q)printf(%dn,p+1);break;if(p=q)printf(%dn,p+1);break;n np=ap.f;p=ap.f;n nq=aq.f;q=aq.f;n n/搜索公共祖先搜索公共祖先算法的优缺点分析和改进复杂度平均O（logN）算法优点：记录深度，为搜索提供方便，节省时间算法缺点：记录深度，使得建树的空间翻倍
