1、 数据结构与算法课程设计数据结构与算法课程设计 说说 明明 书书 学学 院 、 系院 、 系 ： 软件学院 专专 业业： 软件工程 班班 级级： 学学 生生 姓姓 名：名： 学学 号：号： 设设 计计 题题 目目： 树的应用 起起 迄迄 日日 期期: 2015 年 1 月 12 日- 2015 年 1 月 29 日 指指 导导 教教 师师: 2015 年 1 月 29 日 1 一、需求分析一、需求分析 1.设计内容及设计要求 A.设计内容： （1）建立一棵树； （2）将树转换成二叉树； （3）实现二叉树的前序、中序、后序的递归和非递归遍历算法。 B.设计要求： (1) 符合课题要求，实现相应功
2、能； (2) 要求界面友好美观，操作方便易行； (3) 注意程序的实用性、安全性； 2.本演示程序中，元素为单个字符，以空格表示空树(即结点为空)，以回车符作为输入结束标 志，树采用孩子兄弟表示法，二叉树采用二叉链表表示法。在真实的运行过程中，由用户手动 输入待创建树的含有空格的先根次序序列， 并按回车结束， 程序会将其转化为其对应的二叉树， 然后对二叉树进行先序、中序、后序的递归及非递归遍历以及层序遍历，然后显示转化后二叉 树的高度和总结点数，以验证所创建的二叉树是否正确，最后，销毁创建的树和二叉树，程序 结束。 3.演示程序以用户和计算机对话方式执行，即在计算机终端（屏幕）上显示“提示信息
3、”之后， 由用户在键盘上输入演示程序规定的运算命令，相应的输入数据和运算结果显示在其后。 4.为了美观，程序的输出结果采用了分块显示的模式，由虚线及标题隔开，便于用 户检查和验证。 5.测试数据 如图，给出一棵树，若屏幕上显示如下信息： -请按树的先根次序输入序列，如有空子树，用空格填充，完成后输入回车确认 此时，你应当输入：（表示回车确认） ABE F C DGHI J K 提示：为方便确认输入了几个空格，用星号*表示输入序列中的空格，则序列如下 ABE*F*C*DGHI*J*K*（不是真实的输入序列，供计算需输入空格个数时用） 这时，建好的树的先根和后根次序序列如下： 树的先根序列树的先根
4、序列 A B E F C D G H I J K 树的后根序列树的后根序列 E F B C I J K H G D A 2 由树和二叉树的转换关系知， 二叉树的先序和中序遍历所得序列分别与树的先根和后根遍历 所得序列相同，据此验证转化是否正确。二叉树的先序和中序遍历序列如下： 二叉树先序序列二叉树先序序列 A B E F C D G H I J K 二叉树中序序列二叉树中序序列 E F B C I J K H G D A 二、概要设计 为了实现上述程序功能，树采用孩子兄弟表示法，二叉树采用二叉链表表示法。为此，需 要两个抽象数据类型，树和二叉树的抽象数据类型。 1.树的抽象数据类型定义 ADT Tree 数据对象 D：D 是具有相同特性的数据元素的集合。 数据关系 R：若 D 为空集，则称为空树； 若 D 仅含有一个数据元素，则 R 为空集，否则 R=H，H 是如下二元关系： (1)在 D 中存在唯一的称为根的数据元素 root，它在关系 H 下无前驱； (2)若 D-root，则存在 D-
