欢迎来到天天文库
浏览记录
ID:58874712
大小:58.50 KB
页数:8页
时间:2020-09-21
《树上任意两结点的路径求法.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、...《数据结构》课程设计报告题目:树上任意两个结点间路径的查找班级:姓名:学号:完成日期:.......一、问题描述例如:知识题第28个任务——树上任意两个结点间路径的查找:对于任意的一棵树,任给该树中的两个结点,可以在该树中找到从其中一个结点到另一个结点的一条路径。路径是树中结点的序列,a1a2…an是树中结点a1到结点an的一条路径,当且仅当a1,a2…,an均是树中的结点,且对任意的ai和ai+1(1<=i2、在计算机表示这棵树。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”:-#Pleas4、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=='')(*bt7、)=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
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
此文档下载收益归作者所有