树上任意两结点的路径求法

《数据结构》课程设计报告

题 目： 树上任意两个结点间路径的查找 班 级： 姓 名： 学 号： 完成日期：

. . .

一、问题描述

例如：

知识题第28个任务——树上任意两个结点间路径的查找

：

对于任意的一棵树，任给该树中的两个结点，可以在该树中找到从其中一个结点到另一个结点的一条路径。路径是树中结点的序列，a1a2…an是树中结点a1到结点an的一条路径，当且仅当a1,a2…,an均是树中的结点，且对任意的ai和ai+1(1<=i

编写程序

1. 可接受从字符终端输入的任意的树。如果未按输入格式输入，或输入不正确，应分别给

出错误提示。 2. 可用顺序存储结构或链式存储结构在计算机表示这棵树。

3. 能够接受从字符终端输入的任意两个结点，当这两个结点均是同一棵树中的结点时，可

输出它们之间的路径；当这两个结点不是同一棵树中的结点时，输出错误提示。无论什么情况下，当输入不正确时均提示用户重新输入。 4. 编写函数create Tree,创建一棵树。

5. 编写函数isNode,判断任一结点是否在指定的 树中。 6. 编写函数searchPath，生成树中两结点间的路径。 7. 编写函数printPath，输出树中两结点间的路径。

二、需求分析

先输入根结点，然后提示自左向右依次输入各结点的孩子，如果没有孩子，则输入#，直至整棵树输入完成，并给出提示。 举例：输入的树如下图所示。 屏幕显示应为：（斜体为输入容） Please input the root:-L-l

Please input the son of “L-1”:-L-l-l Please input the son of “L-1”:-L-l-2 Please input the son of “L-1”:-L-l-3 Please input the son of “L-1”:-# Please input the son of “L-1-1”:-# Please input the son of”L-1-2”:-L-1-2-1 Please input the son of”L-1-2”:-L-1-2-2 Please input the son of “L-1-2”:-# Please input the son of”L-1-3”:-L-1-3-1 Please input the son of”L-1-3”:-# Please input the son of”L-1-2-1”:-# Please input the son of”L-1-2-2”:-# Please input the son of”L-1-3-1”:-#

.. ..

. . .

Finished!

当树输入完成后，给出输入结点的提示，并要求输入任意两个结点，结点间以逗号（“，”）分割，并以回车（“?”） 作为结束。例如：

Please input TWO nodes of the tree (separated by a comma, e.g., a,b):?L_1,L_2?

“L_2” is NOT in the tree!

Please input TWO nodes of the tree again:?

输入要求与格式

结点间的路径以结点序列的形式给出。在结点序列中，任意两结点之间以一个制表符分隔。每行最多显示5个结点。

例如，当给定结点L_1_1和L_1_2_2时，输出结果应为： The path from L_1_1 to L_1_2_2 is: L_1_1 L_1 L_1_2 L_1_2_2 测试说明

对于下图所示的树，

测试用例1： 输入两结点：P,M

输出结果：“P” is NOT in the tree! 测试用例2： 输入两结点：N,P

输出结果：“P” is NOT in the tree! 测试用例3： 输入两结点：N,M 输出结果：

N K H C A D I M

三、程序设计

#include #include #define num 100 #define OK 1

typedef int Status; typedef char datatype; typedef struct node {

datatype data;

struct node *lchild, *rchild; }

BinTNode,*BinTree; int found; BinTNode *p;

.. ..