最近公共祖先问题.ppt
《最近公共祖先问题.ppt》由会员分享,可在线阅读,更多相关《最近公共祖先问题.ppt(9页珍藏版)》请在三一文库上搜索。
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 个正
2、整数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,总节点数 各节点的儿子数以及儿
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最近 公共 祖先 问题
链接地址:https://www.31doc.com/p-3391978.html