问题描述:
设计一个算法，计算出给定二叉树中任意2 个结点之间的最短路径。
编程任务:
对于给定的二叉树，和二叉树中结点对，编程计算结点对之间的最短路径。
数据输入:
第1行有1个正整数n，表示给定的二叉树有n个顶点，
编号为1，2，…，n。接下来的n行中，每行有3个正整数a,b,c，分别表示编号为a的结点
的左儿子结点编号为b，右儿子结点编号为c。各结点信息按照层序列表的顺序给出。
文件的第n+2行是1个正整数m，表示要计算最短路径的m个结点对。接下来的m行，
每行2 个正整数，是要计算最短路径的结点编号。
结果输出:
每行1 个正整数，是结点对编号之间的最短路径长度。
输入文件示例
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
输出文件示例
3
5
3
3
3
代码->
#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 100
typedef struct node
{
struct node * lChild, * rChild;
int data;
}Tree;
Tree* Node[MAX_SIZE];//在这程序中，即当作栈，又当作队
//按层非递归创建二叉树
Tree* LevelCreate()
{
int n, sign, a, b, c;
int front = -1;
int rear = -1;
scanf("%d", &n);
sign = n;
Tree* root = NULL;
Tree* node = NULL;
Tree* lChild = NULL;
Tree* rChild = NULL;
do
{
scanf("%d%d%d", &a, &b, &c);//分别输入根结点a和a的左右孩子b和c
if (a != 0)
{
if (sign == n)//对树的根结点入队，即输入的第一个结点
{
node = new Tree();
node->data = a;
node->lChild = NULL;
node->rChild = NULL;
root = node;
Node[++rear] = node;//入队
}
node = Node[++front];//出队
if (b != 0)//对左孩子b入队
{
lChild = new Tree();
lChild->data = b;
Node[++rear] = lChild;
node->lChild = lChild;
}
else
{
node->lChild = NULL;
}
if (c != 0)//对右孩子c入队
{
rChild = new Tree();
rChild->data = c;
Node[++rear] = rChild;
node->rChild = rChild;
}
else
{
node->rChild = NULL;
}
}
}while (--n);
return root;
}
//前序遍历打印二叉树
void PreOrder(Tree* root)
{
int i =-1;
if (root != NULL)
{
Node[++i] = root;
}
while (i != -1)
{
root = Node[i--];
printf("%d\t", root->data);
if (root->rChild != NULL)
{
Node[++i] = root->rChild;
}
if (root->lChild != NULL)
{
Node[++i] = root->lChild;
}
}
printf("\n");
}
/**///////////////////////////////////////全局变量
int h, k;
/**///////////////////////////////////////对二叉树前序遍历计算某个根结点分别到a和b的路径。用h和k表示
bool Distance1(Tree* root, int a, int b)
{
h = k = -1;
Tree* root2 = root;
int i = -1, j = -1, sign1 = 0, sign2 = 0;
int str1[100], str2[100] ;//标记结点到根结点root的路径
Tree* Node2[100];
if (root != NULL)
{
Node[++i] = root;
Node2[++j] = root;
str1[i] = 0;
str2[j] = 0;
}
while (sign1 !=1 || sign2 !=1)//当a和b没全找到时循环查找a和b
{
if (!sign1 && i != -1)
{
h = str1[i];
root = Node[i--];
}
if (!sign2 && j != -1)
{
k = str2[j];
root2 = Node2[j--];
}
if ( sign1 !=1)
{
//如果当前节点或左右孩子等于a，则标记a已找到
if (root->data == a ||root->rChild && root->rChild->data == a ||
root->lChild && root->lChild->data == a)
{
sign1 = 1;
if (root->data != a)//若root->data != a表示是左右孩子中的一个跟a相等，所以路径加1
{
h++;
}
}
else
{
if (root->rChild != NULL)
{
Node[++i] = root->rChild;
str1[i] = h + 1;
}
if (root->lChild != NULL)
{
Node[++i] = root->lChild;
str1[i] = h + 1;
}
}
}
if ( sign2 != 1)
{
if (root2->data == b || root2->rChild && root2->rChild->data == b ||
root2->lChild && root2->lChild->data == b)//同上
{
sign2 = 1;
if (root2->data != b)
{
k++;
}
}
else
{
if (root2->rChild != NULL)
{
Node2[++j] = root2->rChild;
str2[j] = k + 1;
}
if (root2->lChild != NULL)
{
Node2[++j] = root2->lChild;
str2[j] = k + 1;
}
}
}
if (i == -1 && j == -1)//当i和j都是-1时，表示都查找完毕。终止循环
{
break;
}
}
if (sign1 && sign2)//如果sign1和sign2 都为1，表示a和b都被找到。
{
return true;
}
return false;
}
//枚举计算a和b的最短路径
void Distance2(Tree* root, int a, int b)
{
int i = -1, total = 100, sign = 0;
Tree* node = NULL;
if (root)
{
Node[++i] = root;
}
while (i != -1)
{
root = Node[i--];
node = root;
if (Distance1(node, a, b))
{
sign = 1;
if (total > h + k)//如果当前路径比total小，则令total等于当前路径
{
total = h + k;
}
}
if (root->rChild)//对右孩子入栈
{
Node[++i] = root->rChild;
}
if (root->rChild)//对左孩子入栈
{
Node[++i] = root->lChild;
}
}
if (sign)//sign为1表示a和b存在。输出两者的路径
{
printf("%d\n",total);
}
else
{
printf("Find false\n");
}
}
int main()
{
int m, a, b;
Tree* root = LevelCreate();
PreOrder(root);
scanf("%d", &m);
while (m--)
{
scanf("%d%d", &a, &b);
Distance2(root, a,b);
}
system("pause");
return 0;
}