欢迎来到天天文库
浏览记录
ID：52043204
大小：131.00 KB
页数：10页
时间：2020-03-31
《最近公共祖先问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、最近公共祖先问题罗汉忠2008.4.21问题描述与实验任务问题描述：给定一棵树，设计一个算法对于给定的两个结点返回他们的最近公共祖先实验任务：对于给定的树和树中的结点对，输出最近公共祖先数据输入有文件input.txt给出输入数据，第一行有一个正整数n，表示树有n个结点，标号为1,2,3,……,n,标号为1的是树根。接下来的n行，第i+1行描述与第i个结点相关联的子结点信息。其中，每行的第一个正整数k表示该节点的儿子数，其后的k个数，每一个数表示儿子结点的标号，当k=0时表示它是叶节点文件的第n+2行是一个正整数m，表示要计算最近公共祖先的m个结点
2、对。接下来的m行，每行有两个数，表示要计算最近公共祖先的结点标号数据输出将计算出来的m个节点队的最近公共祖先结点标号输出到output.txt,每行三个数，前两个是结点标号，第三个是他们的最近公共祖先标号输入数据样例12（n）323425600278291000021112005(m)311712489128103111712248191268102123456789101112算法思想在查询最近公共祖先时，实际上就是一次次的找节点的父亲，所以用父节点数组表示法来表示这棵树实际做法，通过考察规律，可以发现如果把这两个结点的祖先用两个数组来存储，可以
3、非常快的找打他的最近公共祖先752101234567891011127结点10结点106210算法特点分析只要把两个结点的祖先数组存储下来，然后最坏情况下只要O(N)时间，最好清空下只要O(1)就可以找到这里都只是自己的算法思想，源程序我就不黏贴在这里了。呵呵thankyou
此文档下载收益归作者所有
