数据结构课程设计报告-二叉树根节点到指定节点的路径
数据结构课程设计报告二叉树根节点到指定节点的路径——递归调用思想班级：__ 软件092________ 姓名：_ __________ 指导教师：__ 成绩：___________________ 信息工程学院2011 年 6 月17 日- 2 - 摘要(题目): 二叉树根节点到指定节点的路径 1.引言二叉树是n 个结点
的有穷个集合，它或者是空集（n=0），或者同时满足以下两个条件；（1）有且仅有一个称为根的结点；（2）其余结点分为两个互不相交的集合T1，T2，并且T1，T2，都是二叉树，分别称为根的左子树和右子树。二叉树形结构在客观世界中大量存在，如行政组织机构和人类社会的家谱关系等都可用二叉树结构形象地表示。在计算机应用领域，二叉树也被广泛地应用。例如在编译程序中，可用二叉树来表示源程序的语法结构；在数据库系统中，可用二叉树来表示组织信息；在计算机图形学中，可用二叉树来表示图像关系等。因此对二叉树的研究具有重要意义。2.需求分析利用一个简单的菜单，通过菜单项进行选择，实现和完成如下功能：用先序输入，建立二叉树存储结构、求指定结点的路径。对于建立二叉树存储结构，考虑到栈和队列的存储结构比较繁琐，从而定义一指针数组来一一存储该二叉树先序遍历过的结点，并对该结点进行判断是否为指定的目标结点，并进行输出等操作。 3.概要设计对二叉树采用链式存储结构，其结构定义如下：typedef struct
node{ DataType data; struct node
*lchild,*rchild; }BinTNode,*BinTree; 每个结点中设置三个域，即值域data，左指针域*lchild 和右指针域*rchild。本程序分为6 大模块：全局变量定义、创建结构体、创建二叉链表存储表示、查找目标结点、求结点路径、主函数。（1）全局变量定义（2）创建结构体（3）创建二叉链表存储表示：定义二叉树的链式存储结构，输入数据生成二叉树。（4）查找目标结点：采用二叉链表作为存储结构，利用递归方法，对各个结点进行判断改结点是否在二叉树中。- 3 - （5）求结点路径：采用二叉链表作为存储结构，利用先序遍历二叉树方法以及指针数组的存储结构方法，对结点路径的遍历查找及输出。（6）主函数程序流程图重要函数有主函数int main（）输入函数scanf（）输出函数printf（）二叉树的先序建立函数CreateBiTree（）结点查找函数FindBT（）求结点路径函数NodePath（）4.详细设计（1）定义二叉树用链式存储结构存储二叉树。其中，了lchild 和rchild 是分别指向该结点左孩子和右孩子的指针，data 是数据元素的内容。定义二叉树结点值的类型为字符型且结点个数不超过100 个，具体实现方法如下：二叉树的根节点到指定节点的路径主程序代码输入函数输出函数
建立函数查找函数求路径函数- 4 - typedef struct node{ DataType data; struct node
*lchild,*rchild; }BinTNode,*BinTree; （2）建立二叉树创建二叉链表存储的二叉树。按二叉树带空指针的先序次序输入结点值，结点类型为字符型。按先序次序输入，其中“@”表示空结点。算法是按照先序遍历思想设计的。构造二叉链表表示的二叉树，“@”符号表示空树。具体实现方法如下：Status CreateBiTree(BinTree &bt) { char ch; printf("ch="); scanf("%c",&ch); getchar(); if (ch=='@') bt=NULL; else { bt=(BinTNode *)malloc(sizeof(BinTNode)); bt->data=ch; //生成根结点CreateBiTree(bt->lchild); //构造左子树CreateBiTree(bt->rchild); //构造右子树} return OK; } （3）查找函数- 5 - 函数功能是用递归方法对二叉树进行先序遍历查找，调用此函数可以返回二叉树中指定目标结点。算法思想：若找到目标结点，则返回该目标结点；否则访问二叉树的根结点；先序遍历根的左子树；先序遍历根的右子树。具体实现方法如下：void FindBT(BinTree bt,DataType x) { if((bt!=NULL) && !found) { if(bt->data==x)
{p=bt;found=1;} else { FindBT(bt->lchild,x); //遍历查找左子树FindBT(bt->rchild,x); //遍历查找右子树} } } BinTNode *Findx(BinTree bt,DataType x) {//按给定值查找结点int found=0; //用found 来作为是否查找到的标志BinTree p=NULL; //置空指针FindBT(bt,x); return(p); } 7）求指定结点路径：该函数功能是根据已创建的二叉树和输
入的目标结点，调用此函数可以查找并输出目标结点的路径。算法思想：根据先序遍历二叉树的递归定义，采用一个指针数组来保存返回的结点。先扫描根结点的左子树上的结点并写入指针数组。判断该结点是否与指定目标结点相等，若不相等，然后扫描该结点的右结点并写- 6 - 入指针数组，再扫描该右结点的所有左结点写入指针数组。当一个结点的左孩子树均访问完后再访问该结点，并与给定的结点比较。若相等，则循环输出指针数组中的所有元素，而这个顺序值就是要求的路径。若不相等，则继续上述过程。具体实现方法如下：void NodePath(BinTree bt,BinTNode *ch) {//求二叉树根结点到给定结点*p 的路径typedef enum {FALSE,TRUE}boolean; BinTNode *stack[num]; //定义指针数组int tag[num]; int i,top; boolean find; BinTNode *s; find=FALSE; top=0; s=bt; do { while(s!=NULL) {//扫描左子树top++; stack[top]=s; tag[top]=0; s=s->lchild; } if(top>0) { s=stack[top]; if(tag[top]==1) - 7 - { if(s==ch) {//找到ch,则显示从根结点到ch 的路径
for(i=1;i<=top;i++) printf("->%c",stack[i]->data);
find=TRUE; } else top--; s=stack[top]; }//endif if(top>0 && !find) { if(tag[top]!=1) { s=s->rchild; //扫描右子树tag[top]=1; } else s=NULL; }//endif }//endlif }while(!find && top!=0); } （8）主函数：- 8 - 该函数为程序的主函数
功能是循环输出菜单，功能界面；从界面获取功能菜单中对应的字符，通过switch()语句实现对函数的调用，进而实现功能。具体代码如下：int main() { bool isStop; BinTree bt; char ch1; int xz=1; printf("\t
*********************************************** ***********\n"); printf("\t *\t\t\t\t\t\t\t *\n"); printf("\t *\t\t 欢迎来到这里\t\t *\n"); printf("\t * \t \t 建立二叉树并求指定结点路径\t \t *\n"); printf("\t *\t\t\t\t\t\t\t *\n"); printf("\t
*********************************************** ***********\n"); while(xz){ /*****输出菜单,功能*****/ printf("\n \n"); printf("
=================================== =============\n"); - 9 - printf(" 1.建立二叉树的存储结构\n"); printf(" 2.求二叉树指定结点的路径\n"); printf(" 0.Exit System!\n"); printf("
=================================== =============\n"); printf("请选择:(0-2)\n");
scanf("%d",&xz); getchar(); switch(xz) { case 1:printf("输入二叉树的先序序列结点值:\n"); CreateBiTree(bt); printf("二叉树的链式存储结构建立完成! \n"); printf("\n"); break; case 2:printf("路径的节点值是：\n"); ch1=getchar();
p=NULL; found=0; Findx(bt,ch1); if(p!=NULL) - 10 - NodePath(bt,p); else printf("没有要求的节点!\n");
printf("\n"); break; }// switch }// while } 源程序：
#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; Status CreateBiTree(BinTree &bt) - 11 - { char ch; printf("ch="); scanf("%c",&ch); getchar(); if (ch=='@')
bt=NULL; else { bt=(BinTNode *)malloc(sizeof(BinTNode)); bt->data=ch; //生成根结点CreateBiTree(bt->lchild); //构造左子树CreateBiTree(bt->rchild); //构造右子树} return OK; } void NodePath(BinTree bt,BinTNode *ch) {//求二叉树根结点到给定结点*p 的路径typedef enum {FALSE,TRUE}boolean; BinTNode *stack[num]; //定义栈int tag[num]; int i,top; boolean find; BinTNode *s;
find=FALSE; top=0; s=bt; - 12 - do { while(s!=NULL) {//
扫描左子树top++; stack[top]=s; tag[top]=0;
s=s->lchild; } if(top>0) { s=stack[top]; if(tag[top]==1) { if(s==ch) {//找到ch,则显示从根结点到ch 的路径
for(i=1;i<=top;i++) printf("->%c",stack[i]->data);
find=TRUE; } else top--; s=stack[top]; }//endif if(top>0
&& !find) { - 13 - if(tag[top]!=1) { s=s->rchild; //扫描右子树tag[top]=1; } else
s=NULL; }//endif }//endlif }while(!find && top!=0); } void FindBT(BinTree bt,DataType x) { if((bt!=NULL) && !found) { if(bt->data==x) {p=bt;found=1;} else
{ FindBT(bt->lchild,x); //遍历查找左子树
FindBT(bt->rchild,x); //遍历查找右子树} } } - 14 - BinTNode *Findx(BinTree bt,DataType x) {//按给定值查找结点int found=0; //用found 来作为是否查找到的标志BinTree p=NULL; //置空指针FindBT(bt,x); return(p); } int main() { bool isStop; BinTree bt; char ch1; int xz=1; printf("\t
*********************************************** ***********\n"); printf("\t *\t\t\t\t\t\t\t *\n"); printf("\t *\t\t 欢迎来到这里\t\t *\n"); printf("\t * \t \t 建立二叉树并求指定结点路径\t \t *\n"); printf("\t *\t\t\t\t\t\t\t *\n"); printf("\t
*********************************************** ***********\n"); - 15 - while(xz){ /*****输出菜单,功能*****/ printf("\n \n"); printf("
=================================== =============\n"); printf(" 1.建立二叉树的存储结
构\n"); printf(" 2.求二叉树指定结点的路径\n"); printf("
0.Exit System!\n"); printf("
=================================== =============\n"); printf("请选择:(0-2)\n");
scanf("%d",&xz); getchar(); switch(xz) { case 1:printf("输入二叉树的先序序列结点值:\n"); CreateBiTree(bt); printf("二叉树的链式存储结构建立完成! \n"); printf("\n"); break; - 16 - case 2:printf("路径的节点值是：\n"); ch1=getchar(); p=NULL; found=0; Findx(bt,ch1); if(p!=NULL) NodePath(bt,p); else printf("没有要求的节点!\n");
printf("\n"); break; }// switch }// while } 5.测试结果- 17 - - 18 - 6.调试分析本设计是先序输入的，当然也可以中序和后序输入，为了减小时间和空间复杂度，所以只设计了先序输入。对于先序，中序，后序等访问，需要的话，也可以按要求加入。本设计的缺点是，输错了的话，要重新输入。
7.设计体会虽然都说“程序＝数据结构＋算法”，但我们在学习运用数据结构编程之前，并没能深刻体会到这一点，直到这次课设实践。我们感受最深的一点是：以前用C 编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭单纯的意识和简单的语句来堆砌出一段程序。还体会到深刻理解数据结构的重要性。只有真正理解这样定义数据类型的好处，才能用好这样一种数据结构。了
解典型数据结构的性质是非常有用的，它往往是编写程序的关键。以前对递归算法一直很害怕，总是看不明白究竟这递归是怎么进行的。在这次实验中终于克服了这一障碍，一次次单步执行书中递归函数的例子，并一遍遍在心中自己默默的走，终于弄明白了，真的是功夫不负有心人啊！同时还根据自己的理解写出了类似的递归函数实现了新的功能，真是受益良多啊！在这次实验中，对参数的调用也进行了很多种尝试，已差不多经能够选择合适的参数形式来实现函数之间的数据传输交互了。这次实验中也出现过一些比较严重的错误。在主函数调用CreateBiTree (&bt)的参数&bt 误写成元素bt，在调试程序时给我们团队带来一定的
封面
山东建筑大学
2009级工程造价专业毕业设计任务书
题目：山东省职业技术学院办公楼工程项目
商务标书
设计期限：自2011年7月
至2011年10月
班级：0720913141
学生姓名：
学号：
指导教师(签字)：任成友
庄春华
山东建筑大学毕业设计任务书