内容发布更新时间 : 2024/12/24 3:58:04星期一 下面是文章的全部内容请认真阅读。

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

数据结构课程设计报告 二叉树根节点到指定节点的路径 ——递归调用思想 班 级：__ 软件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(\scanf(\{ 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）求指定结点路径： 该函数功能是根据已创建的二叉树和输