数据结构课程设计报告-二叉树根节点到指定节点的路径.pdf
《数据结构课程设计报告-二叉树根节点到指定节点的路径.pdf》由会员分享,可在线阅读,更多相关《数据结构课程设计报告-二叉树根节点到指定节点的路径.pdf(9页珍藏版)》请在三一文库上搜索。
1、数据结构课程设计报告-二叉树根节点到指定节点的路径 数据结构课程设计报告二叉树根节点到指定节点的路径 递归调用思想班 级:_ 软件 092_ 姓 名:_ _ 指导教师: _ 成 绩:_ 信息工程学院2011 年 6 月 17 日 - 2 - 摘要 (题目 ): 二 叉树根节点到指定节点的路径1.引言二叉树是 n 个结点 的有穷个集合,它或者是空集(n=0 ),或者同时满足以下 两个条件;( 1)有且仅有一个称为根的结点;(2)其余 结点分为两个互不相交的集合T1,T2,并且 T1,T2,都是 二叉树,分别称为根的左子树和右子树。二叉树形结构在 客观世界中大量存在,如行政组织机构和人类社会的家谱
2、关 系 等都可用二叉树结构形象地表示。在计算机应用领域, 二叉树也被广泛地应用。例如在编译程序中,可用二叉树 来表示源程序的语法结构;在数据库系统中,可用二叉树来 表示组织信息;在计算机图形学中,可用二叉树来表示图 像关系等。 因此对二叉树的研究具有重要意义。2.需求分析 利用一个简单的菜单,通过菜单项进行选择,实现和完成如 下功能:用先序输入,建立二叉树存储结构、求指定结点 的路径。对于建立二叉树存储结构,考虑到栈和队列的存 储结构比较繁琐,从而定义一指针数组来一一存储该二叉 树先序遍历过的结点,并对该结点进行判断是否为指定的目 标结点,并进行输出等操作。3.概要设计对二叉树采用链 式存储结
3、构,其结构定义如下:typedef struct node DataType data; struct node *lchild,*rchild; BinTNode,*BinTree; 每个结点中设置三个 域,即值域data ,左指针域 *lchild 和右指针域 *rchild 。 本 程序分为 6 大模块:全局变量定义、创建结构体、创建二叉 链表存储表示、 查找目标结点、 求结 点路径、 主函数。 (1) 全局变量定义(2)创建结构体(3)创建二叉链表存储表 示: 定义二叉树的链式存储结构,输入数据生成二叉树。(4) 查找目标结点: 采用二叉链表作为存储结构,利用递归方法, 对各个结点进行
4、判断改结点是否在二叉树中。- 3 - (5) 求结点路径:采用二叉链表作为存储结构,利用先序遍历二 叉树方法以及指针数组的存储结构方法,对结点路径的遍 历查找及输出。(6)主函数程序流程图重要函数有主 函数 int main () 输入函数scanf() 输出函数printf () 二叉树的先序建立函数CreateBiTree () 结点查找函数 FindBT() 求结点路径函数NodePath() 4.详细设计 (1) 定义二叉树用链式存储结构存储二叉树。其中,了 lchild 和 rchild 是分别指向该结点左孩子和右孩子的指针,data 是数 据元素的内容。定义二叉树结点值的类型为字符
5、型且结点个 数不超过 100 个,具体实现方法如下:二叉树的根节点到 指定节点的路径主程序代码输 入 函 数 输 出 函 数 建 立 函 数 查 找 函 数 求 路 径 函 数 - 4 - typedef struct node DataType data; struct node *lchild,*rchild; BinTNode,*BinTree; (2)建立二叉树创 建二叉链表存储的二叉树。按二叉树带空指针的先序次序输 入结点值,结点类型为字符型。按先序次序输入,其中 “ ” 表示空结点。算法是按照先序遍历思想设计的。构造二叉链 表表示的二叉树,“ ” 符号表示空树。具体实现方法如下:
6、Status CreateBiTree(BinTree printf(“ch=“); scanf(“%c“, getchar(); if (ch=) bt=NULL; else bt=(BinTNode *)malloc(sizeof(BinTNode); bt-data=ch; / 生成根结点CreateBiTree(bt-lchild); /构造左子树 CreateBiTree(bt-rchild); /构造右子树 return OK; (3) 查找函数- 5 - 函数功能是用递归方法对二叉树进行先序遍 历查找,调用此函数可以返回二叉树中指定目标结点。算 法 思想:若找到目标结点,则返回该
7、目标结点;否则访问二叉 树的根结点;先序遍历根的左子树;先序遍历根的右子树。 具体实现方法如下:void FindBT(BinTree bt,DataType x) if(bt!=NULL) 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);
8、 7) 求指定结点路径:该函数功能是根据已创建的二叉树和输 入的目标结点,调用此函数可以查找并输出目标结点的路 径。 算法思想:根据先序遍历二叉树的递归定义,采用一 个指针数组来保存返回的结点。先扫描根结点的左子树上 的结点并写入指针数组。判断该结点是否与指定目标结点相 等,若不相等,然后扫描该结点的右结点并写- 6 - 入指针 数组,再扫描该右结点的所有左结点写入指针数组。当一个 结点的左孩子树均访问完后再访问该结点,并与给定的结 点比较。若相等,则循环输出指针数组中的所有元素,而这 个顺序值就是要求的路径。若不相等,则继续上述过程。 具体实现方法如下:void NodePath(BinTr
9、ee bt,BinTNode *ch) /求二叉树根结点到给定结点*p 的路径typedef enum FALSE,TRUEboolean; BinTNode *stacknum; /定 义指针数组int tagnum; int i,top; boolean find; BinTNode *s; find=FALSE; top=0; s=bt; do while(s!=NULL) /扫描 左子树top+; stacktop=s; tagtop=0; s=s-lchild; if(top0) s=stacktop; if(tagtop=1) - 7 - if(s=ch) / 找到 ch,则显示从
10、根结点到ch 的路径 for(i=1;i%c“,stacki-data); find=TRUE; else top-; s=stacktop; /endif if(top0 /扫描右子树 tagtop=1; else s=NULL; /endif /endlif while(!find (8)主函数:- 8 - 该函数为程序的主函数 功能是循环输出菜单,功能界面;从界面获取功能菜单中对 应的字符,通过switch() 语句实现对函数的调用,进而实现 功能。具体代码如下:int main() bool isStop; BinTree bt; char ch1; int xz=1; printf(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 报告 二叉 树根 节点 指定 路径
链接地址:https://www.31doc.com/p-4738884.html