《数据结构课程设计报告》由会员分享，可在线阅读，更多相关《数据结构课程设计报告（13页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计报告-二叉树根节点到指定节点的路径数据结构课程设计报告 二叉树根节点到指定节点的路径 递归调用思想班级：软件092姓名：_指导教师：_成绩： 信息工程学院2011年6月17日-2 -摘要（题目）：二 叉树根节点到指定节点的路径1引言二叉树是n个结点 的有穷个集合，它或者是空集（n=0）,或者同时满足以下 两个条件；（1）有且仅有一个称为根的结点；（2）其余 结点分为两个互不相交的集合T1，T2,并且T1，T2,都是 二叉树，分别称为根的左子树和右子树。二叉树形结构在 客观世界中大量存在，如行政组织机构和人类社会的家谱关 系 等都可用二叉树结构形象地表示。在计算机应用领域， 二叉
2、树也被广泛地应用。例如在编译程序中，可用二 叉树 来表示源程序的语法结构；在数据库系统中，可用二叉树来 表示组织信息；在计算机图形学中，可用二 叉树来表示图 像关系等。因此对二叉树的研究具有重要意义。2需求分析 利用一个简单的菜单，通过菜单项进行选择，实现和完成如 下功能：用先序输入，建立二叉树存储结 构、求指定结点 的路径。对于建立二叉树存储结构，考虑到栈和队列的存 储结构比较繁琐，从而定义一指针数组来存储该 二叉树先序遍历过的结点，并对该结点进行判断是否为指定的目 标结点，并进行输出等操作。3概要设计 对二叉树采用链 式存储结构，其结构定义如下：typedef structno de Da
3、taType data; struct node*lchild,*rchild; BinTNode,*BinTree;每个结点中设置三个 域，即值域data，左指针域*lchild和右指针域*rchild。本 程序分为6大模块：全局变量定义、创建结构体、创建二叉 链表存储表示、查找目标结点、求结点路径、主函数。（1） 全局变量定义（2）创建结构体（3）创建二叉链表存储表 示：定义二叉树的链式存储结构，输入数据生成二叉树。（4） 查找目标结点：采用二叉链表作为存储结构，利用递归方法， 对各个结点进行判断改结点是否在二叉树中。-3 - （5） 求结点路径：采用二叉链表作为存储结构，利用先序遍历二
4、叉树方法以及指针数组的存储结 构方法，对结点路径的遍 历查找及输出。（6）主函数 程序流程图重要函数有 主 函数int main （）输入函数scanf （）输出函数printf（） 二叉树的先序建立函数CreateBiTree（）结点查找函数 Find盯（）求结点路径函数NodePath （） 4详细设计（1） 定义二叉树用链式存储结构存储二叉树。其中，了 lchild和 rchild是分别指向该结点左孩子和右孩子的指针，data是数 据元素的内容。定义二叉树结点值的类型为字符型且结点个 数不超过100个，具体实现方法如下：二叉树的根节点到 指定节点的路径主程序代码输入函数输出函数 建立函数
5、查找函数求路径函数-4 - typedef struct no de DataType data; struct node*lchild,*rchild; BinTNode,*BinTree; (2)建立二叉树 创 建二叉链表存储的二叉树。按二叉树带空指针的先序次序输 入结点值，结点类型为字符型。按先序次序输入，其中“ 表示空结点。算法是按照先序遍历思想设计的。构造二叉链 表表示的二叉树，“符号 表示空树。具体实现方法如下： Status CreateBiTree(BinTree &bt) char ch; printf(ch=); sca nf(%c,&ch); getchar(); if
6、(ch=) bt=NULL; else bt=(BinTNode *)malloc(sizeof(BinTNode); bt-data=ch;生成根结点CreateBiTree(bt-lchild); /构造左子树 CreateBiTree(bt-rchild); 构造右子树 return OK; (3) 查找函数-5 -函数功能是用递归方法对二叉树进行先序遍 历查找，调用此函数可以返回二叉树中指定目标结点。算 法 思想：若找到目标结点，则返回该目标结点；否则访问二叉 树的根结点；先序遍历根的左子树；先序遍历 根的右子树。 具体实现方法如下：void Fin dBT(BinTree bt,Da
7、taType x) if(bt!=NULL) & !found) if(bt-data=x) p=bt;fou nd=l; else Fin dBT(bt-lchild,x); 遍历查找左 子树FindBT(bt-rchild,x); /遍历查找右子树 BinTNode *F in dx(BinTree bt,DataType x) / 按给定值查找 结点int found=0; /用found来作为是否查找到的标志 BinTree p=NULL; /置空指针 FindBT(bt,x); return(p); 7) 求指定结点路径：该函数功能是根据已创建的二叉树和输 入的目标结点，调用此函数可
8、以查找并输出目标结点的路 径。算法思想：根据先序遍历二叉树的递归定义，采用一 个指针数组来保存返回的结点。先扫描根结点的左子树 上 的结点并写入指针数组。判断该结点是否与指定目标结点相 等，若不相等，然后扫描该结点的右结点并写-6 -入指针 数组，再扫描该右结点的所有左结点写入指针数组。当一个 结点的左孩子树均访问完后再访问该结 点，并与给定的结 点比较。若相等，贝V循环输出指针数组中的所有元素，而这 个顺序值就是要求的路径。若 不相等，则继续上述过程。 具体实现方法如下：void NodePath(BinTree bt,BinTNode *ch) /求二叉树根结点到给定结点*p的路径type
9、def enum FALSE,TRUEboolea n; BinTNode *stack nu m; / 定 义指针数组 int tagnum; int i,top; boolean find; BinTNode *s; fin d=FALSE; top=0; s=bt; do while(s!=NULL) /扫描 左子树 top+; stacktop=s; tagtop=0; s=s-lchild; if(top0) s=stacktop; if(tagtop=l) - 7 - if(s=ch) /找到ch,则显示从根结点到ch的路径 for(i=1;i%c,stacki-data);fin
10、 d=TRUE; else top-; s=stacktop; /e ndif if(top0 & !find) if(tagtop!=l) s=s-rchild; /扫描右子树 tagtop=1; else s=NULL; /e ndif /e ndlif while(!fi nd & top!=0); (8)主函数：-8 -该函数为程序的主函数功能是循环输出菜单，功能界面；从界面获取功能菜单中对 应的字符，通过switch()语句实现对函数的调用，进而实现 功能。具体代码如下：int mai n() bool isStop; BinTree bt char ch1; int xz=1; p
11、ri ntf(t*n)；卩和 tf(t *ttttttt *n); pri ntf(t *tt 欢迎来到这里tt *n); printf(t * t t 建立二叉树 并求指定结点路径 t t *n); pri ntf(t *ttttttt *n); prin tf(t prin tf(n n); printf( =n); - 9 - pri ntf( 1.建立二叉树的存 储结构n); printf( 2.求二叉树指定结点的路径n); printf( 0. Exit System!n); printf( =n); prin tf(请选择:(0-2)n);n); while(xz) /*输出菜单，
12、功能*/sca nf(%d,&xz); getchar(); switch(xz) case 1:pri ntf(输 入二叉树的先序序列结点值:n); CreateBiTree(bt); printf( 二叉树的链式存储结构建立完成！ n); pri ntf(n); break; case 2:printf(路径的节点值是:n); ch1=getchar(); p=NULL; found=0; Findx(bt,chl); if(p!=NULL) - 10 - NodePath(bt,p); else printf(没有要求的节点!n); printf(n); break; / switch
13、/ while 源程序： #in elude #i nclude #defi ne num 100 #defi ne OK 1 typedef int Status; typedef char DataType; typedef struct no de DataType data; struct node *lchild,*rchild; BinTNode,*BinTree; int found; BinTNode *p; Status CreateBiTree(BinTree &bt) - 11 - char ch; pri ntf(ch=); sca nf(%c,&ch); getcha
14、r(); 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,TRUEboolean; BinTNode *stacknum; /定义栈 int tag num; int i,to
15、p; boolea n find; Bin TNode *s;fin d=FALSE; top=0; s=bt; - 12 - do while(s!=NULL) / 扫描左子树 top+; stacktop=s; tagtop=0; s=s-lchild; if(top0) s=stacktop; if(tagtop=1) if(s=ch) /找到ch,则显示从根结点到ch的路径 for(i=1;iv=top;i+) prin tf(-%c,stacki-data);fin d=TRUE; else top-; s=stacktop; /e ndif if(top0& !find) - 13 - if(tagtop!=l) s=s-rchild; 扫描右子 树 tagtop=1; elses=NULL; /e ndif /e ndlif wh
