数据结构课程设计报告--- 建立二叉树并求指定结点路径

1、数据结构课程设计报告数据结构课程设计报告 1 电子与信息工程学院 数据结构课程设计报告 ( 2010( 201020112011 年度第一学期年度第一学期) ) 课程名称： 数据结构课程设计 题 目： 建立二叉树并求指定结点路径 院 系： 电信学院计算机系 班 级： 计算机 08 本（1） 姓 名： * 学 号： * 指导教师： * 成 绩： 2010 年 12 月 4 日 数据结构课程设计报告数据结构课程设计报告 2 题目题目 建立二叉树并求指定结点路径建立二叉树并求指定结点路径 问题描述问题描述 要求能够按先序遍历的次序输入二叉树的各个结点， 并能够输出中序遍历的 序列，以及指定结点的路径

2、 基本要求基本要求 分别建立二叉树存储结构的输入函数、输出中序遍历的函数，以及输出指定 结点路径的函数 课程设计的需求和规格说明课程设计的需求和规格说明 1、定义二叉树的存储结构，每个结点中设置三个域，即值域、左指针域、右指针域。 要建立二叉树 T 的链式存储结构，即建立二叉链表。根据输入二叉树结点的形式不同，建 立的方法也不同，本系统采用先序序列递归建立二叉树，建立如下图所示的二叉树。应该 在程序运行窗口的主控菜单后，先选择“1 1”并回车，紧接着在程序运行窗口中提示信息 “输入二叉树的先序序列结点值输入二叉树的先序序列结点值: :” 之后， 采用以下字符序列： ABCDEGF （以替代空格

3、）作为建立二叉树 T 的输入字符序列并回车，窗口出现：二叉树的链式存二叉树的链式存 储结构建立完成储结构建立完成! ! 2、二叉树的遍历。本系统采用非递归中序遍历算法进行中序遍历，这意味着遍历右子 树时不再需要保存当前层的根指针，可直接修改栈顶记录中的指针即可。需要在程序运行 窗口的主控菜单中选择“2 2” 并回车，程序运行窗口会出现以下中序遍历序列：该二叉树该二叉树 的中序遍历序列是的中序遍历序列是: : CBEGDFA 3 3、求二叉树的指定结点路径。在程序运行窗口的主控菜单中选择“3 3” 并回车，在 程序运行窗口中提示信息“输入要求路径的结点值:”输入“G” 并回车，会得到结果为： A

4、BDEG 如果输入“I” 并回车，会得到结果为：没有要求的结点！没有要求的结点！ 图 1 二叉树的图形结构 数据结构课程设计报告数据结构课程设计报告 3 设计设计 设计思想：设计思想： 我们知道，在二叉树上无论采用哪种遍历方法，都能够访问遍树中的所有结点。由于 访问结点的顺序不同，前序遍历和中序遍历都很难达到设计的要求；但采用后序遍历二叉 树是可行的，因为后序遍历是最后访问根结点，按这个顺序将访问过的结点存储到一个顺 序栈中，然后再输出即可。因此，我们可以非递归地后序遍历二叉树 T，当后序遍历访问 到结点*p 时， 此时栈中存放的所有结点均为给定结点*p 的祖先， 而由这些祖先便构成了一 条从根结点到结点*p 之间的路径。 设计表示：设计表示： 为实现上述的设计思想，首先要定义二叉树的链式存储结构，我们采用二叉链表的方 式，相应的类型说明为：