资源描述：
《数据结构课程设计说明书 树的应用 树和二叉树的转换》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构课程设计说明书树的应用树和二叉树的转换导读：就爱阅读网友为您分享以下“数据结构课程设计说明书树的应用树和二叉树的转换”资讯，希望对您有所帮助，感谢您对92to.com的支持!中北大学数据结构与算法课程设计说明书学院、系：专业：班级：学生姓名：设计题目：起迄日37期:指导教师:软件学院软件工程1314010xxx学号：1314010xxx树的应用2015年1月12日-2015年1月29日尹四清2015年1月29日一、需求分析1.设计内容及设计要求A.设计内容：（1）建立一棵树；（2）将树转换成二叉树；（3）实现二叉树的前序、中
2、序、后序的递归和非递归遍历算法。B.设计要求：(1)符合课题要求，实现相应功能；(2)要求界面友好美观，操作方便易行；(3)注意程序的实用性、安全性；2.本演示程序中，元素为单个字符，以空格表示空树(即结点为空)37，以回车符作为输入结束标志，树采用孩子兄弟表示法，二叉树采用二叉链表表示法。在真实的运行过程中，由用户手动输入待创建树的含有空格的先根次序序列，并按回车结束，程序会将其转化为其对应的二叉树，然后对二叉树进行先序、中序、后序的递归及非递归遍历以及层序遍历，然后显示转化后二叉树的高度和总结点数，以验证所创建的二叉树是否正确，
3、最后，销毁创建的树和二叉树，程序结束。3.演示程序以用户和计算机对话方式执行，即在计算机终端（屏幕）上显示“提示信息”之后，由用户在键盘上输入演示程序规定的运算命令，相应的输入数据和运算结果显示在其后。4.为了美观，程序的输出结果采用了分块显示的模式，由虚线及标题隔开，便于用户检查和验证。5.测试数据如图，给出一棵树，若屏幕上显示如下信息：-请按树的先根次序输入序列，如有空子树，用空格填充，完成后输入回车确认此时，你应当输入：（↙表示回车确认）ABEFCDGHIJK↙提示：为方便确认输入了几个空格，用星号’*’表示输入序列中的空格，
4、则序列如下ABE*F**C*DGHI*J*K******↙37（不是真实的输入序列，供计算需输入空格个数时用）这时，建好的树的先根和后根次序序列如下：树的先根序列ABEFCDGHIJK树的后根序列EFBCIJKHGDA1由树和二叉树的转换关系知，二叉树的先序和中序遍历所得序列分别与树的先根和后根遍历所得序列相同，据此验证转化是否正确。二叉树的先序和中序遍历序列如下：二叉树先序序列ABEFCDGHIJK二叉树中序序列EFBCIJKHGDA二、概要设计为了实现上述程序功能，树采用孩子兄弟表示法，二叉树采用二叉链表表示法。为此，需要两个抽
5、象数据类型，树和二叉树的抽象数据类型。1.树的抽象数据类型定义ADTTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树；若D仅含有一个数据元素，则R为空集，否则R={H}，H37是如下二元关系：(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)若D-{root}≠Φ，则存在D-{root}的一个划分D1,D2,D3,„,Dm(m0)，对于任意j≠k(1≤j,k≤m)有Dj∩Dk=Φ,且对任意的i(1≤i≤m)，唯一存在数据元素xi∈Di有root,xi∈H;(3)对应于
6、D-{root}的划分，H-{root,xi,„,root,xm}有唯一的一个划分H1，H2,„,Hm(m0)，对任意j≠k(1≤j,k≤m)有Hj∩Hk=Φ，且对任意i(1≤i≤m),Hi是Di上的二元关系，(Di,{Hi})是一棵符合本定义的树，称为根root的子树。基本操作P：InitTree(&T);操作结果：构造空树T。DestroyTree(&T);初始条件：树T存在。操作结果：销毁树T。CreateTree(&T,definition);初始条件：definition给出树T的定义。操作结果：按definition构造
7、树T37。ClearTree(&T);2初始条件：树T存在。操作结果：将树T清为空树。TreeEmpty(T);初始条件：树T存在。操作结果：若T为空树，则返回TRUE，否则返回FALSE。TreeDepth(T);初始条件：树T存在。操作结果：返回Ｔ的深度。Root(T);初始条件：树T存在。操作结果：返回T的根。Value(T,cur_e);初始条件：树T存在，cur_e是T中某个结点。操作结果：返回cur_e的值。Assign(T,cur_e,value);初始条件：树T存在，cur_e是T中某个结点。操作结果：结点cur_e
8、赋值为value。Parent(T,cur_e);初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非根结点，则返回它的双亲，否则函数值为“空”。37LeftChild(T,cur_e);初始条件：树T存在，c
