問題描述:
設計一個算法，計算出給定二叉樹中任意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;
}