数据结构课程设计报告-二叉树根节点到指定节点的路径

《数据结构课程设计报告-二叉树根节点到指定节点的路径》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程设计报告二叉树根节点到指定节点的路径——递归调用思想班级：__软件092________姓名：___________指导教师：__成绩：___________________信息工程学院2011年6月17日-18-摘要(题目):二叉树根节点到指定节点的路径1.引言二叉树是n个结点的有穷个集合，它或者是空集（n=0），或者同时满足以下两个条件；（1）有且仅有一个称为根的结点；（2）其余结点分为两个互不相交的集合T1，T2，并且T1，T2，都是二叉树，分别称为根的左子树和右子树 。二叉树形结构在客观世界中大量存在，如行政组织机构和人类社会的家谱关系等都可用二

2、叉树结构形象地表示。在计算机应用领域，二叉树也被广泛地应用。例如在编译程序中，可用二叉树来表示源程序的语法结构；在数据库系统中，可用二叉树来表示组织信息；在计算机图形学中，可用二叉树来表示图像关系等。因此对二叉树的研究具有重要意义。2.需求分析利用一个简单的菜单，通过菜单项进行选择，实现和完成如下功能：用先序输入，建立二叉树存储结构、求指定结点的路径。对于建立二叉树存储结构，考虑到栈和队列的存储结构比较繁琐，从而定义一指针数组来一一存储该二叉树先序遍历过的结点，并对该结点进行判断是否为指定的目标结点，并进行输出等操作。3.概要设计对二叉树采用链式存储结构，其结构定义

3、如下：typedefstructnode{DataTypedata;structnode*lchild,*rchild;}BinTNode,*BinTree;每个结点中设置三个域，即值域data，左指针域*lchild和右指针域*rchild。  本程序分为6大模块：全局变量定义、创建结构体、创建二叉链表存储表示、查找目标结点、求结点路径、主函数。  （1）全局变量定义  （2）创建结构体  （3）创建二叉链表存储表示：定义二叉树的链式存储结构，输入数据生成二叉树。  （4）查找目标结点：采用二叉链表作为存储结构，利用递归方法，对各个结点进行判断改结点是否在二叉树中

4、。-18-  （5）求结点路径：采用二叉链表作为存储结构，利用先序遍历二叉树方法以及指针数组的存储结构方法，对结点路径的遍历查找及输出。（6）主函数 程序流程图二叉树的根节点到指定节点的路径主程序代码输入函数输出函数建立函数查找函数求路径函数 重要函数有主函数                                   intmain（）输入函数                                  scanf（）输出函数                                  printf（）二叉树的先序建立函数           

5、    CreateBiTree（）结点查找函数                              FindBT（）求结点路径函数                            NodePath（）4.详细设计（1）定义二叉树用链式存储结构存储二叉树。其中，了lchild和rchild是分别指向该结点左孩子和右孩子的指针，data是数据元素的内容。定义二叉树结点值的类型为字符型且结点个数不超过100个，具体实现方法如下：-18-typedefstructnode{DataTypedata;structnode*lchild,*rchild;}BinT

6、Node,*BinTree;（2）建立二叉树创建二叉链表存储的二叉树。按二叉树带空指针的先序次序输入结点值，结点类型为字符型。按先序次序输入，其中“@”表示空结点。算法是按照先序遍历思想设计的。构造二叉链表表示的二叉树，“@”符号表示空树。具体实现方法如下：StatusCreateBiTree(BinTree&bt){charch;printf("ch=");scanf("%c",&ch);getchar();if(ch=='@')bt=NULL;else{bt=(BinTNode*)malloc(sizeof(BinTNode));bt->data=ch;//生成

7、根结点CreateBiTree(bt->lchild);//构造左子树CreateBiTree(bt->rchild);//构造右子树}returnOK;}（3）查找函数-18- 函数功能是用递归方法对二叉树进行先序遍历查找，调用此函数可以返回二叉树中指定目标结点。算法思想：若找到目标结点，则返回该目标结点；否则访问二叉树的根结点；先序遍历根的左子树；先序遍历根的右子树。具体实现方法如下：voidFindBT(BinTreebt,DataTypex){if((bt!=NULL)&&!found){if(bt->data==x){p=bt;found=1;}els