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

《树上任意两结点的路径求法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、...《数据结构》课程设计报告题目：树上任意两个结点间路径的查找班级：姓名：学号：完成日期：.......一、问题描述例如：知识题第28个任务——树上任意两个结点间路径的查找：对于任意的一棵树，任给该树中的两个结点，可以在该树中找到从其中一个结点到另一个结点的一条路径。路径是树中结点的序列，a1a2…an是树中结点a1到结点an的一条路径，当且仅当a1,a2…,an均是树中的结点，且对任意的ai和ai+1(1<=i

2、在计算机表示这棵树。3.能够接受从字符终端输入的任意两个结点，当这两个结点均是同一棵树中的结点时，可输出它们之间的路径；当这两个结点不是同一棵树中的结点时，输出错误提示。无论什么情况下，当输入不正确时均提示用户重新输入。4.编写函数createTree,创建一棵树。5.编写函数isNode,判断任一结点是否在指定的树中。6.编写函数searchPath，生成树中两结点间的路径。7.编写函数printPath，输出树中两结点间的路径。二、需求分析先输入根结点，然后提示自左向右依次输入各结点的孩子，如果没有孩子，则输入#，直至整棵树输入完成，并给出提示。举例：输入的树如下图所示。

3、屏幕显示应为：（斜体为输入容）Pleaseinputtheroot:-L-lPleaseinputthesonof“L-1”:-L-l-lPleaseinputthesonof“L-1”:-L-l-2Pleaseinputthesonof“L-1”:-L-l-3Pleaseinputthesonof“L-1”:-#Pleaseinputthesonof“L-1-1”:-#Pleaseinputthesonof”L-1-2”:-L-1-2-1Pleaseinputthesonof”L-1-2”:-L-1-2-2Pleaseinputthesonof“L-1-2”:-#Pleas

4、einputthesonof”L-1-3”:-L-1-3-1Pleaseinputthesonof”L-1-3”:-#Pleaseinputthesonof”L-1-2-1”:-#Pleaseinputthesonof”L-1-2-2”:-#Pleaseinputthesonof”L-1-3-1”:-#.......Finished!当树输入完成后，给出输入结点的提示，并要求输入任意两个结点，结点间以逗号（“，”）分割，并以回车（“↲”）作为结束。例如：PleaseinputTWOnodesofthetree(separatedbyacomma,e.g.,a,b):␣L_1,

5、L_2↲“L_2”isNOTinthetree!PleaseinputTWOnodesofthetreeagain:␣输入要求与格式结点间的路径以结点序列的形式给出。在结点序列中，任意两结点之间以一个制表符分隔。每行最多显示5个结点。例如，当给定结点L_1_1和L_1_2_2时，输出结果应为：ThepathfromL_1_1toL_1_2_2is:L_1_1L_1L_1_2L_1_2_2测试说明对于下图所示的树，测试用例1：输入两结点：P,M输出结果：“P”isNOTinthetree!测试用例2：输入两结点：N,P输出结果：“P”isNOTinthetree!测试用例3：输

6、入两结点：N,M输出结果：NKHCADIM三、程序设计#include#include#definenum100#defineOK1typedefintStatus;typedefchardatatype;typedefstructnode{datatypedata;structnode*lchild,*rchild;}BinTNode,*BinTree;intfound;BinTNode*p;.......Statuscreatetree(BinTree*bt){charch;scanf("%c",&ch);if(ch=='')(*bt

7、)=NULL;else{(*bt)=(BinTNode*)malloc(sizeof(BinTNode));(*bt)->data=ch;createtree(&(*bt)->lchild);createtree(&(*bt)->rchild);}returnOK;}voidsearchPath(BinTreebt,BinTNode*ch){typedefenum{FALSE,TRUE}boolean;BinTNode*stack[num];inttag[num];inti,top;booleanfin