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

《数据结构》课程设计报告题目：树上任意两个结点间路径的查找班级：姓名：学号：完成日期：1一、问题描述例如：知识题第28个任务——树上任意两个结点间路径的查找：对于任意的一棵树，任给该树中的两个结点，可以在该树中找到从其中一个结点到另一个结点的一条路径。路径是树中结点的序列，a1a2…an是树中结点a1到结点an的一条路径，当且仅当a1,a2…,an均是树中的结点，且对任意的ai和ai+1(1=in),它们之间存在父子关系。编写程序1.可接受从字符终端输入的任意的树。如果未按输入格式输入，或输入不正确，应分别给出错误提示。2.可用顺序存储结构或链式存储结构在计算机内表示这棵树。3.能够接受从字符终端输入的任意两个结点，当这两个结点均是同一棵树中的结点时，可输出它们之间的路径；当这两个结点不是同一棵树中的结点时，输出错误提示。无论什么情况下，当输入不正确时均提示用户重新输入。4.编写函数createTree,创建一棵树。5.编写函数isNode,判断任一结点是否在指定的树中。6.编写函数searchPath，生成树中两结点间的路径。7.编写函数printPath，输出树中两结点间的路径。二、需求分析先输入根结点，然后提示自左向右依次输入各结点的孩子，如果没有孩子，则输入#，直至整棵树输入完成，并给出提示。举例：输入的树如下图所示。屏幕显示应为：（斜体为输入内容）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”:-#Pleaseinputthesonof”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”:-#2Finished!当树输入完成后，给出输入结点的提示，并要求输入任意两个结点，结点间以逗号（“，”）分割，并以回车（“↲”）作为结束。例如：PleaseinputTWOnodesofthetree(separatedbyacomma,e.g.,a,b):␣L_1,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：输入两结点：N,M输出结果：NKHCADIM三、程序设计#includestdio.h#includestdlib.h#definenum100#defineOK1typedefintStatus;typedefchardatatype;typedefstructnode{datatypedata;structnode*lchild,*rchild;}BinTNode,*BinTree;intfound;BinTNode*p;Statuscreatetree(BinTree*bt)3{charch;scanf(%c,&ch);if(ch=='@')(*bt)=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;booleanfind;BinTNode*s;find=FALSE;top=0;s=bt;do{while(s!=NULL){top++;stack[top]=s;tag[top]=0;s=s-lchild;}if(top0){s=stack[top];if(tag[top]==1){if(s==ch){for(i=1;i=top;i++)printf(-%c,stack[i]-data);find=TRUE;4}elsetop--;s=stack[top];}if(top0&&!find){if(tag[top]!=1){s=s-rchild;tag[top]=1;}elses=NULL;}}}while(!find&&top!=0);}voidisNode(BinTreebt,datatypex){if((bt!=NULL)&&!found){if(bt-data==x){p=bt;found=1;}else{isNode(bt-lchild,x);isNode(bt-rchild,x);}}}BinTNode*Findx(BinTreebt,datatypex){intfound=0;BinTreep=NULL;isNode(bt,x);return(p);}//printPath函数未能写出，但已有大概思路：比较两个叶子节点的路径。从根节点开始往下查找，若发现节点不同，则说明两条路径从此节点分叉。即可输出两叶子节点间的路径！intmain()5{BinTreebt;intxz=1;charch1,ch2;BinTreetree;while(xz){printf(建立二叉树并求指定节点路径\n);printf(===========================\n);printf(1.建立二叉树的存储结构\n);printf(2.求两指定节点的路径\n);printf(0.退出系统\n);printf(===========================\n);printf(请选择:(0-2)\n);scanf(%d,&xz);getchar();switch(xz){case0:break;case1:printf(输入二叉树的先序序列节点值:\n);createtree(&bt);getchar();printf(二叉树的链式存储结构建立完成!\n);break;case2:printf(输入要求路径的节点值:\n);ch1=getchar();ch2=getchar();p=NULL;found=0;isNode(bt,ch1);if(p!=NULL){printf(节点1的路径为:\n);searchPath(bt,p);printf(\n);}elseprintf(没有找到输入的节点:\n);break;isNode(bt,ch2);if(p!=NULL){printf(节点2的路径为:\n);searchPath(bt,p);6printf(\n);}elseprintf(没有找到输入的节点:\n);break;printPath(ch1,ch2);}}}五、测试分析六、设计小结printPath函数未能写出，但已有大概思路：比较两个叶子节点的路径。从根节点开始往下查找，若发现节点不同，则说明两条路径从此节点分叉。即可输出两叶子节点间的路径！七、使用说明建立二叉树并求指定节点路径建立二叉树的存储结构求两指定节点的路径退出系统八、附录7由于程序稍有复杂，输出函数未能写出，希望在今后学习中有机会查漏补缺，完成设计。