最新消息:点击查看大S的省钱秘笈

二叉树任意两点间最短路径长度 C语言暴力版

编程相关 Slyar 132浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

数据结构课的实验题目,涉及到LCA问题,这次暴力解决了,以后学了NB算法回来做个对比...

问题描述:

设计一个算法,计算出给定二叉树中任意2个结点之间的最短路径。

编程任务:

对于给定的二叉树,和二叉树中结点对,编程计算结点对之间的最短路径。

数据输入:

由文件input.txt给出输入数据。第1行有1个正整数n,表示给定的二叉树有n个顶点,编号为1,2,…,n。接下来的n行中,每行有3个正整数a,b,c,分别表示编号为a的结点的左儿子结点编号为b,右儿子结点编号为c。各结点信息按照层序列表的顺序给出。

文件的第n+2行是1个正整数m,表示要计算最短路径的m个结点对。接下来的m行,每行2 个正整数,是要计算最短路径的结点编号。

结果输出:

将编程计算出的m个结点对的最短路径长度输出到文件output.txt。每行3 个正整数,前2 个是结点对编号,第3 个是它们的最短路径长度。

输入文件示例input.txt

9
1 2 3
2 4 5
3 0 0
4 0 0
5 6 7
6 0 0
7 8 9
8 0 0
9 0 0
5
6 9
3 8
4 7
2 9
4 6

输出文件示例output.txt

6 9 3
3 8 5
4 7 3
2 9 3
4 6 3

Tips:因为题目中的2句话,使得这题变得很简单...

1、"第1行有1个正整数n,表示给定的二叉树有n个顶点,编号为1,2,…,n"

2、"各结点信息按照层序列表的顺序给出"

第一句话说明如果我们用数组来存结点,并且从下标1开始,那么结点的值和结点的下标是一样的...

第二句话说明编号小的结点一定在编号大的结点的上方...

这样我们只需要求出2个结点到最近公共祖先结点的路径长度,然后将其相加就可以得到2个结点的最短路径了...

不过 最近公共祖先(Least Common Ancestors) 问题貌似还是比较高级的玩意,貌似还要用并查集...反正咱现在不会,以后研究了再修改...

转载请注明:Slyar Home » 二叉树任意两点间最短路径长度 C语言暴力版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (5)

  1. 树任意两点间不是只有一条路径么? 为何会有最短路径这一说
    ellochen4年前 (2013-04-08)回复
    • 可以一条边走多次。所以最短距离就是两点到其LCA的距离和。一般用tarjan做。
      riaqn4年前 (2013-04-11)回复
  2. @Felix021, Tarjan算法不是要用到并查集么...
    Slyar8年前 (2009-05-24)回复
  3. 我果然转载过这样一篇文章(LCA to RMQ): https://www.felix021.com/blog/read.php?1065
    Felix0218年前 (2009-05-24)回复
  4. LCA是和RMQ互相转化吧,怎么变成并查集了@_@
    Felix0218年前 (2009-05-24)回复