问题描述:

设计一个算法,计算出给定二叉树中任意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;
}