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