文章作者: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) 问题貌似还是比较高级的玩意,貌似还要用并查集...反正咱现在不会,以后研究了再修改...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
/*
求二叉树任意两节点最短路径长度
Slyar
http://www.slyar.com
2009.5.22
*/
#include <stdio.h>
#include <malloc.h>
/* 二叉树节点定义 */
typedef struct node
{
int data;
int lchild;
int rchild;
}bitree;
/* 定义全局变量 */
int n, dis, sign;
bitree *t;
/* 函数声明 */
int Search(int);
int ShortestPath(int, int);
int GetPathLength(int, int);
/* 主函数 */
int main()
{
int i, m, a, b, c;
int start, end;
int length;
/* 定义文件指针 */
FILE *fp1, *fp2;
/* 以只读方式打开输入文件 input.txt */
if((fp1 = fopen("input.txt","r")) == NULL)
{
printf("Cannot open this file./n");
exit(0);
}
fscanf(fp1, "%d", &n);
/* 动态分配空间 */
t = (bitree*) calloc(n + 1, sizeof(bitree));
/* 读入二叉树 */
for (i = 1; i <= n; i++)
{
fscanf(fp1, "%d%d%d", &a, &b, &c);
t[i].data = a;
t[i].lchild = b;
t[i].rchild = c;
}
fscanf(fp1, "%d", &m);
/* 以写入方式打开输出文件 output.txt */
if((fp2 = fopen("output.txt","w")) == NULL)
{
printf("Cannot open this file./n");
exit(0);
}
while (m--)
{
fscanf(fp1, "%d %d", &start, &end);
/* 求解最短路径 */
length = ShortestPath(start, end);
fprintf(fp2, "%d %d %d/n", start, end, length);
}
/* 关闭输入文件 */
fclose(fp1);
/* 关闭输出文件 */
fclose(fp2);
/* 注销分配的空间 */
free(t);
return 0;
}
/* 计算最短路径,找最近的共同祖先结点 */
int ShortestPath(int start, int end)
{
int i;
int dis1, dis2;
/* 共同祖先节点肯定在序号较小结点的上方 */
for (i = (start < end ? start:end); i > 0; i--)
{
/* 求start节点的祖先结点路径长度 */
sign = 0;
dis = 0;
dis1 = GetPathLength(i, start);
/* 求end节点的祖先结点路径长度 */
sign = 0;
dis = 0;
dis2 = GetPathLength(i, end);
/* 如果有共同祖先结点则最短路径为两路径之和 */
if (dis1 != 0 && dis2 != 0)
{
/* 小于0说明起始结点就是要找的,路径长度应为0 */
if (dis1 < 0) dis1 = 0;
if (dis2 < 0) dis2 = 0;
return dis1 + dis2;
}
}
}
/* 求以start为根的二叉树中编号为key的结点路径长度 */
int GetPathLength(int start, int key)
{
/* 遇到叶子结点停止递归 */
if (start != 0)
{
/* 找到key就返回。如果起始结点就是要找的,返回-1 */
if (t[start].data == key)
{
sign = 1;
return -1;
}
/* 没找到则递归搜索左子树 */
if (!sign) GetPathLength(t[start].lchild, key);
/* 没找到则递归搜索右子树 */
if (!sign) GetPathLength(t[start].rchild, key);
/* 找到key后返回,每次路径长度+1 */
if (sign) dis++;
}
return dis;
}
|
分享到:
相关推荐
数据结构与算法代码,有图,二叉树,avl树,最短路径
C#算法实现(哈希表 图 二叉树 KMP prim 最短路径 各种排序)!希望大家喜欢!
matlab程序,找出网络中确定两点间的所有最短路径。 注意:输入的矩阵为邻接矩阵。如果两点间没有相邻,请将参数设较大数,例如点i和点j间没有相邻,则将Aij设为999。
证明了有向双环网络的直径等于其二叉树的树高,研究了任意两节点之间的最短路径与其所在层及其相应位置的关系,给出有向双环网络任意两节点最短路径的算法。运用此算法,只需简单的算术运算和关系运算,就能快速求出...
对二叉树,计算任意两个结点的最短路径长度。 输入 第一行输入测试数据组数T 第二行输入n,m 。n代表结点的个数,m代表要查询的数据组数 接下来n行,每行输入两个数,代表1~n结点的孩子结点,如果没有孩子结点则输入-...
实现二叉树的定义及基本操作,实现迪杰斯特拉最短路径算法
都是从网上下载的,希望不要投诉我哈!线性表,二叉树和队列的都是基本操作,图的是最短路径。
判断两颗二叉树是否相似,C语言二叉树部分入门小程序,适合C语言课程的入门小练习 判断两颗二叉树是否相似,C语言二叉树部分入门小程序,适合C语言课程的入门小练习 判断两颗二叉树是否相似,C语言二叉树部分入门...
数据结构报告 一元稀疏多项式运算器 唯一确定的二叉树 求最短路径 内部排序算法性能比较
数据结构课程设计报告-最短路径算法-二叉树的三种遍历.docx
二叉树的直径指的是该二叉树上任意两个节点路径长度中最长的一条,其长度为这两个节点之间经过的边数。 可以使用深度优先搜索(DFS)来求解二叉树的直径。具体做法如下: 定义一个私有变量 diameter,用于存储当前...
在研究城市道路网络特征基础上,建立城市道路网络模型及其数据库,应用一种改进的Dijkstra算法对城市道路进行最短路径查询,该算法是从起点和终点分别用二叉树按起点到终点和终点到起点的方向进行搜索。在计算某一段...
C语言 二叉树实验报告,创建并输出二叉树,输出内容有:图形、数的深度、数的叶子数量。然后根据所创建的二叉树进行线序遍历,创建一棵先序线索二叉树链表,并非递归地输出先序遍历序列。包含各函数算法,源代码。
利用递归方式完成二叉树的简单创建以及遍历。
写出一个示例并输出示例的直径(输出直径即输出最长路径上的节点)及其路径长度(路径长度为树的高度-1)。 BinaryTree(T inlist[], T postlist[]) //以中根和后根次序遍历序列构造二叉树,递归算法 static void ...
用vc++实现用最短路径查找赫夫曼树。n个权值构成n棵二叉树的集合F={T1, T2, …, Tn},其中每棵二叉树Ti中只有一个带树为Ti的根结点。
数据结构的内容,关于二叉树具体操作c语言代码
数据结构遍历二叉树算法(前序、中序、后序),C语言版程序(附完成版实验报告),完全可运,供大家参考。
NULL 博文链接:https://128kj.iteye.com/blog/1632218